text: 5 with instantaneous quantities. [For instance, (13): Eq. (15) will now be understood in a sta- (cid:104) (cid:105) 8k T tistical sense: z = 0. Likewise, the swim- K = B , (21) ming eﬃciency Eq. (18) will generalize to 3ΓR2 (cid:104) (cid:105) (cid:104) (cid:105) η = umigr / Q ]. At the same time, the swim- with k the Boltzmann constant and T the B ming stroke will no longer be associated with temperature [42]. The mean dissipation is ob- a closed orbit in deformation space, and the T tained from generalization of Eq. (12): stroke time must be interpreted as a charac- (cid:104) (cid:105) (cid:104) ◦ (cid:105) teristic deformation time of the device. Q˙ = (3ΓR2/8) z˙(t) g(t) , (22) The choice of the statistical quantities to ◦ minimize, and of the constraints to impose in where the in the scalar product indicates the optimization procedure, strongly rests on Stratonovich prescription [40, 41]. Similarly for the speciﬁc problem in which one is interested. the mean migration velocity, that is obtained A swimmer that wants to hit a target in the generalizing Eq. (10): √ shortest possible time, may have uncertainty (the variance of umigr) among the quantities to (cid:104)umigr(cid:105) = −3 3a(cid:104)[z z˙ − z z˙ ](cid:105), (23) minimize or to use as constraints. For the long 16 1 2 2 1 time – steady state regime we are interested in, and it is easy to see, from Eq. (20), that the the most natural choice is that of minimizing term in the average does not depend on the expended power. We thus impose minimization (cid:104) (cid:105) choice of the stochastic prescription. of the mean expended power Q˙ at ﬁxed mean (cid:104) (cid:105) The presence of noise induces a diﬀusive com- migration velocity umigr . Supported by the ponent in migration, which receives contribu- observation that optimal noiseless swimming is tion both from thermal noise in the ﬂuid and achieved at constant Q˙ [and at constant value − random swimming. The ﬁrst contribution to of the rate z z˙ z z˙ in Eq. (10)], we shall 1 2 2 1 diﬀusivity can be estimated as restrict our analysis to a stationary statistics ∼ condition. Dext KR2. (24) We focus on a situation in which the internal (cid:90) forces vary slowly on the scale of the relaxation The second can be obtained from time of the system. This condition appeared to (cid:104) (cid:105) be crucial in stochastic optimization problems Dint = dt uˆ(t)uˆ(0) , involving a ﬁnite time horizon [35], due to the occurrence of singularities in the solution [36]. where √ In [37], the problem was avoided by regulariza- tion (see also [38, 39]). This is not an issue −3 3a − − (cid:104) (cid:105) uˆ = [z z˙ z z˙ ] umigr for the stationary regime considered here, and 16 1 2 2 1 the main advantage of an overdamped regime, is the ﬂuctuating component of the migration is that the dynamics is described by a sim- velocity. Working in polar coordinates (z, φ), ple Langevin equation, and that steady state − we can write z z˙ z z˙ = z2φ˙, and, using Eq. ﬂuctuation-dissipation relations do apply. 1 2 (cid:104) 2 1 (20): The relaxation time can be estimated, in the case of the trimer, by the Stokes time of the (cid:90)27a2 (cid:105) beads τ = m/Γ, where m is the bead mass Dint = 2K S 256 [32]. For spherical beads of radius a and den- (cid:104) (cid:105) sity ρ = λρ : τ = (2/9)λa2/ν , with ν and + dt z(t)g (t)z(0)g (0) . (25) b s S s s φ φ c ρ the kinematic viscosity and the density of s (cid:28) T the solvent. Under the condition τS , the In the present situation, in which noise results dynamics will be described by a Langevin equa- from equilibrium ﬂuctuations in the ﬂuid, and tion the moving parts in the swimmer are small, (cid:104) (cid:105) global diﬀusion, Eq. (24), will dominate over z˙ + g = ξ, ξi(t)ξj(0) = 2Kδijδ(t), (20) random swimming, Eq. (25). In realistic situa- tions, internal noise acquires a non-equilibrium where, imposing validity of the equilibrium component [22], and one should make a sub- → (cid:29) ﬂuctuation-relations, and making use of Eq. stitution K Kint K in both Eqs. (20) ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: with

text: instantaneous

text: quantities.

text: [For

text: instance,

text: Eq.

text: will

text: now

text: be

text: understood

text: in

text: a

text: sta-

text: T

text: tistical

text: sense:

text: z

text: Likewise,

text: the

text: swim-

text: K

text: B

text: ming

text: eﬃciency

text: Eq.

text: will

text: generalize

text: to

text: η

text: umigr

text: Q

text: At

text: the

text: same

text: time,

text: the

text: swim-

text: with

text: k

text: the

text: Boltzmann

text: constant

text: and

text: T

text: the

text: B

text: ming

text: stroke

text: will

text: no

text: longer

text: be

text: associated

text: with

text: temperature

text: The

text: mean

text: dissipation

text: is

text: ob-

text: a

text: closed

text: orbit

text: in

text: deformation

text: space,

text: and

text: the

text: T

text: tained

text: from

text: generalization

text: of

text: Eq.

text: stroke

text: time

text: must

text: be

text: interpreted

text: as

text: a

text: charac-

text: teristic

text: deformation

text: time

text: of

text: the

text: device.

text: Q˙

text: z˙(t)

text: g(t)

text: The

text: choice

text: of

text: the

text: statistical

text: quantities

text: to

text: minimize,

text: and

text: of

text: the

text: constraints

text: to

text: impose

text: in

text: where

text: the

text: in

text: the

text: scalar

text: product

text: indicates

text: the

text: optimization

text: procedure,

text: strongly

text: rests

text: on

text: Stratonovich

text: prescription

text: Similarly

text: for

text: the

text: speciﬁc

text: problem

text: in

text: which

text: one

text: is

text: interested.

text: the

text: mean

text: migration

text: velocity,

text: that

text: is

text: obtained

text: A

text: swimmer

text: that

text: wants

text: to

text: hit

text: a

text: target

text: in

text: the

text: generalizing

text: Eq.

text: shortest

text: possible

text: time,

text: may

text: have

text: uncertainty

text: (the

text: variance

text: of

text: umigr)

text: among

text: the

text: quantities

text: to

text: −3

text: z˙

text: z

text: z˙

text: minimize

text: or

text: to

text: use

text: as

text: constraints.

text: For

text: the

text: long

text: time

text: steady

text: state

text: regime

text: we

text: are

text: interested

text: in,

text: and

text: it

text: is

text: easy

text: to

text: see,

text: from

text: Eq.

text: that

text: the

text: the

text: most

text: natural

text: choice

text: is

text: that

text: of

text: minimizing

text: term

text: in

text: the

text: average

text: does

text: not

text: depend

text: on

text: the

text: expended

text: power.

text: We

text: thus

text: impose

text: minimization

text: choice

text: of

text: the

text: stochastic

text: prescription.

text: of

text: the

text: mean

text: expended

text: power

text: Q˙

text: at

text: ﬁxed

text: mean

text: The

text: presence

text: of

text: noise

text: induces

text: a

text: diﬀusive

text: com-

text: migration

text: velocity

text: umigr

text: Supported

text: by

text: the

text: ponent

text: in

text: migration,

text: which

text: receives

text: contribu-

text: observation

text: that

text: optimal

text: noiseless

text: swimming

text: is

text: tion

text: both

text: from

text: thermal

text: noise

text: in

text: the

text: ﬂuid

text: and

text: achieved

text: at

text: constant

text: Q˙

text: [and

text: at

text: constant

text: value

text: random

text: swimming.

text: The

text: ﬁrst

text: contribution

text: to

text: of

text: the

text: rate

text: z

text: z˙

text: z

text: z˙

text: in

text: Eq.

text: we

text: shall

text: diﬀusivity

text: can

text: be

text: estimated

text: as

text: restrict

text: our

text: analysis

text: to

text: a

text: stationary

text: statistics

text: condition.

text: Dext

text: We

text: focus

text: on

text: a

text: situation

text: in

text: which

text: the

text: internal

text: forces

text: vary

text: slowly

text: on

text: the

text: scale

text: of

text: the

text: relaxation

text: The

text: second

text: can

text: be

text: obtained

text: from

text: time

text: of

text: the

text: system.

text: This

text: condition

text: appeared

text: to

text: be

text: crucial

text: in

text: stochastic

text: optimization

text: problems

text: Dint

text: dt

text: involving

text: a

text: ﬁnite

text: time

text: horizon

text: due

text: to

text: the

text: occurrence

text: of

text: singularities

text: in

text: the

text: solution

text: where

text: In

text: the

text: problem

text: was

text: avoided

text: by

text: regulariza-

text: tion

text: (see

text: also

text: This

text: is

text: not

text: an

text: issue

text: −3

text: uˆ

text: [z

text: z˙

text: z

text: z˙

text: umigr

text: for

text: the

text: stationary

text: regime

text: considered

text: here,

text: and

text: the

text: main

text: advantage

text: of

text: an

text: overdamped

text: regime,

text: is

text: the

text: ﬂuctuating

text: component

text: of

text: the

text: migration

text: is

text: that

text: the

text: dynamics

text: is

text: described

text: by

text: a

text: sim-

text: velocity.

text: Working

text: in

text: polar

text: coordinates

text: (z,

text: φ),

text: ple

text: Langevin

text: equation,

text: and

text: that

text: steady

text: state

text: we

text: can

text: write

text: z

text: z˙

text: z

text: z˙

text: and,

text: using

text: Eq.

text: ﬂuctuation-dissipation

text: relations

text: do

text: apply.

text: The

text: relaxation

text: time

text: can

text: be

text: estimated,

text: in

text: the

text: case

text: of

text: the

text: trimer,

text: by

text: the

text: Stokes

text: time

text: of

text: the

text: beads

text: τ

text: m/Γ,

text: where

text: m

text: is

text: the

text: bead

text: mass

text: Dint

text: S

text: For

text: spherical

text: beads

text: of

text: radius

text: a

text: and

text: den-

text: sity

text: ρ

text: λρ

text: τ

text: with

text: ν

text: and

text: dt

text: z(t)g

text: b

text: s

text: S

text: s

text: s

text: φ

text: φ

text: c

text: ρ

text: the

text: kinematic

text: viscosity

text: and

text: the

text: density

text: of

text: s

text: T

text: the

text: solvent.

text: Under

text: the

text: condition

text: τS

text: the

text: In

text: the

text: present

text: situation,

text: in

text: which

text: noise

text: results

text: dynamics

text: will

text: be

text: described

text: by

text: a

text: Langevin

text: equa-

text: from

text: equilibrium

text: ﬂuctuations

text: in

text: the

text: ﬂuid,

text: and

text: tion

text: the

text: moving

text: parts

text: in

text: the

text: swimmer

text: are

text: small,

text: global

text: diﬀusion,

text: Eq.

text: will

text: dominate

text: over

text: z˙

text: g

text: ξ,

text: random

text: swimming,

text: Eq.

text: In

text: realistic

text: situa-

text: tions,

text: internal

text: noise

text: acquires

text: a

text: non-equilibrium

text: where,

text: imposing

text: validity

text: of

text: the

text: equilibrium

text: component

text: and

text: one

text: should

text: make

text: a

text: sub-

text: ﬂuctuation-relations,

text: and

text: making

text: use

text: of

text: Eq.

text: stitution

text: K

text: Kint

text: K

text: in

text: both

text: Eqs.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 8 The equation for the correlations entering Eq. the forces, controlling the trimer deformation, (39) are obtained from Eqs. (30) and (38). At more intense. For ﬁxed strength of the defor- stationary state: mation forces, some swimming strategies will (cid:104) (cid:105) (cid:104) (cid:105) nevertheless lead to a smaller migration veloc- αss s2 + αsψ sψ = K˜ , ity ﬂuctuation than others. We see that in both (cid:104) (cid:105) (cid:104) (cid:105) (cid:104) (cid:105) α s2 + (α + α ) sψ + α ψ2 = 0, cases of forcing by a uniform drive, and by a cir- ψs ss ψψ sψ (cid:104) (cid:105) (cid:104) (cid:105) culating potential well, minimization of the ran- α sψ + α ψ2 = K˜ . (40) ψs ψψ dom migration velocity component is achieved, in good approximation, together with that of The solutions of Eq. (40) have in general a dissipation. rather complicated form. We can solve the sys- We parametrize the degree of randomness tem explicitly in some special situation. in swimming through the coeﬃcient D˜ = In the case of a purely potential g˜, which (ω/(u¯migr)2)Dint, where Dint is deﬁned in Eq. implies α = α , Eq. (40) gives sψ ψs (25). Substituting (cid:90)Eq. ((cid:104)28) into Eq. (25), we (cid:104) (cid:105) α K˜ obtain, keeping terms up to O(K˜ ): s2 = ψψ− ; αss−αψψ αs2ψ D˜ = 2K˜ + dt˜ 4(cid:104)s(0)s(t˜)(cid:105) (cid:105) (cid:104) (cid:105) α K˜ sψ = sψ− ; (cid:104) (cid:105) (cid:104) (cid:105) αssαψψ αs2ψ + 4 s(0)g˜(t˜) + g˜ψ(0)g˜ψ(t˜) . (42) (cid:104) (cid:105) α K˜ ψ2 = ss − . In the uniform tangential drive case, we have α α α2 − ss ψψ sψ g˜ = α + O(K˜ ). From Eqs. (28) and (30), ψ (cid:104) ψs (cid:105) − | | SubstAituting into Eq. (39), it is possible to see we ﬁnd s(0)s(cid:16)(t˜) = (K˜ /αss) exp( αss(cid:17)t˜), and, that = 1, which is the expected result from substituting into Eq. (42): a purely potential force. 2K˜ − Things change if we consider a dissipative D˜ = 4 + α2 + 2α (α 2) . (43) force. Let us take for simplicity α = α α2 ss ψs ψs − ss ψψ ss and α = α . We obtain ψs sψ Comparing with Eq. (37), we see that minimal (cid:104) (cid:105) (cid:104) (cid:105) (cid:104) (cid:105) s2 = ψ2 = K˜ /α , sψ = 0, contribution to diﬀusion from random swim- ss ming is achieved, together with minimal dis- which, upon substitution into Eq. (39) gives sipation, for αψs = 1. In the case of a forcing by a circulating po- A = 1 + 2αψsK˜ (α − 1). (41) tential well, with αψψ = αss and αsψ = αψs, α ψs we proceed in the same fashio−n. W−e have, ss to lowest order in K˜ : g˜ = α s α ψ − s ss ψψ Dissipation reduction occurs in this case for and g˜ = α ψ + α s, which gives, from ψ ss (cid:104) ψψ (cid:105) (cid:104) (cid:105) 0 < α < 1, corresponding to an increase Eqs. (28) and (30): s(0)s(t˜) = ψ(0)ψ(t˜) = ψs − | | (cid:104) (cid:105) of eﬃciency with respect to the optimal noise- (K˜ /α ) exp( α t˜) and s(0)ψ(t˜) = 0. Sub- ss (cid:16) ss (cid:17) less case η > η¯. Maximum reduction occurs at stituting into Eq. (42), we ﬁnd α = 1/2 [compare with Eq. (37)]. ψs C. Randomness minimization 2K˜ − D˜ = 4 + α2 + α (α 4) . (44) α2 ss ψs ψs ss An optimal microswimmer should have the property of “arriving at the target on time”, Comparing with Eq. (41), we ﬁnd that dissi- if required. Thus, another quantity that one pation reduction implies random swimming re- may wish to minimize is the migration velocity duction, but not vice versa. In this case, min- ﬂuctuation. For simplicity, we keep considering imum random swimming occurs for αψs = 2, the situation of a stationary swimmer, although that is out of the domain in which there is dis- the appropriate setting for such a constraint is sipation reduction. that of a device swimming over a ﬁnite distance V. STRONG NOISE (or over a ﬁnite time interval). One way to minimize swimming randomness, We consider now the situation in which the of course, is to make the deterministic part of random component of the deformations cannot ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: paragraph

text: The

text: equation

text: for

text: the

text: correlations

text: entering

text: Eq.

text: the

text: forces,

text: controlling

text: the

text: trimer

text: deformation,

text: are

text: obtained

text: from

text: Eqs.

text: and

text: At

text: more

text: intense.

text: For

text: ﬁxed

text: strength

text: of

text: the

text: defor-

text: stationary

text: state:

text: mation

text: forces,

text: some

text: swimming

text: strategies

text: will

text: nevertheless

text: lead

text: to

text: a

text: smaller

text: migration

text: veloc-

text: αss

text: αsψ

text: sψ

text: K˜

text: ity

text: ﬂuctuation

text: than

text: others.

text: We

text: see

text: that

text: in

text: both

text: α

text: (α

text: α

text: sψ

text: α

text: ψ2

text: cases

text: of

text: forcing

text: by

text: a

text: uniform

text: drive,

text: and

text: by

text: a

text: cir-

text: ψs

text: ss

text: ψψ

text: sψ

text: culating

text: potential

text: well,

text: minimization

text: of

text: the

text: ran-

text: α

text: sψ

text: α

text: ψ2

text: K˜

text: ψs

text: ψψ

text: dom

text: migration

text: velocity

text: component

text: is

text: achieved,

text: in

text: good

text: approximation,

text: together

text: with

text: that

text: of

text: The

text: solutions

text: of

text: Eq.

text: have

text: in

text: general

text: a

text: dissipation.

text: rather

text: complicated

text: form.

text: We

text: can

text: solve

text: the

text: sys-

text: We

text: parametrize

text: the

text: degree

text: of

text: randomness

text: tem

text: explicitly

text: in

text: some

text: special

text: situation.

text: in

text: swimming

text: through

text: the

text: coeﬃcient

text: D˜

text: In

text: the

text: case

text: of

text: a

text: purely

text: potential

text: g˜,

text: which

text: where

text: Dint

text: is

text: deﬁned

text: in

text: Eq.

text: implies

text: α

text: α

text: Eq.

text: gives

text: sψ

text: ψs

text: Substituting

text: into

text: Eq.

text: we

text: α

text: K˜

text: obtain,

text: keeping

text: terms

text: up

text: to

text: O(K˜

text: ψψ−

text: αss−αψψ

text: αs2ψ

text: D˜

text: dt˜

text: α

text: K˜

text: sψ

text: sψ−

text: αssαψψ

text: αs2ψ

text: α

text: K˜

text: ψ2

text: ss

text: In

text: the

text: uniform

text: tangential

text: drive

text: case,

text: we

text: have

text: α

text: α

text: α2

text: ss

text: ψψ

text: sψ

text: g˜

text: α

text: O(K˜

text: From

text: Eqs.

text: and

text: ψ

text: ψs

text: SubstAituting

text: into

text: Eq.

text: it

text: is

text: possible

text: to

text: see

text: we

text: ﬁnd

text: (K˜

text: /αss)

text: exp(

text: and,

text: that

text: which

text: is

text: the

text: expected

text: result

text: from

text: substituting

text: into

text: Eq.

text: a

text: purely

text: potential

text: force.

text: Things

text: change

text: if

text: we

text: consider

text: a

text: dissipative

text: D˜

text: α2

text: 2α

text: (α

text: force.

text: Let

text: us

text: take

text: for

text: simplicity

text: α

text: α

text: α2

text: ss

text: ψs

text: ψs

text: ss

text: ψψ

text: ss

text: and

text: α

text: α

text: We

text: obtain

text: ψs

text: sψ

text: Comparing

text: with

text: Eq.

text: we

text: see

text: that

text: minimal

text: ψ2

text: K˜

text: /α

text: sψ

text: contribution

text: to

text: diﬀusion

text: from

text: random

text: swim-

text: ss

text: ming

text: is

text: achieved,

text: together

text: with

text: minimal

text: dis-

text: which,

text: upon

text: substitution

text: into

text: Eq.

text: gives

text: sipation,

text: for

text: αψs

text: In

text: the

text: case

text: of

text: a

text: forcing

text: by

text: a

text: circulating

text: po-

text: A

text: 2αψsK˜

text: (α

text: tential

text: well,

text: with

text: αψψ

text: αss

text: and

text: αsψ

text: αψs,

text: α

text: ψs

text: we

text: proceed

text: in

text: the

text: same

text: fashio−n.

text: W−e

text: have,

text: ss

text: to

text: lowest

text: order

text: in

text: K˜

text: g˜

text: α

text: s

text: α

text: ψ

text: s

text: ss

text: ψψ

text: Dissipation

text: reduction

text: occurs

text: in

text: this

text: case

text: for

text: and

text: g˜

text: α

text: ψ

text: α

text: s,

text: which

text: gives,

text: from

text: ψ

text: ss

text: ψψ

text: α

text: corresponding

text: to

text: an

text: increase

text: Eqs.

text: and

text: ψs

text: of

text: eﬃciency

text: with

text: respect

text: to

text: the

text: optimal

text: noise-

text: (K˜

text: /α

text: exp(

text: α

text: t˜)

text: and

text: Sub-

text: ss

text: ss

text: less

text: case

text: η

text: η¯.

text: Maximum

text: reduction

text: occurs

text: at

text: stituting

text: into

text: Eq.

text: we

text: ﬁnd

text: α

text: [compare

text: with

text: Eq.

text: ψs

text: C.

text: Randomness

text: minimization

text: D˜

text: α2

text: α

text: (α

text: α2

text: ss

text: ψs

text: ψs

text: ss

text: An

text: optimal

text: microswimmer

text: should

text: have

text: the

text: property

text: of

text: “arriving

text: at

text: the

text: target

text: on

text: time”,

text: Comparing

text: with

text: Eq.

text: we

text: ﬁnd

text: that

text: dissi-

text: if

text: required.

text: Thus,

text: another

text: quantity

text: that

text: one

text: pation

text: reduction

text: implies

text: random

text: swimming

text: re-

text: may

text: wish

text: to

text: minimize

text: is

text: the

text: migration

text: velocity

text: duction,

text: but

text: not

text: vice

text: versa.

text: In

text: this

text: case,

text: min-

text: ﬂuctuation.

text: For

text: simplicity,

text: we

text: keep

text: considering

text: imum

text: random

text: swimming

text: occurs

text: for

text: αψs

text: the

text: situation

text: of

text: a

text: stationary

text: swimmer,

text: although

text: that

text: is

text: out

text: of

text: the

text: domain

text: in

text: which

text: there

text: is

text: dis-

text: the

text: appropriate

text: setting

text: for

text: such

text: a

text: constraint

text: is

text: sipation

text: reduction.

text: that

text: of

text: a

text: device

text: swimming

text: over

text: a

text: ﬁnite

text: distance

text: V.

text: STRONG

text: NOISE

text: (or

text: over

text: a

text: ﬁnite

text: time

text: interval).

text: One

text: way

text: to

text: minimize

text: swimming

text: randomness,

text: We

text: consider

text: now

text: the

text: situation

text: in

text: which

text: the

text: of

text: course,

text: is

text: to

text: make

text: the

text: deterministic

text: part

text: of

text: random

text: component

text: of

text: the

text: deformations

text: cannot

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ≥ Algorithm 2: Let n+1+g > m 5g+t + 1 2 2 B B Data: Generator matrices for the codes and B0 1 Result: A generator matrix for the code (cid:98) (cid:99) − ≤t+g ≤ − Let b = log n + 1, then n satisﬁes: 2b 1 n < 2b. Therefore, 2 n/2b 2 < 4. 2 B B Compute and using Proposition 9; −2 3 for s = b 2, . . . , 1 B B Compute the codes (cid:98) − (cid:99) and (cid:98) − (cid:99) from the codes B B (t+g)/2s 1 (t+g+1)/2s 1 (cid:98) (cid:99) and (cid:98) (cid:99) by applying twice Theorem 10. (t+g)/2s (t+g+1)/2s endfor (cid:100) (cid:101) Algorithm complexity: We solve 2 log (t + g) + 2 systems of linear equations of 2 type (1) and (2). C C Y Q − Lemma 12. Let Q , . . . , Q be n diﬀerent rational points. Deﬁne = ( , , F Q ). 1 n { } L 1 Let I , . . . , I be diﬀerent subsets of 2, . . . , n such that 1 s ∩ ∅ (cid:80) C − | | ≥ | ∩ | − | ∩ | s I = and k( ) I s I s I j=1 j j i=j+1 i i=j i C C · · · C C Then = (I ) + + (I ) = s (I ). 1 s j=1 j Remark 4. Suppose there exists i > 1 such that n + i + g n + 1 + g > m > . 2 2 B { } Then, to compute , it suﬃces to ﬁnd diﬀerent subsets I , . . . , I of 2, . . . , n with t+g 1 s at least i elements and each satisfying the assumptions of Lemma 12. Then, Algorithm B 1 or 2 will provide the codes (I ) with j = 1, . . . , s from which we obtain the desired t+g j code using Lemma 12. 5.4 From degenerate to non degenerate codes C X Q ⊥ In summary, from the single knowledge of ( , , F ) we are able to compute a C X Q − C X Q L subcode ( , , F E) of ( , , F ) for some positive divisor E. Unfortunately, L L Q C X Q − since E is supported by elements of , the code ( , , F E) is degenerated and L hence not suitable for the construction of an ECP using Corollary 5. In what follows, we C X Q − (cid:48) (cid:48) explain how to compute another code ( , , F E ), where E is linearly equivalent (cid:48) L X (cid:48) to E, i.e. E = E + (h) for some rational function on and such that E has disjoint support with DQ. It should be pointed out that we do not need to compute h but just prove its existence. On the following, we explain how to compute a generator matrix of C X Q − − ( , , F (t + g)P (h)) L B B knowing generator matrices of and . t+g (cid:18) t+g+1B (cid:19) Theorem 13. Let G be a generator matrix of of the form t+g 0 c G = 1 , (0) G 1 7 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: caption

text: Algorithm

text: Let

text: m

text: B

text: B

text: Data:

text: Generator

text: matrices

text: for

text: the

text: codes

text: and

text: Result:

text: A

text: generator

text: matrix

text: for

text: the

text: code

text: ≤t+g

text: Let

text: b

text: log

text: n

text: then

text: n

text: satisﬁes:

text: n

text: Therefore,

text: B

text: B

text: Compute

text: and

text: using

text: Proposition

text: −2

text: for

text: s

text: b

text: B

text: B

text: Compute

text: the

text: codes

text: and

text: from

text: the

text: codes

text: B

text: B

text: and

text: by

text: applying

text: twice

text: Theorem

text: endfor

text: Algorithm

text: complexity:

text: We

text: solve

text: log

text: (t

text: g)

text: systems

text: of

text: linear

text: equations

text: of

text: type

text: and

text: C

text: C

text: Y

text: Q

text: Lemma

text: Let

text: Q

text: Q

text: be

text: n

text: diﬀerent

text: rational

text: points.

text: Deﬁne

text: F

text: Q

text: n

text: L

text: Let

text: I

text: I

text: be

text: diﬀerent

text: subsets

text: of

text: n

text: such

text: that

text: s

text: C

text: s

text: I

text: and

text: k(

text: I

text: s

text: I

text: s

text: I

text: j

text: j

text: i

text: i=j

text: i

text: C

text: C

text: C

text: C

text: Then

text: (I

text: (I

text: s

text: (I

text: s

text: j

text: Remark

text: Suppose

text: there

text: exists

text: i

text: such

text: that

text: n

text: i

text: g

text: n

text: g

text: m

text: B

text: Then,

text: to

text: compute

text: it

text: suﬃces

text: to

text: ﬁnd

text: diﬀerent

text: subsets

text: I

text: I

text: of

text: n

text: with

text: t+g

text: s

text: at

text: least

text: i

text: elements

text: and

text: each

text: satisfying

text: the

text: assumptions

text: of

text: Lemma

text: Then,

text: Algorithm

text: B

text: or

text: will

text: provide

text: the

text: codes

text: (I

text: with

text: j

text: s

text: from

text: which

text: we

text: obtain

text: the

text: desired

text: t+g

text: j

text: code

text: using

text: Lemma

text: From

text: degenerate

text: to

text: non

text: degenerate

text: codes

text: C

text: X

text: Q

text: In

text: summary,

text: from

text: the

text: single

text: knowledge

text: of

text: F

text: we

text: are

text: able

text: to

text: compute

text: a

text: C

text: X

text: Q

text: C

text: X

text: Q

text: L

text: subcode

text: F

text: E)

text: of

text: F

text: for

text: some

text: positive

text: divisor

text: E.

text: Unfortunately,

text: L

text: L

text: Q

text: C

text: X

text: Q

text: since

text: E

text: is

text: supported

text: by

text: elements

text: of

text: the

text: code

text: F

text: E)

text: is

text: degenerated

text: and

text: L

text: hence

text: not

text: suitable

text: for

text: the

text: construction

text: of

text: an

text: ECP

text: using

text: Corollary

text: In

text: what

text: follows,

text: we

text: C

text: X

text: Q

text: explain

text: how

text: to

text: compute

text: another

text: code

text: F

text: E

text: where

text: E

text: is

text: linearly

text: equivalent

text: L

text: X

text: to

text: E,

text: i.e.

text: E

text: E

text: (h)

text: for

text: some

text: rational

text: function

text: on

text: and

text: such

text: that

text: E

text: has

text: disjoint

text: support

text: with

text: DQ.

text: It

text: should

text: be

text: pointed

text: out

text: that

text: we

text: do

text: not

text: need

text: to

text: compute

text: h

text: but

text: just

text: prove

text: its

text: existence.

text: On

text: the

text: following,

text: we

text: explain

text: how

text: to

text: compute

text: a

text: generator

text: matrix

text: of

text: C

text: X

text: Q

text: F

text: (t

text: g)P

text: (h))

text: L

text: B

text: B

text: knowing

text: generator

text: matrices

text: of

text: and

text: t+g

text: Theorem

text: Let

text: G

text: be

text: a

text: generator

text: matrix

text: of

text: of

text: the

text: form

text: t+g

text: c

text: G

text: G

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:0) (cid:1) (cid:0) (cid:1) ∈ F − ∈ B \ B where c n 1 and 0 c − and (0) G is a generator matrix B 1 q 1 t+g (cid:18) t+g 1 (cid:19) X 1 of . Then, there exists a rational function h on such that the matrix t+g+1 (cid:48) 1 c G := 1 (0) G 1 C X Q − − is a generator matrix for ( , , F (t + g)P (h)). L Proof. Let P be any Q , for simplicity take i = 1. ∈ − i \ − | Let f L(F (t+g)P ) L(F (t+g+1)P ) be such that (0 c ) = (f(Q ), . . . , f(Q )). 1 1 n By deﬁnition, v (f) = t + g. From the weak approximation Theorem [24, Theorem 1.3.1], there exisQts1 a rational function h ∈ F (X ) such that q ∀ ≥ (i) i 2, h(Q ) = 1; i − − (ii) v (h) = t g and hf(Q ) = 1. Q1 1 Such a function h yields the result. Details are left to the reader. 6 The Attack 6.1 The algorithm C C X Q ⊥ Recall that the attacker knows a generator matrix of the public code = ( , , F ) pub L and the integer t. ≥ If n+1+g m, then the attack summarizes as follows. Otherwise we have to apply 2 techniques from §. Step 1. Determine the values g and m using Proposition 8. C X Q Step 2. Compute ( , , F ) by Gaussian elimination. L C X Q − Step 3. Compute the code B = ( , , F (t + g)P ), using one of the algorithms L 1 described in §. C X Q − − Step 4. Deduce from B a non degenerated code Bˆ = ( , , F (t + g)P (h)) using L 1 §. Step 5. Apply Corollary 5 to deduce an ECP from Bˆ. 6.2 Complexity C X Q − The costly part of the attack is the computation of the code B = ( , , F Q ) C C X Q L 1 such that (A , B) forms an t-ECP for = ( , , F ). For that purpose we can apply 0 L one of the algorithms proposed in §. Take notice that computing a generator matrix of (cid:18)(cid:18) (cid:19) (cid:18) (cid:19) (cid:19) (cid:18) (cid:19) C (2) and then apply Gaussian elimination to such matrix has complexity: k k ∼ k2n2 O n log2 q + n2 log2 q (cid:0)O log2 q (cid:1). 2 2 2 2 2 2 Roughly speaking the cost of our attack is about O (λ + 1)n4 log2 q where λ denotes 2 the number of linear systems to solve depending on the chosen algorithm from §. The term λ + 1 is due to Theorem 13. 8 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: F

text: B

text: B

text: where

text: c

text: n

text: and

text: c

text: and

text: G

text: is

text: a

text: generator

text: matrix

text: B

text: q

text: t+g

text: t+g

text: X

text: of

text: Then,

text: there

text: exists

text: a

text: rational

text: function

text: h

text: on

text: such

text: that

text: the

text: matrix

text: c

text: G

text: G

text: C

text: X

text: Q

text: is

text: a

text: generator

text: matrix

text: for

text: F

text: (t

text: g)P

text: (h)).

text: L

text: Proof.

text: Let

text: P

text: be

text: any

text: Q

text: for

text: simplicity

text: take

text: i

text: i

text: Let

text: f

text: L(F

text: (t+g)P

text: L(F

text: be

text: such

text: that

text: c

text: (f(Q

text: f(Q

text: n

text: By

text: deﬁnition,

text: v

text: (f)

text: t

text: g.

text: From

text: the

text: weak

text: approximation

text: Theorem

text: Theorem

text: there

text: a

text: rational

text: function

text: h

text: F

text: (X

text: such

text: that

text: q

text: (i)

text: i

text: h(Q

text: i

text: (ii)

text: v

text: (h)

text: t

text: g

text: and

text: hf(Q

text: Such

text: a

text: function

text: h

text: yields

text: the

text: result.

text: Details

text: are

text: left

text: to

text: the

text: reader.

text: The

text: Attack

text: The

text: algorithm

text: C

text: C

text: X

text: Q

text: Recall

text: that

text: the

text: attacker

text: knows

text: a

text: generator

text: matrix

text: of

text: the

text: public

text: code

text: F

text: pub

text: L

text: and

text: the

text: integer

text: t.

text: If

text: m,

text: then

text: the

text: attack

text: summarizes

text: as

text: follows.

text: Otherwise

text: we

text: have

text: to

text: apply

text: techniques

text: from

text: Step

text: Determine

text: the

text: values

text: g

text: and

text: m

text: using

text: Proposition

text: C

text: X

text: Q

text: Step

text: Compute

text: F

text: by

text: Gaussian

text: elimination.

text: L

text: C

text: X

text: Q

text: Step

text: Compute

text: the

text: code

text: B

text: F

text: (t

text: g)P

text: using

text: one

text: of

text: the

text: algorithms

text: L

text: described

text: in

text: C

text: X

text: Q

text: Step

text: Deduce

text: from

text: B

text: a

text: non

text: degenerated

text: code

text: Bˆ

text: F

text: (t

text: g)P

text: (h))

text: using

text: L

text: Step

text: Apply

text: Corollary

text: to

text: deduce

text: an

text: ECP

text: from

text: Bˆ.

text: Complexity

text: C

text: X

text: Q

text: The

text: costly

text: part

text: of

text: the

text: attack

text: is

text: the

text: computation

text: of

text: the

text: code

text: B

text: F

text: Q

text: C

text: C

text: X

text: Q

text: L

text: such

text: that

text: (A

text: B)

text: forms

text: an

text: t-ECP

text: for

text: F

text: For

text: that

text: purpose

text: we

text: can

text: apply

text: L

text: one

text: of

text: the

text: algorithms

text: proposed

text: in

text: Take

text: notice

text: that

text: computing

text: a

text: generator

text: matrix

text: of

text: C

text: and

text: then

text: apply

text: Gaussian

text: elimination

text: to

text: such

text: matrix

text: has

text: complexity:

text: k

text: k

text: O

text: n

text: q

text: q

text: q

text: Roughly

text: speaking

text: the

text: cost

text: of

text: our

text: attack

text: is

text: about

text: O

text: (λ

text: q

text: where

text: λ

text: denotes

text: the

text: number

text: of

text: linear

text: systems

text: to

text: solve

text: depending

text: on

text: the

text: chosen

text: algorithm

text: from

text: The

text: term

text: λ

text: is

text: due

text: to

text: Theorem

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Fig. 3. The left system is in the initial state, while the right system is on the half of its way to ω with 6 Grover’s iterations. Fig. 1. The First Grover Iteration. Fig. 4. Us6 applied. Fig. 2. The Second Grover Iteration. computing model still distinguish data (quantum system state) from a program (sequence of unitary transforms in the system Fig. 5. Us3 applied. state space). Some of these unitary tranforms have the natural | (cid:105) mapping on the system states. For example, the state s | (cid:105) (cid:104) |− Grover’s iterations must be close to 12. Let’s suppose that we deﬁnes the transform U = 2 s s 1 in the previous section. s already have performed a half of these 12 iterations in one If we assume, that the state of one quantum system can be system, while in another system we’ve prepared the initial used as a reﬂection tranform in another quantum system, then | (cid:105) state s (ﬁgure ). we can introduce a much simplier and effective algorithm for | (cid:105) If the vector s can be used as the operator U = the unsorted database search. | (cid:105) (cid:104) | − 6 | (cid:105)s6 2 s s 1 in the left system with the initial state s , then Following Grover, we will denote: 6 6 we need only one iteration to get close to ω instead of the { } → remained 6 Grover’s iterations (ﬁgure ). f : 0, 1 n 0, 1, | (cid:105) Again, the vector s itself can be constructed from the | (cid:105) | (cid:105) → | (cid:105) | ⊕ (cid:105) | (cid:105) 6 U : x y x y f(x) , vector s with the same process, thus omitting 3 Grover’s ω 3 | (cid:105) | (cid:105) iterations (ﬁgure ). Continuously applying this trick we can re- s = H 0 n . duce the number of all Grover’s iterations to T = lg T . new grov We still consider the case of searching of the special Each such reﬂection divides the number of nesessary Grover’s input ω among all n-bit strings. The number of Grover’s iterations by 2. iterations needed to get the result with h√igh probability after This means that for solving the unsorted database search measurement is estimated by T = π 2n . For example, if problem we need to: grov 4 | (cid:105) n equals to 8 (each input is one byte), then the number of 1) perform one Grover’s iteration to get vector s . 1 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine##

text: Fig.

text: The

text: left

text: system

text: is

text: in

text: the

text: initial

text: state,

text: while

text: the

text: right

text: system

text: is

text: on

text: the

text: half

text: of

text: its

text: way

text: to

text: ω

text: with

text: Grover’s

text: iterations.

text: Fig.

text: The

text: First

text: Grover

text: Iteration.

text: Fig.

text: applied.

text: Fig.

text: The

text: Second

text: Grover

text: Iteration.

text: computing

text: model

text: still

text: distinguish

text: data

text: (quantum

text: system

text: state)

text: from

text: a

text: program

text: (sequence

text: of

text: unitary

text: transforms

text: in

text: the

text: system

text: Fig.

text: applied.

text: state

text: space).

text: Some

text: of

text: these

text: unitary

text: tranforms

text: have

text: the

text: natural

text: mapping

text: on

text: the

text: system

text: states.

text: For

text: example,

text: the

text: state

text: s

text: Grover’s

text: iterations

text: must

text: be

text: close

text: to

text: Let’s

text: suppose

text: that

text: we

text: deﬁnes

text: the

text: transform

text: U

text: s

text: s

text: in

text: the

text: previous

text: section.

text: s

text: already

text: have

text: performed

text: a

text: half

text: of

text: these

text: iterations

text: in

text: one

text: If

text: we

text: assume,

text: that

text: the

text: state

text: of

text: one

text: quantum

text: system

text: can

text: be

text: system,

text: while

text: in

text: another

text: system

text: we’ve

text: prepared

text: the

text: initial

text: used

text: as

text: a

text: reﬂection

text: tranform

text: in

text: another

text: quantum

text: system,

text: then

text: state

text: s

text: (ﬁgure

text: we

text: can

text: introduce

text: a

text: much

text: simplier

text: and

text: effective

text: algorithm

text: for

text: If

text: the

text: vector

text: s

text: can

text: be

text: used

text: as

text: the

text: operator

text: U

text: the

text: unsorted

text: database

text: search.

text: s

text: s

text: in

text: the

text: left

text: system

text: with

text: the

text: initial

text: state

text: s

text: then

text: Following

text: Grover,

text: we

text: will

text: denote:

text: we

text: need

text: only

text: one

text: iteration

text: to

text: get

text: close

text: to

text: ω

text: instead

text: of

text: the

text: remained

text: Grover’s

text: iterations

text: (ﬁgure

text: f

text: n

text: Again,

text: the

text: vector

text: s

text: itself

text: can

text: be

text: constructed

text: from

text: the

text: U

text: x

text: y

text: x

text: y

text: f(x)

text: vector

text: s

text: with

text: the

text: same

text: process,

text: thus

text: omitting

text: Grover’s

text: ω

text: iterations

text: (ﬁgure

text: Continuously

text: applying

text: this

text: trick

text: we

text: can

text: re-

text: s

text: H

text: n

text: duce

text: the

text: number

text: of

text: all

text: Grover’s

text: iterations

text: to

text: T

text: lg

text: T

text: new

text: grov

text: We

text: still

text: consider

text: the

text: case

text: of

text: searching

text: of

text: the

text: special

text: Each

text: such

text: reﬂection

text: divides

text: the

text: number

text: of

text: nesessary

text: Grover’s

text: input

text: ω

text: among

text: all

text: n-bit

text: strings.

text: The

text: number

text: of

text: Grover’s

text: iterations

text: by

text: iterations

text: needed

text: to

text: get

text: the

text: result

text: with

text: h√igh

text: probability

text: after

text: This

text: means

text: that

text: for

text: solving

text: the

text: unsorted

text: database

text: search

text: measurement

text: is

text: estimated

text: by

text: T

text: π

text: For

text: example,

text: if

text: problem

text: we

text: need

text: to:

text: grov

text: n

text: equals

text: to

text: (each

text: input

text: is

text: one

text: byte),

text: then

text: the

text: number

text: of

text: perform

text: one

text: Grover’s

text: iteration

text: to

text: get

text: vector

text: s

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##


text: | (cid:105) 2) prepare the state s on another system. 3) apply the vector from the ﬁrst system as a reﬂection to the second system. 4) repeat lg T times the steps 2 - 3 . grov The implementation of U operator, which depends on some | (cid:105) si quantum state s and acts on another quantum system is an i open question in the scope of this work. IV. CONCLUSION The proposed quantum algorithm allows us to solve the unsorted database search problem exponentialy faster than that described by Grover. However, the assumption of possibility of applying states as operators to other systems doesn’t corre- spond to the classical quantum computation model, developed to these days. Note that with the new algorithm we need only one call to the U oracle to get the direction. After that all the remained ω iterations do not call the oracle directly. To implement the new algorithm we need only two quantum systems, which will change their roles on each iteration. The ”algorithm” system (which is used as an operator) on the next iteration | (cid:105) must prepare the initial state s and become a ”data” system and vice versa. REFERENCES [1] D. Deutsch, The Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London A 400: 97. 1985 [2] D. Deutsch, R. Jozsa Rapid solutions of problems by quantum computa- tion. Proceedings of the Royal Society of London A 439: 553. 1992. [3] E. Bernstein, U. Vazirani Quantum complexity theory. Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC ’93), pp. 11–20. 1993. [4] D. R. Simon, On the power of quantum computation. Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on: 116–123. 1994. [5] P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the 35th IEEESymposium on Foundations of Computer Science. pp. 124 – 134. 1994. [6] L. K. Grover, A fast quantum mechanical algorithm for database search. Proceedings of the Twenty-Eighth Annual ACMSymposium on Theory of Computing. pp. 212 – 219. 1996. [7] J. von Neumann, First Draft of a Report on the EDVAC. 1996.

label: list

text: prepare

text: the

text: state

text: s

text: on

text: another

text: system.

text: apply

text: the

text: vector

text: from

text: the

text: ﬁrst

text: system

text: as

text: a

text: reﬂection

text: to

text: the

text: second

text: system.

text: repeat

text: lg

text: T

text: times

text: the

text: steps

text: grov

text: The

text: implementation

text: of

text: U

text: operator,

text: which

text: depends

text: on

text: some

text: si

text: quantum

text: state

text: s

text: and

text: acts

text: on

text: another

text: quantum

text: system

text: is

text: an

text: i

text: open

text: question

text: in

text: the

text: scope

text: of

text: this

text: work.

text: IV.

label: section

text: CONCLUSION

text: The

text: proposed

text: quantum

text: algorithm

text: allows

text: us

text: to

text: solve

text: the

text: unsorted

text: database

text: search

text: problem

text: exponentialy

text: faster

text: than

text: that

text: described

text: by

text: Grover.

text: However,

text: the

text: assumption

text: of

text: possibility

text: of

text: applying

text: states

text: as

text: operators

text: to

text: other

text: systems

text: doesn’t

text: corre-

text: spond

text: to

text: the

text: classical

text: quantum

text: computation

text: model,

text: developed

text: to

text: these

text: days.

text: Note

text: that

text: with

text: the

text: new

text: algorithm

text: we

text: need

text: only

text: one

text: call

text: to

text: the

text: U

text: oracle

text: to

text: get

text: the

text: direction.

text: After

text: that

text: all

text: the

text: remained

text: ω

text: iterations

text: do

text: not

text: call

text: the

text: oracle

text: directly.

text: To

text: implement

text: the

text: new

text: algorithm

text: we

text: need

text: only

text: two

text: quantum

text: systems,

text: which

text: will

text: change

text: their

text: roles

text: on

text: each

text: iteration.

text: The

text: ”algorithm”

text: system

text: (which

text: is

text: used

text: as

text: an

text: operator)

text: on

text: the

text: next

text: iteration

text: must

text: prepare

text: the

text: initial

text: state

text: s

text: and

text: become

text: a

text: ”data”

text: system

text: and

text: vice

text: versa.

text: REFERENCES

text: D.

text: Deutsch,

text: The

text: Church-Turing

text: principle

text: and

text: the

text: universal

text: quantum

text: computer.

text: Proceedings

text: of

text: the

text: Royal

text: Society

text: of

text: London

text: A

text: D.

text: Deutsch,

text: R.

text: Jozsa

text: Rapid

text: solutions

text: of

text: problems

text: by

text: quantum

text: computa-

text: tion.

text: Proceedings

text: of

text: the

text: Royal

text: Society

text: of

text: London

text: A

text: E.

text: Bernstein,

text: U.

text: Vazirani

text: Quantum

text: complexity

text: theory.

text: Proceedings

text: of

text: the

text: Twenty-Fifth

text: Annual

text: ACM

text: Symposium

text: on

text: Theory

text: of

text: Computing

text: (STOC

text: pp.

text: D.

text: R.

text: Simon,

text: On

text: the

text: power

text: of

text: quantum

text: computation.

text: Foundations

text: of

text: Computer

text: Science,

text: Proceedings.,

text: Annual

text: Symposium

text: on:

text: P.

text: W.

text: Shor,

text: Algorithms

text: for

text: quantum

text: computation:

text: discrete

text: logarithms

text: and

text: factoring.

text: Proceedings

text: of

text: the

text: IEEESymposium

text: on

text: Foundations

text: of

text: Computer

text: Science.

text: pp.

text: L.

text: K.

text: Grover,

text: A

text: fast

text: quantum

text: mechanical

text: algorithm

text: for

text: database

text: search.

text: Proceedings

text: of

text: the

text: Twenty-Eighth

text: Annual

text: ACMSymposium

text: on

text: Theory

text: of

text: Computing.

text: pp.

text: J.

text: von

text: Neumann,

text: First

text: Draft

text: of

text: a

text: Report

text: on

text: the

text: EDVAC.


text: MANUSCRIPT 11 long (possibly inﬁnite) support. We construct a smooth dual window h supported I , the support set of g and compare our g result to that provided by the truncation method. Experiment 1 - Optimizing TF concentration: In this experiment, we simultaneously optimize TF concentration with regards to the previously introduced measures. This is either achieved by a single prior on the TF representation of the dual } } } } }∇ } p| |q window h ( x , x ), or by applying the time and frequency versions of one prior, with equal weights ( x 2, var x , p| | q S0 S0,w 2 var x 2 ), i.e. p q ` pF q arg min f x f x . PC XC x dual supp The time step γ of the algorithm has been tuned experimentally for each prior, to yield good convergence speed and precision. { “ “ For this experiment, we have chosen a Tukey window with a transition area ratio6 of 3 5 (see Fig. 8), with L 240, a 50 “ “ g and M 300. The support of the dual window candidates was restricted to L 600. h Fig. 8. The analysis Tukey window and its magnitude frequency response (in dB). Fig. 9 shows time and frequency representations, as well as the ambiguity function7 of the results. We see Fig. 9(a)(b)(c) that all the criteria provide (visually) nicely concentrated dual Gabor windows, improved over the canonical dual. In particular, we see that the gradient and energy variance optimal windows are very similar around the origin, whereas the latter shows worse decay. The variance induces the best concentration of large values in an almost rectangular TF area, but similar to the energy variance, no good decay is achieved. Both S and weighted S priors perform very well, but the weight induces a more 0 0 symmetric TF concentration and slightly better decay. Note that, while the shape of this experiment’s results is quite characteristic, their quality cannot be representative for any arbitrary setup. In fact the results are highly dependent on the quality of the original Gabor frame, its redundancy and the choice of support constraint. As expected, the optimization effect is smaller, the better the starting setup is. For additional experiments with other starting windows and/or without support constraint, we refer to the webpage. To further emphasize the similarities and differences between the window functions and to assess their quality, we computed for all the results every concentration measure discussed in Sec. , see Table II. Besides demonstrating nicely that the various solutions actually provide the best result in their respective criteria, the table underlines the similarity of gradient and energy variance optimization. In total, except for the canonical dual and S -norm solution, all results are reasonably close. The 0 different shape of the S -norm solution is easily explained by the fact that it is the only measure that does not penalize 0 high-energy contributions away from the origin. Furthermore, in Table III, the following classical measures for window quality ´ are presented: 3 dB width (time), main lobe width (frequency), side lobe attenuation (frequency, in dB) and side lobe decay (in dB). Please note that the lack of an underlying continuous function for the dual windows prevents us from determining the side lobe decay rate from the degree of smoothness of the window. Therefore, as a rough approximation, we compute the ratio between the largest sidelobe and the largest of the ﬁnal 3 side lobes below the Nyquist frequency instead. Notably, the variance optimization concentrates the main energy contribution in the smallest TF area as indicated in the third column, while the gradient optimization provides arguably the most balanced solution and the best decay properties, followed by the considerably more expensive S and weighted S solutions. 0 0 Experiment 2 - Controlling the time-frequency trade-off: It is well known that no function can be arbitrarily concentrated in both the time and the frequency domain simultaneously. When choosing a dual window to a given Gabor frame the concentration is further limited by the duality conditions, the shape { and the quality of the given frame. Oversimpliﬁed, a badly conditioned Gabor frame (with large frame bound ratio B A), admits only badly concentrated duals. However, even if the canonical dual window is well concentrated overall, applications might beneﬁt from the improvement of time concentration versus frequency concentration and vice-versa. To see this, just recall that the TF shape of the synthesis window limits the precision of TF processing. The following experiment demonstrates the surprising ﬂexibility that the set of dual windows allows when choosing the “ “ “ appropriate TF concentration trade-off. The system parameters are the same as in Exp. 1: L 240, a 50, M 300 and g P r s p q “ P r´p ´ q{ p ´ q{ s p q “ ` p p ´ ` q{ q 6ThPerT´uk{ey w´ipndo´w wq{iths trapnsqit“ion are`a ratio r p p0,1`is ´giveqn{ byqg t P 1rpfo´r t q{ 1{ s r 2, 1 r 2 , g t 0.5 0.5cos π 2t r 1 2r for t 1 2, 1 r 2 , g t 0.5 0.5cos π 2t r 1 2r for t 1 r 2,1 2 and zero else. 7In CL, the ambiguity function is the STFT of a function with regards to itself: G f. f,1,L ##LTFigure## ##LTFigure##

text: MANUSCRIPT

text: long

text: (possibly

text: inﬁnite)

text: support.

text: We

text: construct

text: a

text: smooth

text: dual

text: window

text: h

text: supported

text: I

text: the

text: support

text: set

text: of

text: g

text: and

text: compare

text: our

text: g

text: result

text: to

text: that

text: provided

text: by

text: the

text: truncation

text: method.

text: Experiment

text: Optimizing

text: TF

text: concentration:

text: In

text: this

text: experiment,

text: we

text: simultaneously

text: optimize

text: TF

text: concentration

text: with

text: regards

text: to

text: the

text: previously

text: introduced

text: measures.

text: This

text: is

text: either

text: achieved

text: by

text: a

text: single

text: prior

text: on

text: the

text: TF

text: representation

text: of

text: the

text: dual

text: p|

text: |q

text: window

text: h

text: x

text: x

text: or

text: by

text: applying

text: the

text: time

text: and

text: frequency

text: versions

text: of

text: one

text: prior,

text: with

text: equal

text: weights

text: x

text: var

text: x

text: p|

text: q

text: var

text: x

text: i.e.

text: p

text: q

text: pF

text: q

text: arg

text: min

text: f

text: x

text: f

text: x

text: PC

text: XC

text: x

text: dual

text: supp

text: The

text: time

text: step

text: γ

text: of

text: the

text: algorithm

text: has

text: been

text: tuned

text: experimentally

text: for

text: each

text: prior,

text: to

text: yield

text: good

text: convergence

text: speed

text: and

text: precision.

text: For

text: this

text: experiment,

text: we

text: have

text: chosen

text: a

text: Tukey

text: window

text: with

text: a

text: transition

text: area

text: of

text: (see

text: Fig.

text: with

text: L

text: a

text: g

text: and

text: M

text: The

text: support

text: of

text: the

text: dual

text: window

text: candidates

text: was

text: restricted

text: to

text: L

text: h

text: Fig.

text: The

text: analysis

text: Tukey

text: window

text: and

text: its

text: magnitude

text: frequency

text: response

text: (in

text: dB).

text: Fig.

text: shows

text: time

text: and

text: frequency

text: representations,

text: as

text: well

text: as

text: the

text: ambiguity

text: of

text: the

text: results.

text: We

text: see

text: Fig.

text: that

text: all

text: the

text: criteria

text: provide

text: (visually)

text: nicely

text: concentrated

text: dual

text: Gabor

text: windows,

text: improved

text: over

text: the

text: canonical

text: dual.

text: In

text: particular,

text: we

text: see

text: that

text: the

text: gradient

text: and

text: energy

text: variance

text: optimal

text: windows

text: are

text: very

text: similar

text: around

text: the

text: origin,

text: whereas

text: the

text: latter

text: shows

text: worse

text: decay.

text: The

text: variance

text: induces

text: the

text: best

text: concentration

text: of

text: large

text: values

text: in

text: an

text: almost

text: rectangular

text: TF

text: area,

text: but

text: similar

text: to

text: the

text: energy

text: variance,

text: no

text: good

text: decay

text: is

text: achieved.

text: Both

text: S

text: and

text: weighted

text: S

text: priors

text: perform

text: very

text: well,

text: but

text: the

text: weight

text: induces

text: a

text: more

text: symmetric

text: TF

text: concentration

text: and

text: slightly

text: better

text: decay.

text: Note

text: that,

text: while

text: the

text: shape

text: of

text: this

text: experiment’s

text: results

text: is

text: quite

text: characteristic,

text: their

text: quality

text: cannot

text: be

text: representative

text: for

text: any

text: arbitrary

text: setup.

text: In

text: fact

text: the

text: results

text: are

text: highly

text: dependent

text: on

text: the

text: quality

text: of

text: the

text: original

text: Gabor

text: frame,

text: its

text: redundancy

text: and

text: the

text: choice

text: of

text: support

text: constraint.

text: As

text: expected,

text: the

text: optimization

text: effect

text: is

text: smaller,

text: the

text: better

text: the

text: starting

text: setup

text: is.

text: For

text: additional

text: experiments

text: with

text: other

text: starting

text: windows

text: and/or

text: without

text: support

text: constraint,

text: we

text: refer

text: to

text: the

text: webpage.

text: To

text: further

text: emphasize

text: the

text: similarities

text: and

text: differences

text: between

text: the

text: window

text: functions

text: and

text: to

text: assess

text: their

text: quality,

text: we

text: computed

text: for

text: all

text: the

text: results

text: every

text: concentration

text: measure

text: discussed

text: in

text: Sec.

text: see

text: Table

text: II.

text: Besides

text: demonstrating

text: nicely

text: that

text: the

text: various

text: solutions

text: actually

text: provide

text: the

text: best

text: result

text: in

text: their

text: respective

text: criteria,

text: the

text: table

text: underlines

text: the

text: similarity

text: of

text: gradient

text: and

text: energy

text: variance

text: optimization.

text: In

text: total,

text: except

text: for

text: the

text: canonical

text: dual

text: and

text: S

text: -norm

text: solution,

text: all

text: results

text: are

text: reasonably

text: close.

text: The

text: different

text: shape

text: of

text: the

text: S

text: -norm

text: solution

text: is

text: easily

text: explained

text: by

text: the

text: fact

text: that

text: it

text: is

text: the

text: only

text: measure

text: that

text: does

text: not

text: penalize

text: high-energy

text: contributions

text: away

text: from

text: the

text: origin.

text: Furthermore,

text: in

text: Table

text: III,

text: the

text: following

text: classical

text: measures

text: for

text: window

text: quality

text: are

text: presented:

text: dB

text: width

text: (time),

text: main

text: lobe

text: width

text: (frequency),

text: side

text: lobe

text: attenuation

text: (frequency,

text: in

text: dB)

text: and

text: side

text: lobe

text: decay

text: (in

text: dB).

text: Please

text: note

text: that

text: the

text: lack

text: of

text: an

text: underlying

text: continuous

text: function

text: for

text: the

text: dual

text: windows

text: prevents

text: us

text: from

text: determining

text: the

text: side

text: lobe

text: decay

text: rate

text: from

text: the

text: degree

text: of

text: smoothness

text: of

text: the

text: window.

text: Therefore,

text: as

text: a

text: rough

text: approximation,

text: we

text: compute

text: the

text: ratio

text: between

text: the

text: largest

text: sidelobe

text: and

text: the

text: largest

text: of

text: the

text: ﬁnal

text: side

text: lobes

text: below

text: the

text: Nyquist

text: frequency

text: instead.

text: Notably,

text: the

text: variance

text: optimization

text: concentrates

text: the

text: main

text: energy

text: contribution

text: in

text: the

text: smallest

text: TF

text: area

text: as

text: indicated

text: in

text: the

text: third

text: column,

text: while

text: the

text: gradient

text: optimization

text: provides

text: arguably

text: the

text: most

text: balanced

text: solution

text: and

text: the

text: best

text: decay

text: properties,

text: followed

text: by

text: the

text: considerably

text: more

text: expensive

text: S

text: and

text: weighted

text: S

text: solutions.

text: Experiment

text: Controlling

text: the

text: time-frequency

text: trade-off:

text: It

text: is

text: well

text: known

text: that

text: no

text: function

text: can

text: be

text: arbitrarily

text: concentrated

text: in

text: both

text: the

text: time

text: and

text: the

text: frequency

text: domain

text: simultaneously.

text: When

text: choosing

text: a

text: dual

text: window

text: to

text: a

text: given

text: Gabor

text: frame

text: the

text: concentration

text: is

text: further

text: limited

text: by

text: the

text: duality

text: conditions,

text: the

text: shape

text: and

text: the

text: quality

text: of

text: the

text: given

text: frame.

text: Oversimpliﬁed,

text: a

text: badly

text: conditioned

text: Gabor

text: frame

text: (with

text: large

text: frame

text: bound

text: ratio

text: B

text: A),

text: admits

text: only

text: badly

text: concentrated

text: duals.

text: However,

text: even

text: if

text: the

text: canonical

text: dual

text: window

text: is

text: well

text: concentrated

text: overall,

text: applications

text: might

text: beneﬁt

text: from

text: the

text: improvement

text: of

text: time

text: concentration

text: versus

text: frequency

text: concentration

text: and

text: vice-versa.

text: To

text: see

text: this,

text: just

text: recall

text: that

text: the

text: TF

text: shape

text: of

text: the

text: synthesis

text: window

text: limits

text: the

text: precision

text: of

text: TF

text: processing.

text: The

text: following

text: experiment

text: demonstrates

text: the

text: surprising

text: ﬂexibility

text: that

text: the

text: set

text: of

text: dual

text: windows

text: allows

text: when

text: choosing

text: the

text: appropriate

text: TF

text: concentration

text: trade-off.

text: The

text: system

text: parameters

text: are

text: the

text: same

text: as

text: in

text: Exp.

text: L

text: a

text: M

text: and

text: g

text: P

text: r

text: s

text: p

text: q

text: P

text: r´p

text: q{

text: p

text: q{

text: s

text: p

text: q

text: p

text: p

text: q{

text: q

text: w´ipndo´w

text: wq{iths

text: trapnsqit“ion

text: are`a

text: ratio

text: r

text: p

text: ´giveqn{

text: byqg

text: t

text: P

text: t

text: q{

text: s

text: r

text: r

text: g

text: t

text: π

text: r

text: for

text: t

text: r

text: g

text: t

text: π

text: r

text: for

text: t

text: r

text: and

text: zero

text: else.

text: CL,

text: the

text: ambiguity

text: function

text: is

text: the

text: STFT

text: of

text: a

text: function

text: with

text: regards

text: to

text: itself:

text: G

text: f.

text: ##LTFigure##

text: ##LTFigure##


text: MANUSCRIPT 19 [48] S. Samadi, M. O. Ahmad, and M. N. S. Swamy. Characterization of nonuniform perfect-reconstruction ﬁlterbanks using unit-step signal. IEEE Transactions on Signal Processing, 52(9):2490–2499, 2004. [49] S. Setzer, G. Steidl, and T. Teuber. Deblurring Poissonian images by split bregman techniques. Journal of Visual Communication and Image Representation, 21(3):193 – 199, 2010. [50] P. L. Søndergaard. Gabor frames by Sampling and Periodization. Adv. Comput. Math., 27(4):355 –373, 2007. [51] P. L. Søndergaard, B. Torre´sani, and P. Balazs. The Linear Time Frequency Analysis Toolbox. International Journal of Wavelets, Multiresolution Analysis and Information Processing, 10(4), 2012. [52] D. T. Stoeva and P. Balazs. Invertibility of multipliers. Applied and Computational Harmonic Analysis, 33(2):292–299, 2012. [53] T. Strohmer. Numerical algorithms for discrete Gabor expansions. In Feichtinger and Strohmer [26], chapter 8, pages 267–294. [54] M. Vetterli. Filter banks allowing perfect reconstruction. Signal Process., 10:219–244, 1986. [55] J. Wexler and S. Raz. Discrete Gabor expansions. Signal Processing, 21(3):207–220, Nov. 1990. [56] C. Wiesmeyr, N. Holighaus, and P. Sondergaard. Efﬁcient algorithms for discrete Gabor transforms on a nonseparable lattice. IEEE Trans. Signal Process., 61(20):5131 – 5142, 2013. N. Perraudin studied electrical engineering at EPFL (”Ecole polytechnique fe´de´ral de Lausanne”) where he specialized himself in signal processing. After his degree he spent six months as research assistant at the Acoustic Research Institute at the Austrian Academy of Science. Then, in 2013, he started a PHD at LTS2 (laboratoire de traitement du signal) at EPFL. His current research focuses on three different domains: spectral graph theory, convex optimization and Gabor analysis. He is the founder and the maintainer of open-source project called the UNLocBoX (A matlab convex optimization toolbox): http://unlocbox.sourceforge.net/. N. Holighaus studied mathematics and theoretical computer sciences at Justus–Liebig–University, Gießen, Germany. In 2013 he received his Ph.D. degree in mathematics at the University of Vienna, where he worked from 2010 to 2012 as research assistant at the Numerical Harmonic Analysis Group (NuHAG), Faculty of Mathematics. Since August 2012 he works as a research assistant at the Acoustic Research Institute at the Austrian Academy of Sciences. His research interests include applied frame theory and time-frequency analysis, adaptive time-frequency techniques and signal processing. P. Søndergaard studied applied time-frequency analysis at the Technical University of Denmark. He defended his Ph.D. thesis on ”Finite Discrete Gabor Analysis” in 2007. From 2007 - 2012 he worked at the Centre for Applied Hearing Research in Denmark, working with auditory modeling and accurate signal modiﬁcations. From 2012 to 2013 he lead the ’Mathematics and Signal Processing in Acoustics’ group at the Acoustic Research Institute (ARI) at the Austrian Academy of Sciences. He is currently employed at Oticon R&D since August 2013. He is the creator of the two open-source software projects, The Large Time Frequency Toolbox, LTFAT: http://ltfat.sourceforge.net/ and the Auditory Modeling Toolbox, AMToolbox: http://amtoolbox.sourceforge.net/, which are maintained by ARI. P. Balazs (M’01 S’12) received the Ph.D. degree (2005) and the habilitation (2011) degree in mathematics at the University of Vienna, in cooperation with the Numerical Harmonic Analysis Group. He has been a member of the Acoustics Research Institute (ARI) of the Austrian Academy of Sciences since 1999. He also worked at the Laboratoire d’Analyse Topologie et Probabilite´s and the Laboratoire de Me´canique et d’Acoustique, in Marseille, France, from 2003 to 2006 as well as the Unite´ de physique the´orique et de physique mathe´matique (FYMA) from the Universite´ Catholique de Louvain a` Louvain-La-Neuve. He is the founder of the working group ’Mathematics and Acoustical Signal Processing’ at ARI. He has been the director of ARI since 2012. He is interested in time-frequency analysis, Gabor analysis, numerical analysis, frame theory, signal processing, acoustics, and psychoacoustics. ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure##

text: MANUSCRIPT

label: reference

text: S.

text: Samadi,

text: M.

text: O.

text: Ahmad,

text: and

text: M.

text: N.

text: S.

text: Swamy.

text: Characterization

text: of

text: nonuniform

text: perfect-reconstruction

text: ﬁlterbanks

text: using

text: unit-step

text: signal.

text: IEEE

text: Transactions

text: on

text: Signal

text: Processing,

text: S.

text: Setzer,

text: G.

text: Steidl,

text: and

text: T.

text: Teuber.

text: Deblurring

text: Poissonian

text: images

text: by

text: split

text: bregman

text: techniques.

text: Journal

text: of

text: Visual

text: Communication

text: and

text: Image

text: Representation,

text: P.

text: L.

text: Søndergaard.

text: Gabor

text: frames

text: by

text: Sampling

text: and

text: Periodization.

text: Adv.

text: Comput.

text: Math.,

text: P.

text: L.

text: Søndergaard,

text: B.

text: Torre´sani,

text: and

text: P.

text: Balazs.

text: The

text: Linear

text: Time

text: Frequency

text: Analysis

text: Toolbox.

text: International

text: Journal

text: of

text: Wavelets,

text: Multiresolution

text: Analysis

text: and

text: Information

text: Processing,

text: D.

text: T.

text: Stoeva

text: and

text: P.

text: Balazs.

text: Invertibility

text: of

text: multipliers.

text: Applied

text: and

text: Computational

text: Harmonic

text: Analysis,

text: T.

text: Strohmer.

text: Numerical

text: algorithms

text: for

text: discrete

text: Gabor

text: expansions.

text: In

text: Feichtinger

text: and

text: Strohmer

text: chapter

text: pages

text: M.

text: Vetterli.

text: Filter

text: banks

text: allowing

text: perfect

text: reconstruction.

text: Signal

text: Process.,

text: J.

text: Wexler

text: and

text: S.

text: Raz.

text: Discrete

text: Gabor

text: expansions.

text: Signal

text: Processing,

text: Nov.

text: C.

text: Wiesmeyr,

text: N.

text: Holighaus,

text: and

text: P.

text: Sondergaard.

text: Efﬁcient

text: algorithms

text: for

text: discrete

text: Gabor

text: transforms

text: on

text: a

text: nonseparable

text: lattice.

text: IEEE

text: Trans.

text: Signal

text: Process.,

text: N.

text: Perraudin

text: studied

text: electrical

text: engineering

text: at

text: EPFL

text: (”Ecole

text: polytechnique

text: fe´de´ral

text: de

text: Lausanne”)

text: where

text: he

text: specialized

text: himself

text: in

text: signal

text: processing.

text: After

text: his

text: degree

text: he

text: spent

text: six

text: months

text: as

text: research

text: assistant

text: at

text: the

text: Acoustic

text: Research

text: Institute

text: at

text: the

text: Austrian

text: Academy

text: of

text: Science.

text: Then,

text: in

text: he

text: started

text: a

text: PHD

text: at

text: (laboratoire

text: de

text: traitement

text: du

text: signal)

text: at

text: EPFL.

text: His

text: current

text: research

text: focuses

text: on

text: three

text: different

text: domains:

text: spectral

text: graph

text: theory,

text: convex

text: optimization

text: and

text: Gabor

text: analysis.

text: He

text: is

text: the

text: founder

text: and

text: the

text: maintainer

text: of

text: open-source

text: project

text: called

text: the

text: UNLocBoX

text: (A

text: matlab

text: convex

text: optimization

text: toolbox):

text: N.

text: Holighaus

text: studied

text: mathematics

text: and

text: theoretical

text: computer

text: sciences

text: at

text: Justus–Liebig–University,

text: Gießen,

text: Germany.

text: In

text: he

text: received

text: his

text: Ph.D.

text: degree

text: in

text: mathematics

text: at

text: the

text: University

text: of

text: Vienna,

text: where

text: he

text: worked

text: from

text: to

text: as

text: research

text: assistant

text: at

text: the

text: Numerical

text: Harmonic

text: Analysis

text: Group

text: (NuHAG),

text: Faculty

text: of

text: Mathematics.

text: Since

text: August

text: he

text: works

text: as

text: a

text: research

text: assistant

text: at

text: the

text: Acoustic

text: Research

text: Institute

text: at

text: the

text: Austrian

text: Academy

text: of

text: Sciences.

text: His

text: research

text: interests

text: include

text: applied

text: frame

text: theory

text: and

text: time-frequency

text: analysis,

text: adaptive

text: time-frequency

text: techniques

text: and

text: signal

text: processing.

text: P.

text: Søndergaard

text: studied

text: applied

text: time-frequency

text: analysis

text: at

text: the

text: Technical

text: University

text: of

text: Denmark.

text: He

text: defended

text: his

text: Ph.D.

text: thesis

text: on

text: ”Finite

text: Discrete

text: Gabor

text: Analysis”

text: in

text: From

text: he

text: worked

text: at

text: the

text: Centre

text: for

text: Applied

text: Hearing

text: Research

text: in

text: Denmark,

text: working

text: with

text: auditory

text: modeling

text: and

text: accurate

text: signal

text: modiﬁcations.

text: From

text: to

text: he

text: lead

text: the

text: ’Mathematics

text: and

text: Signal

text: Processing

text: in

text: Acoustics’

text: group

text: at

text: the

text: Acoustic

text: Research

text: Institute

text: (ARI)

text: at

text: the

text: Austrian

text: Academy

text: of

text: Sciences.

text: He

text: is

text: currently

text: employed

text: at

text: Oticon

text: R&D

text: since

text: August

text: He

text: is

text: the

text: creator

text: of

text: the

text: two

text: open-source

text: software

text: projects,

text: The

text: Large

text: Time

text: Frequency

text: Toolbox,

text: LTFAT:

text: and

text: the

text: Auditory

text: Modeling

text: Toolbox,

text: AMToolbox:

text: which

text: are

text: maintained

text: by

text: ARI.

text: P.

text: Balazs

text: received

text: the

text: Ph.D.

text: degree

text: and

text: the

text: habilitation

text: degree

text: in

text: mathematics

text: at

text: the

text: University

text: of

text: Vienna,

text: in

text: cooperation

text: with

text: the

text: Numerical

text: Harmonic

text: Analysis

text: Group.

text: He

text: has

text: been

text: a

text: member

text: of

text: the

text: Acoustics

text: Research

text: Institute

text: (ARI)

text: of

text: the

text: Austrian

text: Academy

text: of

text: Sciences

text: since

text: He

text: also

text: worked

text: at

text: the

text: Laboratoire

text: d’Analyse

text: Topologie

text: et

text: Probabilite´s

text: and

text: the

text: Laboratoire

text: de

text: Me´canique

text: et

text: d’Acoustique,

text: in

text: Marseille,

text: France,

text: from

text: to

text: as

text: well

text: as

text: the

text: Unite´

text: de

text: physique

text: the´orique

text: et

text: de

text: physique

text: mathe´matique

text: (FYMA)

text: from

text: the

text: Universite´

text: Catholique

text: de

text: Louvain

text: a`

text: Louvain-La-Neuve.

text: He

text: is

text: the

text: founder

text: of

text: the

text: working

text: group

text: ’Mathematics

text: and

text: Acoustical

text: Signal

text: Processing’

text: at

text: ARI.

text: He

text: has

text: been

text: the

text: director

text: of

text: ARI

text: since

text: He

text: is

text: interested

text: in

text: time-frequency

text: analysis,

text: Gabor

text: analysis,

text: numerical

text: analysis,

text: frame

text: theory,

text: signal

text: processing,

text: acoustics,

text: and

text: psychoacoustics.

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##


text: Accepted by ApJ (2014) Chemo-dynamical deuterium fractionation in the early solar nebula: The origin of water on Earth and in asteroids and comets. T. Albertsson, D. Semenov and Th. Henning Max-Planck-Institut für Astronomie, Königstuhl 17, 69117 Heidelberg, Germany albertsson@mpia.de ABSTRACT Formation and evolution of water in the Solar System and the origin of water on Earth constitute one of the most interesting questions in astronomy. The prevailing hypothesis for the origin of water on Earth is by delivery through water-rich small Solar system bodies. In this paper, the isotopic and chemical evolution of water during the early history of the solar nebula, before the onset of planetesimal formation, is studied. A gas-grain chemical model that includes multiply-deuterated species and nuclear spin-states is combined with a steady- state solar nebula model. To calculate initial abundances, we simulated 1 Myr of evolution of a cold and dark TMC1-like prestellar core. Two time-dependent chemical models of the solar nebula are calculated over 1 Myr: (1) a laminar model and (2) a model with 2D turbulent mixing. We ﬁnd that the radial outward increase of the H O D/H ratio is shallower in the chemo- 2 dynamical nebular model compared to the laminar model. This is related to more efﬁcient de- fractionation of HDO via rapid gas-phase processes, as the 2D mixing model allows the water ice to be transported either inward and thermally evaporated or upward and photodesorbed. (cid:46) The laminar model shows the Earth water D/H ratio at r 2.5 AU, while for the 2D chemo- (cid:46) dynamical model this zone is larger, r 9 AU. Similarly, the water D/H ratios representative ∼ × ∼ ∼ of the Oort-family comets, 2.5 − 10 10−4, are achieved within 2 − 6 AU and 2 − 20 AU in the laminar and the 2D model, respectively. We ﬁnd that with regards to the water isotopic composition and the origin of the comets, the mixing model seems to be favored over the laminar model. Subject headings: astrochemistry - deuterium - molecular processes - water - methods: numer- ical, molecules, abundances, fractionation - protoplanetary disks 1. Introduction Water is one of the most abundant molecules detected in interstellar space, found throughout all stages of the stellar evolution, from prestellar cores till protoplanetary disks. The ultimate role of liquid water for

text: Accepted

text: by

text: ApJ

text: Chemo-dynamical

label: title

text: deuterium

text: fractionation

text: in

text: the

text: early

text: solar

text: nebula:

text: The

text: origin

text: of

text: water

text: on

text: Earth

text: and

text: in

text: asteroids

text: and

text: comets.

text: T.

label: author

text: Albertsson,

text: D.

text: Semenov

text: and

text: Th.

text: Henning

text: Max-Planck-Institut

text: für

text: Astronomie,

text: Königstuhl

text: Heidelberg,

text: Germany

text: albertsson@mpia.de

label: footer

font: IEPXSR+NimbusMonL-Regu

text: ABSTRACT

text: Formation

label: abstract

text: and

text: evolution

text: of

text: water

text: in

text: the

text: Solar

text: System

text: and

text: the

text: origin

text: of

text: water

text: on

text: Earth

text: constitute

text: one

text: of

text: the

text: most

text: interesting

text: questions

text: in

text: astronomy.

text: The

text: prevailing

text: hypothesis

text: for

text: the

text: origin

text: of

text: water

text: on

text: Earth

text: is

text: by

text: delivery

text: through

text: water-rich

text: small

text: Solar

text: system

text: bodies.

text: In

text: this

text: paper,

text: the

text: isotopic

text: and

text: chemical

text: evolution

text: of

text: water

text: during

text: the

text: early

text: history

text: of

text: the

text: solar

text: nebula,

text: before

text: the

text: onset

text: of

text: planetesimal

text: formation,

text: is

text: studied.

text: A

text: gas-grain

text: chemical

text: model

text: that

text: includes

text: multiply-deuterated

text: species

text: and

text: nuclear

text: spin-states

text: is

text: combined

text: with

text: a

text: steady-

text: state

text: solar

text: nebula

text: model.

text: To

text: calculate

text: initial

text: abundances,

text: we

text: simulated

text: Myr

text: of

text: evolution

text: of

text: a

text: cold

text: and

text: dark

text: prestellar

text: core.

text: Two

text: time-dependent

text: chemical

text: models

text: of

text: the

text: solar

text: nebula

text: are

text: calculated

text: over

text: Myr:

text: a

text: laminar

text: model

text: and

text: a

text: model

text: with

text: turbulent

text: mixing.

text: We

text: ﬁnd

text: that

text: the

text: radial

text: outward

text: increase

text: of

text: the

text: H

text: O

text: D/H

text: ratio

text: is

text: shallower

text: in

text: the

text: chemo-

text: dynamical

text: nebular

text: model

text: compared

text: to

text: the

text: laminar

text: model.

text: This

text: is

text: related

text: to

text: more

text: efﬁcient

text: de-

text: fractionation

text: of

text: HDO

text: via

text: rapid

text: gas-phase

text: processes,

text: as

text: the

text: mixing

text: model

text: allows

text: the

text: water

text: ice

text: to

text: be

text: transported

text: either

text: inward

text: and

text: thermally

text: evaporated

text: or

text: upward

text: and

text: photodesorbed.

text: The

text: laminar

text: model

text: shows

text: the

text: Earth

text: water

text: D/H

text: ratio

text: at

text: r

text: AU,

text: while

text: for

text: the

text: chemo-

text: dynamical

text: model

text: this

text: zone

text: is

text: larger,

text: r

text: AU.

text: Similarly,

text: the

text: water

text: D/H

text: ratios

text: representative

text: of

text: the

text: Oort-family

text: comets,

text: are

text: achieved

text: within

text: AU

text: and

text: AU

text: in

text: the

text: laminar

text: and

text: the

text: model,

text: respectively.

text: We

text: ﬁnd

text: that

text: with

text: regards

text: to

text: the

text: water

text: isotopic

text: composition

text: and

text: the

text: origin

text: of

text: the

text: comets,

text: the

text: mixing

text: model

text: seems

text: to

text: be

text: favored

text: over

text: the

text: laminar

text: model.

text: Subject

text: headings:

text: astrochemistry

text: deuterium

text: molecular

text: processes

text: water

text: methods:

text: numer-

text: ical,

text: molecules,

text: abundances,

text: fractionation

text: protoplanetary

text: disks

text: Introduction

text: Water

text: is

text: one

text: of

text: the

text: most

text: abundant

text: molecules

text: detected

text: in

text: interstellar

text: space,

text: found

text: throughout

text: all

text: stages

text: of

text: the

text: stellar

text: evolution,

text: from

text: prestellar

text: cores

text: till

text: protoplanetary

text: disks.

text: The

text: ultimate

text: role

text: of

text: liquid

text: water

text: for


text: – 17 – ∼ × Similarly, the enhanced water D/H ratios representative of the Oort-family comets, 2.5 − 10 10−4, are ∼ ∼ achieved within 2 − 6 AU and 6 − 30 AU in the laminar and the 2D model, respectively. The character- istically, slightly lower, water D/H ratio that has been found for Jupiter-family comets are found further in ∼ and we ﬁnd their possible formation location 1 − 10 AU in both models. This means that, in our models, we ﬁnd an overlap in the possible formation location for Oort- and Jupiter-family comets. However, with regard to the water isotopic composition and the origin of the comets, the mixing model seems to be favored over the laminar model as the former allows Oort-family comets to have formed in the region of Jupiter’s and Saturn’s present location. This research made use of NASA’s Astrophysics Data System. The research leading to these results has received funding from the European Community’s Seventh Framework Programme [FP7/2007-2013] under grant agreement no. 238258. DS acknowledges support by the Deutsche Forschungsgemeinschaft through SPP 1385: “The ﬁrst ten million years of the Solar System - a planetary materials approach” (SE 1962/1-2). REFERENCES Aikawa, Y., & Herbst, E. 1999, ApJ, 526, 314 Aikawa, Y., et al. 2012, A&A, 538, A57 Akimkin, V., Zhukovska, S., Wiebe, D., Semenov, D., Pavlyuchenkov, Y., Vasyunin, A., Birnstiel, T., & Henning, T. 2013, Astrophys. J, 766, 8 Al-Halabi, A., & van Dishoeck, E. F. 2007, MNRAS, 382, 1648 Albertsson, T., Semenov, D. A., Vasyunin, A. I., Henning, T., & Herbst, E. 2013, ApJS, 207, 27 Alexander, C. M. O., Bowden, R., Fogel, M. L., Howard, K. T., Herd, C. D. K., & Nittler, L. R. 2012, Science, 337, 721 Andrews, S. M., & Williams, J. P. 2007, Astrophys. J, 659, 705 Balsiger, H., Altwegg, K., & Geiss, J. 1995, J. Geophys. Res., 100, 5827 Banzatti, A., et al. 2012, Astrophys. J, 745, 90 Bergin, E. A., et al. 2010, A&A, 521, L33 —. 2013, Nature, 493, 644 Biver, N., et al. 2006, A&A, 449, 1255 Boato, G. 1954, Geochimica et Cosmochimica Acta, 6, 209 Bockelée-Morvan, D., Woodward, C. E., Kelley, M. S., & Wooden, D. H. 2009, Astrophys. J, 696, 1075 Bockelée-Morvan, D., et al. 1998, Icarus, 133, 147

text: Similarly,

text: the

text: enhanced

text: water

text: D/H

text: ratios

text: representative

text: of

text: the

text: Oort-family

text: comets,

font: KWNWQO+StandardSymL

text: are

text: achieved

text: within

text: AU

text: and

text: AU

text: in

text: the

text: laminar

text: and

text: the

text: model,

text: respectively.

text: The

text: character-

text: istically,

text: slightly

text: lower,

text: water

text: D/H

text: ratio

text: that

text: has

text: been

text: found

text: for

text: Jupiter-family

text: comets

text: are

text: found

text: further

text: in

text: and

text: we

text: ﬁnd

text: their

text: possible

text: formation

text: location

text: AU

text: in

text: both

text: models.

text: This

text: means

text: that,

text: in

text: our

text: models,

text: we

text: ﬁnd

text: an

text: overlap

text: in

text: the

text: possible

text: formation

text: location

text: for

text: Oort-

text: and

text: Jupiter-family

text: comets.

text: However,

text: with

text: regard

text: to

text: the

text: water

text: isotopic

text: composition

text: and

text: the

text: origin

text: of

text: the

text: comets,

text: the

text: mixing

text: model

text: seems

text: to

text: be

text: favored

text: over

text: the

text: laminar

text: model

text: as

text: the

text: former

text: allows

text: Oort-family

text: comets

text: to

text: have

text: formed

text: in

text: the

text: region

text: of

text: Jupiter’s

text: and

text: Saturn’s

text: present

text: location.

text: This

text: research

text: made

text: use

text: of

text: NASA’s

text: Astrophysics

text: Data

text: System.

text: The

text: research

text: leading

text: to

text: these

text: results

text: has

text: received

text: funding

text: from

text: the

text: European

text: Community’s

text: Seventh

text: Framework

text: Programme

text: under

text: grant

text: agreement

text: no.

text: DS

text: acknowledges

text: support

text: by

text: the

text: Deutsche

text: Forschungsgemeinschaft

text: through

text: SPP

text: “The

text: ﬁrst

text: ten

text: million

text: years

text: of

text: the

text: Solar

text: System

text: a

text: planetary

text: materials

text: approach”

text: (SE

text: REFERENCES

text: Aikawa,

text: Y.,

text: Herbst,

text: E.

text: ApJ,

text: Aikawa,

text: Y.,

text: et

text: al.

text: A&A,

text: Akimkin,

text: V.,

text: Zhukovska,

text: S.,

text: Wiebe,

text: D.,

text: Semenov,

text: D.,

text: Pavlyuchenkov,

text: Y.,

text: Vasyunin,

text: A.,

text: Birnstiel,

text: T.,

text: Henning,

text: T.

text: Astrophys.

text: J,

text: Al-Halabi,

text: A.,

text: van

text: Dishoeck,

text: E.

text: F.

text: MNRAS,

text: Albertsson,

text: T.,

text: Semenov,

text: D.

text: A.,

text: Vasyunin,

text: A.

text: I.,

text: Henning,

text: T.,

text: Herbst,

text: E.

text: ApJS,

text: Alexander,

text: C.

text: M.

text: O.,

text: Bowden,

text: R.,

text: Fogel,

text: M.

text: L.,

text: Howard,

text: K.

text: T.,

text: Herd,

text: C.

text: D.

text: K.,

text: Nittler,

text: L.

text: R.

text: Science,

text: Andrews,

text: S.

text: M.,

text: Williams,

text: J.

text: P.

text: Astrophys.

text: J,

text: Balsiger,

text: H.,

text: Altwegg,

text: K.,

text: Geiss,

text: J.

text: J.

text: Geophys.

text: Res.,

text: Banzatti,

text: A.,

text: et

text: al.

text: Astrophys.

text: J,

text: Bergin,

text: E.

text: A.,

text: et

text: al.

text: A&A,

text: Nature,

text: Biver,

text: N.,

text: et

text: al.

text: A&A,

text: Boato,

text: G.

text: Geochimica

text: et

text: Cosmochimica

text: Acta,

text: Bockelée-Morvan,

text: D.,

text: Woodward,

text: C.

text: E.,

text: Kelley,

text: M.

text: S.,

text: Wooden,

text: D.

text: H.

text: Astrophys.

text: J,

text: Bockelée-Morvan,

text: D.,

text: et

text: al.

text: Icarus,


text: – 25 – Table 1. Initial abundances for the models (fractional abundances). Species Abundances Species Abundances × × p-H 4.783 10−1 CH (ice) 5.832 10−6 2 4 × × He 9.750 10−2 N 5.135 10−6 2 × × o-H 2.146 10−2 O (ice) 4.619 10−6 2 2 × × H 2.681 10−4 O 2.661 10−6 × × H O (ice) 7.658 10−5 N (ice) 2.464 10−6 2 2 × × CO (ice) 5.219 10−5 C H (ice) 6.493 10−6 3 2 × × CO 1.816 10−5 HD 1.479 10−5 × × HNO (ice) 3.541 10−6 O 9.645 10−6 2 × × HDO (ice) 2.887 10−6 NH (ice) 8.663 10−6 3 × × D 2.731 10−6 OH 2.295 10−6 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Table

text: Initial

text: abundances

text: for

text: the

text: models

text: (fractional

text: abundances).

text: Species

text: Abundances

text: Species

text: Abundances

text: p-H

text: CH

text: (ice)

text: He

text: N

text: o-H

text: O

text: (ice)

text: H

text: O

text: H

text: O

text: (ice)

text: N

text: (ice)

text: CO

text: (ice)

text: C

text: H

text: (ice)

text: CO

text: HD

text: HNO

text: (ice)

text: O

text: HDO

text: (ice)

text: NH

text: (ice)

text: D

text: OH

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##