text: Now, if the linear orders f and g arise from the same cyclic order π , u u u then they diﬀer in only a cyclic permutation. An immediate consequence is that each coin C must be cyclic so that the quantum walk for a rotation u system is well-deﬁned. This answers our ﬁrst question. In addition, for diﬀerent rotation systems, we wish to obtain diﬀerent transition matrices, so the coin C should not commute with any non-cyclic permutation. We show u that this is guaranteed as long as C has simple eigenvalues. u 5.2 Lemma. Let C be a circulant unitary matrix with simple eigenvalues. u Then C commutes with a permutation matrix P if and only if P is cyclic. u u u Proof. Since C has simple eigenvalues, its commutant consists of precisely u the polynomials in C , which are all cyclic. u × In Section 8.1, we will pick a 3 3 circulant coin with simple eigenvalues, and investigate the arc-reversal quantum walks for all rotation systems of cubic graphs on up to 10 vertices. 6 Asymptotic Properties The discussion in this section applies to any discrete-time quantum walks of the form Uk, with U being a unitary matrix. There are two questions about the asymptotic behaviors of a quantum walk: how long does it take on average to reach a target state, and what is the probability distribution of all states after a long period of time? 6.1 Hitting The hitting time measures how fast a quantum walk reaches a speciﬁc state. Let x be the initial state, and y the target state. A typical choice for x and y would be the characteristic vectors of two arcs in a graph. Since the state of the system is in a superposition, it is not on an arc until we perform a measurement. However, if we do a complete measurement after each step, the quantum walk will collapse to a classical random walk. Thus, we need a way to deﬁne “reaching” without killing the quantum coherence. One choice is to let the quantum walk evolve and do a complete mea- surement only once. The one-shot hitting time, given by Kempe [12], is (cid:12) (cid:12) the time k when a complete m(cid:12)easurem(cid:12) ent returns the target state with high probability: ∗ ≥ − y Ukx 1 (cid:15). 16 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Now,

text: if

text: the

text: linear

text: orders

text: f

text: and

text: g

text: arise

text: from

text: the

text: same

text: cyclic

text: order

text: π

text: u

text: u

text: u

text: then

text: they

text: diﬀer

text: in

text: only

text: a

text: cyclic

text: permutation.

text: An

text: immediate

text: consequence

text: is

text: that

text: each

text: coin

text: C

text: must

text: be

text: cyclic

text: so

text: that

text: the

text: quantum

text: walk

text: for

text: a

text: rotation

text: u

text: system

text: is

text: well-deﬁned.

text: This

text: answers

text: our

text: ﬁrst

text: question.

text: In

text: addition,

text: for

text: diﬀerent

text: rotation

text: systems,

text: we

text: wish

text: to

text: obtain

text: diﬀerent

text: transition

text: matrices,

text: so

text: the

text: coin

text: C

text: should

text: not

text: commute

text: with

text: any

text: non-cyclic

text: permutation.

text: We

text: show

text: u

text: that

text: this

text: is

text: guaranteed

text: as

text: long

text: as

text: C

text: has

text: simple

text: eigenvalues.

text: u

text: Lemma.

text: Let

text: C

text: be

text: a

text: circulant

text: unitary

text: matrix

text: with

text: simple

text: eigenvalues.

text: u

text: Then

text: C

text: commutes

text: with

text: a

text: permutation

text: matrix

text: P

text: if

text: and

text: only

text: if

text: P

text: is

text: cyclic.

text: u

text: u

text: u

text: Proof.

text: Since

text: C

text: has

text: simple

text: eigenvalues,

text: its

text: commutant

text: consists

text: of

text: precisely

text: u

text: the

text: polynomials

text: in

text: C

text: which

text: are

text: all

text: cyclic.

text: u

text: In

text: Section

text: we

text: will

text: pick

text: a

text: circulant

text: coin

text: with

text: simple

text: eigenvalues,

text: and

text: investigate

text: the

text: arc-reversal

text: quantum

text: walks

text: for

text: all

text: rotation

text: systems

text: of

text: cubic

text: graphs

text: on

text: up

text: to

text: vertices.

text: Asymptotic

text: Properties

text: The

text: discussion

text: in

text: this

text: section

text: applies

text: to

text: any

text: discrete-time

text: quantum

text: walks

text: of

text: the

text: form

text: Uk,

text: with

text: U

text: being

text: a

text: unitary

text: matrix.

text: There

text: are

text: two

text: questions

text: about

text: the

text: asymptotic

text: behaviors

text: of

text: a

text: quantum

text: walk:

text: how

text: long

text: does

text: it

text: take

text: on

text: average

text: to

text: reach

text: a

text: target

text: state,

text: and

text: what

text: is

text: the

text: probability

text: distribution

text: of

text: all

text: states

text: after

text: a

text: long

text: period

text: of

text: time?

text: Hitting

text: The

text: hitting

text: time

text: measures

text: how

text: fast

text: a

text: quantum

text: walk

text: reaches

text: a

text: speciﬁc

text: state.

text: Let

text: x

text: be

text: the

text: initial

text: state,

text: and

text: y

text: the

text: target

text: state.

text: A

text: typical

text: choice

text: for

text: x

text: and

text: y

text: would

text: be

text: the

text: characteristic

text: vectors

text: of

text: two

text: arcs

text: in

text: a

text: graph.

text: Since

text: the

text: state

text: of

text: the

text: system

text: is

text: in

text: a

text: superposition,

text: it

text: is

text: not

text: on

text: an

text: arc

text: until

text: we

text: perform

text: a

text: measurement.

text: However,

text: if

text: we

text: do

text: a

text: complete

text: measurement

text: after

text: each

text: step,

text: the

text: quantum

text: walk

text: will

text: collapse

text: to

text: a

text: classical

text: random

text: walk.

text: Thus,

text: we

text: need

text: a

text: way

text: to

text: deﬁne

text: “reaching”

text: without

text: killing

text: the

text: quantum

text: coherence.

text: One

text: choice

text: is

text: to

text: let

text: the

text: quantum

text: walk

text: evolve

text: and

text: do

text: a

text: complete

text: mea-

text: surement

text: only

text: once.

text: The

text: one-shot

text: hitting

text: time,

text: given

text: by

text: Kempe

text: is

text: the

text: time

text: k

text: when

text: a

text: complete

text: ent

text: returns

text: the

text: target

text: state

text: with

text: high

text: probability:

text: y

text: Ukx

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:0) (cid:1) (cid:0) (cid:1) are the amplitudes on the arcs in S. Let · · · · · · T D = e e e e e e S j1 j2 jm j1 j2 jm be the characteristic matrix of S, that is, the diagonal matrix whose (a, a)- entry is 1 if a is in S. Then given initial state x, the probability that the quantum walk is on S at time k is ∗ ∗ P (k) = x (Uk) D Ukx. S S While this probability does not co(cid:88)nverge as k goes to inﬁnity, the average probability over time − K 1 1 P (k) S K k=0 does as K goes to inﬁnity, for any initial state x. Before we prove it, we note (cid:88) that every unitary matrix U can be written as U = eiθrF r r where eiθr is an eigenvalue of U, and F is a Hermitian matrix representing r the projection onto the eigenspace of eiθr. This is usually called the spectral decomposition of U. 6.1 Theorem. Let F , F , . . . , F be the spectral idempotents of the transi- 1 2 m tion matrix U. Let x be the initial state. For any subset S of the arcs, the (cid:88) average probability that the quantum walk is on some arc of S converges to ∗ x F D F x. r S r r (cid:88) Proof. Consider the spectral decomposition of U U = eiθrF . r (cid:88) r It suﬃces to show that − K 1 1 ∗ (Uk) D Uk S K k=0 18 ##LTLine## ##LTLine##

label: paragraph

text: are

text: the

text: amplitudes

text: on

text: the

text: arcs

text: in

text: S.

text: Let

text: T

text: D

text: e

text: e

text: e

text: e

text: e

text: e

text: S

text: jm

text: jm

text: be

text: the

text: characteristic

text: matrix

text: of

text: S,

text: that

text: is,

text: the

text: diagonal

text: matrix

text: whose

text: (a,

text: a)-

text: entry

text: is

text: if

text: a

text: is

text: in

text: S.

text: Then

text: given

text: initial

text: state

text: x,

text: the

text: probability

text: that

text: the

text: quantum

text: walk

text: is

text: on

text: S

text: at

text: time

text: k

text: is

text: P

text: (k)

text: x

text: (Uk)

text: D

text: Ukx.

text: S

text: S

text: While

text: this

text: probability

text: does

text: not

text: as

text: k

text: goes

text: to

text: inﬁnity,

text: the

text: average

text: probability

text: over

text: time

text: K

text: P

text: (k)

text: S

text: K

text: does

text: as

text: K

text: goes

text: to

text: inﬁnity,

text: for

text: any

text: initial

text: state

text: x.

text: Before

text: we

text: prove

text: it,

text: we

text: note

text: that

text: every

text: unitary

text: matrix

text: U

text: can

text: be

text: written

text: as

text: U

text: eiθrF

text: r

text: r

text: where

text: eiθr

text: is

text: an

text: eigenvalue

text: of

text: U,

text: and

text: F

text: is

text: a

text: Hermitian

text: matrix

text: representing

text: r

text: the

text: projection

text: onto

text: the

text: eigenspace

text: of

text: eiθr.

text: This

text: is

text: usually

text: called

text: the

text: spectral

text: decomposition

text: of

text: U.

text: Theorem.

text: Let

text: F

text: F

text: F

text: be

text: the

text: spectral

text: idempotents

text: of

text: the

text: transi-

text: m

text: tion

text: matrix

text: U.

text: Let

text: x

text: be

text: the

text: initial

text: state.

text: For

text: any

text: subset

text: S

text: of

text: the

text: arcs,

text: the

text: average

text: probability

text: that

text: the

text: quantum

text: walk

text: is

text: on

text: some

text: arc

text: of

text: S

text: converges

text: to

text: x

text: F

text: D

text: F

text: x.

text: r

text: S

text: r

text: r

text: Proof.

text: Consider

text: the

text: spectral

text: decomposition

text: of

text: U

text: U

text: eiθrF

text: r

text: r

text: It

text: suﬃces

text: to

text: show

text: that

text: K

text: (Uk)

text: D

text: Uk

text: S

text: K

text: ##LTLine##

text: ##LTLine##


text: (cid:88) converges to the density matrix after the channel: F ρF . r r r Now, let s be the size of the subset S and consider 1 1 · · · 1 ρ := D = e eT + e eT . s S s j1 j1 s jm jm This is a density matrix of a mixed state—a convex combination of the pure (cid:80) states associated with the arcs in S. Hence, if the quantum walk starts with state x, then the average probability of the walk being on S is the inner (cid:68) (cid:88) ∗ (cid:69) (cid:88) product of the density matrices xx and F ρF , scaled by the size of S: r r r ∗ ∗ s xx , F ρF = x F D F x. r r r S r r r The mixing time of a quantum walk measures how far the average proba- bility distribution is from the stationary distribution. Since the average prob- ability on every subset converges, it does not make a big diﬀerence whether the distribution is on the arcs or on the vertices. In [1], Aharonov et al studied the mixing time on the vertices and obtained an upper bound for a general graph. They further showed that the mixing time of a quantum walk on an n-cycle with the Hadamard coin is bounded above by O(n log n), giving a quadratic speedup over the classical walk. We now extend some of their results to the arc probabilities. Given (cid:15), deﬁne the mixing time M to be the smallest K such that for ≥ (cid:15) all L K and all initial states, the average distribution over L steps on the arcs is (cid:15)-close to the limiting distribution. More explicitly, let P (k) denote j the probability on the j-th arc, and let D = e eT j j j be its characteristic m(cid:12)atrix. The mixing time is is(cid:12) the minimum positive ≥ integer K such tha(cid:88)t fo(cid:12)(cid:12)r al(cid:88)l time L K(cid:88)and all initia(cid:12)(cid:12)l states x, (cid:12) (cid:12) (cid:12) − (cid:12) 1 L 1 − ∗ ≤ P (k) x F D F x (cid:15). j r j r L j k=0 r 20 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: converges

text: to

text: the

text: density

text: matrix

text: after

text: the

text: channel:

text: F

text: ρF

text: r

text: r

text: r

text: Now,

text: let

text: s

text: be

text: the

text: size

text: of

text: the

text: subset

text: S

text: and

text: consider

text: ρ

text: D

text: e

text: eT

text: e

text: eT

text: s

text: S

text: s

text: s

text: jm

text: jm

text: This

text: is

text: a

text: density

text: matrix

text: of

text: a

text: mixed

text: state—a

text: convex

text: combination

text: of

text: the

text: pure

text: states

text: associated

text: with

text: the

text: arcs

text: in

text: S.

text: Hence,

text: if

text: the

text: quantum

text: walk

text: starts

text: with

text: state

text: x,

text: then

text: the

text: average

text: probability

text: of

text: the

text: walk

text: being

text: on

text: S

text: is

text: the

text: inner

text: product

text: of

text: the

text: density

text: matrices

text: xx

text: and

text: F

text: ρF

text: scaled

text: by

text: the

text: size

text: of

text: S:

text: r

text: r

text: r

text: s

text: xx

text: F

text: ρF

text: x

text: F

text: D

text: F

text: x.

text: r

text: r

text: r

text: S

text: r

text: r

text: r

text: The

text: mixing

text: time

text: of

text: a

text: quantum

text: walk

text: measures

text: how

text: far

text: the

text: average

text: proba-

text: bility

text: distribution

text: is

text: from

text: the

text: stationary

text: distribution.

text: Since

text: the

text: average

text: prob-

text: ability

text: on

text: every

text: subset

text: converges,

text: it

text: does

text: not

text: make

text: a

text: big

text: diﬀerence

text: whether

text: the

text: distribution

text: is

text: on

text: the

text: arcs

text: or

text: on

text: the

text: vertices.

text: In

text: Aharonov

text: et

text: al

text: studied

text: the

text: mixing

text: time

text: on

text: the

text: vertices

text: and

text: obtained

text: an

text: upper

text: bound

text: for

text: a

text: general

text: graph.

text: They

text: further

text: showed

text: that

text: the

text: mixing

text: time

text: of

text: a

text: quantum

text: walk

text: on

text: an

text: n-cycle

text: with

text: the

text: Hadamard

text: coin

text: is

text: bounded

text: above

text: by

text: O(n

text: log

text: n),

text: giving

text: a

text: quadratic

text: speedup

text: over

text: the

text: classical

text: walk.

text: We

text: now

text: extend

text: some

text: of

text: their

text: results

text: to

text: the

text: arc

text: probabilities.

text: Given

text: deﬁne

text: the

text: mixing

text: time

text: M

text: to

text: be

text: the

text: smallest

text: K

text: such

text: that

text: for

text: all

text: L

text: K

text: and

text: all

text: initial

text: states,

text: the

text: average

text: distribution

text: over

text: L

text: steps

text: on

text: the

text: arcs

text: is

text: to

text: the

text: limiting

text: distribution.

text: More

text: explicitly,

text: let

text: P

text: (k)

text: denote

text: j

text: the

text: probability

text: on

text: the

text: j-th

text: arc,

text: and

text: let

text: D

text: e

text: eT

text: j

text: j

text: j

text: be

text: its

text: characteristic

text: The

text: mixing

text: time

text: is

text: the

text: minimum

text: positive

text: integer

text: K

text: such

text: time

text: L

text: all

text: states

text: x,

text: L

text: P

text: (k)

text: x

text: F

text: D

text: F

text: x

text: j

text: r

text: j

text: r

text: L

text: j

text: r

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: trace. Meanwhile, for the arc-reversal model, the total entropy distinguishes diﬀerent graph embeddings, and increases as the genus increases for most of the time. Besides the natural question arising from the aforementioned experi- ments, we list some other open problems in the end. It is not our current goal to give a charaterization of the most general form of a model. Rather, we aim to ﬁnd some speciﬁc choice of the building blocks, such as the coins, which induce interesting walks that will reveal clear relation between the properties of the graphs and the properties of the walks. 2 Models A discrete-time quantum walk, in its most general form, is a power of a unitary matrix, which updates the amplitudes on arcs at each step. While it seems natural to construct a unitary matrix acting on the vertices of a graph, not every graph admits a unitary weighted adjacency matrix. The path on three vertices is an example. In [17], Severini discovered some properties of digraphs that admit unitary representations. Alternatively, for an arbitrary graph we can always construct a unitary matrix acting on a larger space. In each of the models we describe below, the transition matrix is acting on the arcs, or the ordered pairs of vertices, and is a product of two sparse unitary matrices. The ﬁrst two types of walks are driven by a set of coins, while the last one is coinless. 2.1 Arc-Reversal Model The ﬁrst model we investigate dates back to 2001, when Watrous [21] presented a method to simulate random walks on regular graphs using quan- tum computations. In [13] Kendon extended his idea to a class of coined quantum walks on general graphs. Based on this model, Emms et al [7, 8] proposed an algorithm for the graph isomorphism problem. They tested a large number of strongly regular graphs, and the spectrum of their proposed matrix successfully distinguished all of their non-isomorphic strongly regular graphs with the same parameters. We will view an undirected graph X as a directed graph, with each edge replaced by a pair of opposite arcs. Suppose X has n vertices and m arcs. Our C quantum walk takes place in the complex inner product space m, spanned by the characteristic vectors e of the arcs (u, v). Let R be the permutation u,v 3

text: trace.

text: Meanwhile,

text: for

text: the

text: arc-reversal

text: model,

text: the

text: total

text: entropy

text: distinguishes

text: diﬀerent

text: graph

text: embeddings,

text: and

text: increases

text: as

text: the

text: genus

text: increases

text: for

text: most

text: of

text: the

text: time.

text: Besides

text: the

text: natural

text: question

text: arising

text: from

text: the

text: aforementioned

text: experi-

text: ments,

text: we

text: list

text: some

text: other

text: open

text: problems

text: in

text: the

text: end.

text: It

text: is

text: not

text: our

text: current

text: goal

text: to

text: give

text: a

text: charaterization

text: of

text: the

text: most

text: general

text: form

text: of

text: a

text: model.

text: Rather,

text: we

text: aim

text: to

text: ﬁnd

text: some

text: speciﬁc

text: choice

text: of

text: the

text: building

text: blocks,

text: such

text: as

text: the

text: coins,

text: which

text: induce

text: interesting

text: walks

text: that

text: will

text: reveal

text: clear

text: relation

text: between

text: the

text: properties

text: of

text: the

text: graphs

text: and

text: the

text: properties

text: of

text: the

text: walks.

label: section

text: Models

text: A

text: discrete-time

text: quantum

text: walk,

text: in

text: its

text: most

text: general

text: form,

text: is

text: a

text: power

text: of

text: a

text: unitary

text: matrix,

text: which

text: updates

text: the

text: amplitudes

text: on

text: arcs

text: at

text: each

text: step.

text: While

text: it

text: seems

text: natural

text: to

text: construct

text: a

text: unitary

text: matrix

text: acting

text: on

text: the

text: vertices

text: of

text: a

text: graph,

text: not

text: every

text: graph

text: admits

text: a

text: unitary

text: weighted

text: adjacency

text: matrix.

text: The

text: path

text: on

text: three

text: vertices

text: is

text: an

text: example.

text: In

text: Severini

text: discovered

text: some

text: properties

text: of

text: digraphs

text: that

text: admit

text: unitary

text: representations.

text: Alternatively,

text: for

text: an

text: arbitrary

text: graph

text: we

text: can

text: always

text: construct

text: a

text: unitary

text: matrix

text: acting

text: on

text: a

text: larger

text: space.

text: In

text: each

text: of

text: the

text: models

text: we

text: describe

text: below,

text: the

text: transition

text: matrix

text: is

text: acting

text: on

text: the

text: arcs,

text: or

text: the

text: ordered

text: pairs

text: of

text: vertices,

text: and

text: is

text: a

text: product

text: of

text: two

text: sparse

text: unitary

text: matrices.

text: The

text: ﬁrst

text: two

text: types

text: of

text: walks

text: are

text: driven

text: by

text: a

text: set

text: of

text: coins,

text: while

text: the

text: last

text: one

text: is

text: coinless.

text: Arc-Reversal

text: Model

text: The

text: ﬁrst

text: model

text: we

text: investigate

text: dates

text: back

text: to

text: when

text: Watrous

text: presented

text: a

text: method

text: to

text: simulate

text: random

text: walks

text: on

text: regular

text: graphs

text: using

text: quan-

text: tum

text: computations.

text: In

text: Kendon

text: extended

text: his

text: idea

text: to

text: a

text: class

text: of

text: coined

text: quantum

text: walks

text: on

text: general

text: graphs.

text: Based

text: on

text: this

text: model,

text: Emms

text: et

text: al

text: proposed

text: an

text: algorithm

text: for

text: the

text: graph

text: isomorphism

text: problem.

text: They

text: tested

text: a

text: large

text: number

text: of

text: strongly

text: regular

text: graphs,

text: and

text: the

text: spectrum

text: of

text: their

text: proposed

text: matrix

text: successfully

text: distinguished

text: all

text: of

text: their

text: non-isomorphic

text: strongly

text: regular

text: graphs

text: with

text: the

text: same

text: parameters.

text: We

text: will

text: view

text: an

text: undirected

text: graph

text: X

text: as

text: a

text: directed

text: graph,

text: with

text: each

text: edge

text: replaced

text: by

text: a

text: pair

text: of

text: opposite

text: arcs.

text: Suppose

text: X

text: has

text: n

text: vertices

text: and

text: m

text: arcs.

text: Our

text: C

text: quantum

text: walk

text: takes

text: place

text: in

text: the

text: complex

text: inner

text: product

text: space

text: m,

text: spanned

text: by

text: the

text: characteristic

text: vectors

text: e

text: of

text: the

text: arcs

text: (u,

text: v).

text: Let

text: R

text: be

text: the

text: permutation

text: u,v


text: (cid:88) Theorem 6.1 implies that the average probability distribution 1 K ◦ Uk Uk K (cid:88) k=0 converges to the following Hermitian matrix ◦ F F . r r (cid:99) r Following Godsil’s notion for continuous-time quantum walks [9], we will denote this limit by M, and refer to it as the average mixing matrix. In [9], Godsil established several proper(cid:99)ties of the continuous-time average mixing. We extend some of his results to discrete-time qu(cid:99)antum walks. The ﬁrst observation is that M is do(cid:99)ubly-stochastic, in both the contin- uous and discrete cases. Thus each column of M represents a probability distribution. For the j-th col(cid:88)umn of M(cid:16), we (cid:17)deﬁne its entropy to be the (cid:99) (cid:99) negative expectation of the logarithm of its entries, that is, − M log M (cid:96)j (cid:96)j (cid:96) The entropy reaches its maximum if and only if the probability distribution with respect to the initial state e is uniform. We also deﬁne the total j entropy to be the sum of the entropies over all columns, although it is not an entropy. This invariant has been applied in structural pattern recognition. For example, Bai et al [4] proposed a graph signature based on the entropy of the average mixing matrix of a graph. According to the experimental results, this entropic measure allows us to distinguish diﬀerent structures. In the continuous case, the average mixing matrix is positive semideﬁnite with eigenvalues no greater than one [9]. W(cid:99)e show that the same statement holds for the discrete average mixing matrix. 7.1 Lemma. The average mixing matrix M is positive semideﬁnite, and its eigenvalues lie in [0, 1]. Proof. Since F is positive semideﬁnite, its complex c(cid:99)onjugate F is also r ⊗ r positive semideﬁnite. As a principal submatrix of F F , the Schur product ◦ r r (cid:32) (cid:33) (cid:32) (cid:33) F F is positive semideﬁnite. Hence the eigenvalues of M are non-negative. r s (cid:88) (cid:88) (cid:88) It follows from (cid:99) ◦ ◦ I = I I = F F = M + F F r s r s (cid:54) r s r=s 23 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Theorem

text: implies

text: that

text: the

text: average

text: probability

text: distribution

text: K

text: Uk

text: Uk

text: K

text: converges

text: to

text: the

text: following

text: Hermitian

text: matrix

text: F

text: F

text: r

text: r

text: r

text: Following

text: Godsil’s

text: notion

text: for

text: continuous-time

text: quantum

text: walks

text: we

text: will

text: denote

text: this

text: limit

text: by

text: M,

text: and

text: refer

text: to

text: it

text: as

text: the

text: average

text: mixing

text: matrix.

text: In

text: Godsil

text: established

text: several

text: of

text: the

text: continuous-time

text: average

text: mixing.

text: We

text: extend

text: some

text: of

text: his

text: results

text: to

text: discrete-time

text: walks.

text: The

text: ﬁrst

text: observation

text: is

text: that

text: M

text: is

text: in

text: both

text: the

text: contin-

text: uous

text: and

text: discrete

text: cases.

text: Thus

text: each

text: column

text: of

text: M

text: represents

text: a

text: probability

text: distribution.

text: For

text: the

text: j-th

text: of

text: we

text: its

text: entropy

text: to

text: be

text: the

text: negative

text: expectation

text: of

text: the

text: logarithm

text: of

text: its

text: entries,

text: that

text: is,

text: M

text: log

text: M

text: The

text: entropy

text: reaches

text: its

text: maximum

text: if

text: and

text: only

text: if

text: the

text: probability

text: distribution

text: with

text: respect

text: to

text: the

text: initial

text: state

text: e

text: is

text: uniform.

text: We

text: also

text: deﬁne

text: the

text: total

text: j

text: entropy

text: to

text: be

text: the

text: sum

text: of

text: the

text: entropies

text: over

text: all

text: columns,

text: although

text: it

text: is

text: not

text: an

text: entropy.

text: This

text: invariant

text: has

text: been

text: applied

text: in

text: structural

text: pattern

text: recognition.

text: For

text: example,

text: Bai

text: et

text: al

text: proposed

text: a

text: graph

text: signature

text: based

text: on

text: the

text: entropy

text: of

text: the

text: average

text: mixing

text: matrix

text: of

text: a

text: graph.

text: According

text: to

text: the

text: experimental

text: results,

text: this

text: entropic

text: measure

text: allows

text: us

text: to

text: distinguish

text: diﬀerent

text: structures.

text: In

text: the

text: continuous

text: case,

text: the

text: average

text: mixing

text: matrix

text: is

text: positive

text: semideﬁnite

text: with

text: eigenvalues

text: no

text: greater

text: than

text: one

text: show

text: that

text: the

text: same

text: statement

text: holds

text: for

text: the

text: discrete

text: average

text: mixing

text: matrix.

text: Lemma.

text: The

text: average

text: mixing

text: matrix

text: M

text: is

text: positive

text: semideﬁnite,

text: and

text: its

text: eigenvalues

text: lie

text: in

text: Proof.

text: Since

text: F

text: is

text: positive

text: semideﬁnite,

text: its

text: complex

text: F

text: is

text: also

text: r

text: r

text: positive

text: semideﬁnite.

text: As

text: a

text: principal

text: submatrix

text: of

text: F

text: F

text: the

text: Schur

text: product

text: r

text: r

text: F

text: F

text: is

text: positive

text: semideﬁnite.

text: Hence

text: the

text: eigenvalues

text: of

text: M

text: are

text: non-negative.

text: r

text: s

text: It

text: follows

text: from

text: I

text: I

text: I

text: F

text: F

text: M

text: F

text: F

text: r

text: s

text: r

text: s

text: r

text: s

text: r=s

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 2.3 Two-Reﬂections Model The third model is a direct quantization of the classical random walks, without introducing a coin register. It was extracted from Ambainis’s paper [2] and formalized by Szegedy [19]. Let M be a Markov chain on X. We will construct two reﬂections R and R on the n2 ordered pairs of vertices based 1 2 on M, and set U = R R . 2 1 First, let N denote the matrix obtained from M by taking the square root (cid:0) (cid:1) of its entries. Next, deﬁne two partitions of the ordered pairs: (cid:0) (cid:1) ⊗ · · · ⊗ Q = e Ne e Ne 1 1 1 n n ⊗ · · · ⊗ Q = NT e e NT e e . 2 1 1 n n × Since M is doubly stochastic, these are n2 n matrices such that QT Q = QT Q = I. 1 1 2 2 Then for each j, the matrix Q QT is a projection onto the column space of j j Q , and j − R = 2Q QT I j j j is a reﬂection about the column space of Q . j For instance, take the simple random walk on K with (cid:32) (cid:33) 3 1 2 3 1 0 1/2 1/2 M = 2 1/2 0 1/2 . 3 1/2 1/2 0 8

text: Two-Reﬂections

text: Model

text: The

text: third

text: model

text: is

text: a

text: direct

text: quantization

text: of

text: the

text: classical

text: random

text: walks,

text: without

text: introducing

text: a

text: coin

text: register.

text: It

text: was

text: extracted

text: from

text: Ambainis’s

text: paper

text: and

text: formalized

text: by

text: Szegedy

text: Let

text: M

text: be

text: a

text: Markov

text: chain

text: on

text: X.

text: We

text: will

text: construct

text: two

text: reﬂections

text: R

text: and

text: R

text: on

text: the

text: ordered

text: pairs

text: of

text: vertices

text: based

text: on

text: M,

text: and

text: set

text: U

text: R

text: R

text: First,

text: let

text: N

text: denote

text: the

text: matrix

text: obtained

text: from

text: M

text: by

text: taking

text: the

text: square

text: root

text: of

text: its

text: entries.

text: Next,

text: deﬁne

text: two

text: partitions

text: of

text: the

text: ordered

text: pairs:

text: Q

text: e

text: Ne

text: e

text: Ne

text: n

text: n

text: Q

text: NT

text: e

text: e

text: NT

text: e

text: e

text: n

text: n

text: Since

text: M

text: is

text: doubly

text: stochastic,

text: these

text: are

text: n

text: matrices

text: such

text: that

text: QT

text: Q

text: QT

text: Q

text: I.

text: Then

text: for

text: each

text: j,

text: the

text: matrix

text: Q

text: QT

text: is

text: a

text: projection

text: onto

text: the

text: column

text: space

text: of

text: j

text: j

text: Q

text: and

text: j

text: R

text: QT

text: I

text: j

text: j

text: j

text: is

text: a

text: reﬂection

text: about

text: the

text: column

text: space

text: of

text: Q

text: j

text: For

text: instance,

text: take

text: the

text: simple

text: random

text: walk

text: on

text: K

text: with

text: M


text:     Then we have  1 2 3   1 2 3      √ √ 11 0 0 0  11 0 0 0      √ √ 121/ 2 0 0  12 0 1/ 2 0      131/ 2 0√ 0  13 0√ 0 1/ 2     21 0 1/ 2 0  211/ 2 0 0      Q = 22 0 0√ 0  Q = 22 0 0 0√  1   2   23 0 1/ 2 0√  23 0√ 0 1/ 2 √ √ 31 0 0 1/ 2 31 1/ 2 0 0 32 0 0 1/ 2 32 0 1/ 2 0 33 0 0 0 33 0 0 0 Eﬀectively, Q partitions the arcs according to their tails, and Q partitions 1 2 the arcs according to their heads. This is true for any simple random walk, as the rows indexed by an non-arc is zero in both Q and Q . Thus, a 1 2 quantization of a simple random walk can be viewed as a walk on the arcs only. In the above example, the initial state e is mapped to e by R , and 12 13 1 then mapped to e by R . 12 2 2.4 Similarities and Diﬀerences In some cases the aforementioned models are equivalent, but there are also quantum walks that belong to only one of the frameworks. The shift matrix S in the shunt-decomposition is symmetric if and only if every shunt P j is symmetric, and so the arc coloring arising from the shunt-decomposition is in fact an edge coloring. Hence, the arc-reversal model and the shunt- decomposition model overlap when the same coins and same linear orders are applied, and the graph admits a d-edge-coloring. The arc-reversal model can also be equivalent to the two-reﬂections model, if the ﬁrst walk uses the Grover coins and lexicographical linear orders, and the second walk quantizes the simple random walk. They are equivalent in the sense that two steps of the ﬁrst walk has the same eﬀect as one step of the second walk. For more details, see the recent paper by Wong [22]. Another correlation between these two models has been found by Portugal and Segawa [16], who showed that an arc-reversal walk with Grover coins can be converted into a two-reﬂection walk on the same graph with each edge subdivided once. 3 Shunt-Decompositions 9 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Then

text: we

text: have

text: 0√

text: 0√

text: 2

text: Q

text: 0√

text: Q

text: 0√

text: 0√

text: 0√

text: 2

text: Eﬀectively,

text: Q

text: partitions

text: the

text: arcs

text: according

text: to

text: their

text: tails,

text: and

text: Q

text: partitions

text: the

text: arcs

text: according

text: to

text: their

text: heads.

text: This

text: is

text: true

text: for

text: any

text: simple

text: random

text: walk,

text: as

text: the

text: rows

text: indexed

text: by

text: an

text: non-arc

text: is

text: zero

text: in

text: both

text: Q

text: and

text: Q

text: Thus,

text: a

text: quantization

text: of

text: a

text: simple

text: random

text: walk

text: can

text: be

text: viewed

text: as

text: a

text: walk

text: on

text: the

text: arcs

text: only.

text: In

text: the

text: above

text: example,

text: the

text: initial

text: state

text: e

text: is

text: mapped

text: to

text: e

text: by

text: R

text: and

text: then

text: mapped

text: to

text: e

text: by

text: R

text: Similarities

text: and

text: Diﬀerences

text: In

text: some

text: cases

text: the

text: aforementioned

text: models

text: are

text: equivalent,

text: but

text: there

text: are

text: also

text: quantum

text: walks

text: that

text: belong

text: to

text: only

text: one

text: of

text: the

text: frameworks.

text: The

text: shift

text: matrix

text: S

text: in

text: the

text: shunt-decomposition

text: is

text: symmetric

text: if

text: and

text: only

text: if

text: every

text: shunt

text: P

text: j

text: is

text: symmetric,

text: and

text: so

text: the

text: arc

text: coloring

text: arising

text: from

text: the

text: shunt-decomposition

text: is

text: in

text: fact

text: an

text: edge

text: coloring.

text: Hence,

text: the

text: arc-reversal

text: model

text: and

text: the

text: shunt-

text: decomposition

text: model

text: overlap

text: when

text: the

text: same

text: coins

text: and

text: same

text: linear

text: orders

text: are

text: applied,

text: and

text: the

text: graph

text: admits

text: a

text: d-edge-coloring.

text: The

text: arc-reversal

text: model

text: can

text: also

text: be

text: equivalent

text: to

text: the

text: two-reﬂections

text: model,

text: if

text: the

text: ﬁrst

text: walk

text: uses

text: the

text: Grover

text: coins

text: and

text: lexicographical

text: linear

text: orders,

text: and

text: the

text: second

text: walk

text: quantizes

text: the

text: simple

text: random

text: walk.

text: They

text: are

text: equivalent

text: in

text: the

text: sense

text: that

text: two

text: steps

text: of

text: the

text: ﬁrst

text: walk

text: has

text: the

text: same

text: eﬀect

text: as

text: one

text: step

text: of

text: the

text: second

text: walk.

text: For

text: more

text: details,

text: see

text: the

text: recent

text: paper

text: by

text: Wong

text: Another

text: correlation

text: between

text: these

text: two

text: models

text: has

text: been

text: found

text: by

text: Portugal

text: and

text: Segawa

text: who

text: showed

text: that

text: an

text: arc-reversal

text: walk

text: with

text: Grover

text: coins

text: can

text: be

text: converted

text: into

text: a

text: two-reﬂection

text: walk

text: on

text: the

text: same

text: graph

text: with

text: each

text: edge

text: subdivided

text: once.

text: Shunt-Decompositions

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: 8 β β β 14 140 14 88 140 on1102 (a) Δ ()12 mK 130 (b) on 1102 (c)Δ ()1 mK 86 (d) ()mK 130 (e) Occupati 02468 1 ( Δ)2 emperature 111012000 xyz ( ) Occupati 02468 1 ( ) Δ2 emperature 78888024 ( ) β2 emperature 111012000 xyz ( ) 0 50 100 150 200 T 0 20 40 60 80 100 0 50 100 150 200 T 20 40 60 80 100 T 0 20 40 60 80 100 Time ms Time ms Time ms Time ms Time ms FIG. 6. (Color online) The parametric feedback cooling in only the rotational degrees of freedom for a nano-diamond (a = 48 nm, b = 53 nm). All cu{rves are averaged over 400 }trajectories. (a) and (b) show the cooling in both β1 and β2 with the cooling parameters ∆1 = η1,2,3 = 0, ζi = 1011 s/m2 . The black and purple lines show the rotational motion gets cooled as we increase the feedback parameters from ∆1 to ∆2 = 10∆1. The red, green and blue lines depict that the heating traject{ories in translational degrees of }freedom. (c), (d) and (e) show the result of cooling in only β1 with parameters ∆1 = η1,2,3 = 0, ζ2 = 0, ζ1 = 1011 s/m2 and ∆2 = 10∆1, and heating in β2 and x, y, z respectively. In (d), resonance heating causes massive heating in the uncooled β2 degree of freedom. The dashed lines in (b), (d) and (e) are the heating curves T = T0 + E˙ t with T0 the initial temperature and E˙ the corresponding heating rate from Tab. I. Combining the translational and rotational motion, (a = 38 nm, 60 nm) to (a = 48 nm, b = 53 nm). The the classical dynamics of the ellipsoid is governed by corresponding parameters are given in Tab. I. The clas- sical equations of motion are numerically solved using a fourth-order Runga-Kutta algorithm with adaptive time d2x m i (cid:39) −mω2(1 + ∆)x , steps [31]. All simulations are repeated many times and dt2 i i (31) data is collected by averaging over the diﬀerent runs to I d2βj (cid:39) −I ω2 (1 + ∆)β . reduce the random noise. 1 dt2 1 βj j We start by presenting the simulation with zero feed- back (η = 0, ζ = 0), which corresponds to the pure 1,2,3 1,2 The small oscillation approximation is used in the shot noise heating process. The system is prepared ini- above equations where all corrections quadratic in the tially at temperature T = 1 µK. The result is shown in i amplitude of oscillations have been dropped. x = Fig. (4), where each curve depicts the time evolution of i (x, y, z) and β = (β , β ). The shot noises in translation the energy in the corresponding degrees of freedom. Fig- j 1 2 and rotation are added at each time step according to ure 4(a) and 4(b) show the case (a = 15 nm, b = 70 nm) in the ﬁrst 100 ms. The rotational shot noise is about an order of magnitude larger than that in the translational p (t + δt) = p (t) + δW · δp , i i i i motion. The case (a = 38 nm, b = 60 nm) is given in (32) L (t + δt) = L (t) + δR · δL , Fig. 4(c) and 4(d), in which the rotational and transla- i i j j tional shot noise heating rates are of similar size. As the ellipticity gets smaller, the shot noise in the rotational where δW , δR are the standard normally distributed i j (cid:113) (cid:113) degrees of freedom becomes less than that in the trans- random numbers, and δpi = 2E˙Tiδt · m, δLj = 2E˙Rjδt · Ilational motion, which is shown in the Fig. 4(e) and 4(f) are the ﬂuctuation of the momentum and angular mo- for the case (a = 48 nm, b = 53 nm). From Tab. I, the mentum for each degree of freedom induced by the shot case (a = 48 nm, b = 53 nm) has a higher rotational than noise. The heating rate in the z direction (optical po- translational oscillating frequency, which suggests that it larization direction) is half that of the other two trans- might be a good candidate for rotational cooling. lational degrees of freedom because the photons scatter The non-zero feedback cooling is performed with the less in the direction of the laser polarization [11]. ∆ is a system temperature initially prepared at T = 0.1 K. The i scalar which takes the form feedback parameters (η , ζ ) are chosen in a way such that i i Eq. (33) is much smaller than one and the position and (cid:88) (cid:88) velocity are assumed to be measured perfectly. ∆ = ηixix˙i + ζir2βiβ˙i, (33) First, we turn on the feedback in all degrees of freedom. i=1,2,3 i=1,2 The results are shown in Fig. (5). Because the calcula- tions are classical, the results for occupation less than where r is the size of the nanoparticle. The feedback 10 are qualitative/suggestive. However, we do expect parameters η and ζ have the unit Time/Length2 and that the classical results are approximately correct for i i they control the cooling limit and speed. Details about (cid:104)n(cid:105) ∼ 10 so we do expect this feedback could get to near the parameters and the parametric feedback cooling limit the ground state. By tuning the feedback parameters are given in the appendix. Simulations are performed for from ∆ = {η = 1.1 × 1011 s/m2, ζ = 1011 s/m2} 1 1,2,3 1,2 three diﬀerent nano-diamonds with decreasing elliptic- to ∆ = 10∆ , the system is observed to be quickly 2 1 ity, whose half axes go from (a = 15 nm, b = 70 nm), cooled. Both the translational and rotational occupa- ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: β

font: default

text: β

text: β

text: (a)

text: Δ

text: mK

text: (b)

text: on

text: (c)Δ

text: mK

text: (d)

text: ()mK

text: (e)

text: Occupati

text: emperature

text: xyz

text: Occupati

text: Δ2

text: emperature

text: β2

text: emperature

text: xyz

text: T

text: T

text: T

text: Time

text: ms

text: Time

text: ms

text: Time

text: ms

text: Time

text: ms

text: Time

text: ms

text: FIG.

text: (Color

text: online)

text: The

text: parametric

text: feedback

text: cooling

text: in

text: only

text: the

text: rotational

text: degrees

text: of

text: freedom

text: for

text: a

text: nano-diamond

text: (a

text: nm,

text: b

text: nm).

text: All

text: cu{rves

text: are

text: averaged

text: over

text: }trajectories.

text: (a)

text: and

text: (b)

text: show

text: the

text: cooling

text: in

text: both

text: β1

text: and

text: β2

text: with

text: the

text: cooling

text: parameters

text: ∆1

text: ζi

text: The

text: black

text: and

text: purple

text: lines

text: show

text: the

text: rotational

text: motion

text: gets

text: cooled

text: as

text: we

text: increase

text: the

text: feedback

text: parameters

text: from

text: ∆1

text: to

text: ∆2

text: The

text: red,

text: green

text: and

text: blue

text: lines

text: depict

text: that

text: the

text: heating

text: traject{ories

text: in

text: translational

text: degrees

text: of

text: }freedom.

text: (c),

text: (d)

text: and

text: (e)

text: show

text: the

text: result

text: of

text: cooling

text: in

text: only

text: β1

text: with

text: parameters

text: ∆1

text: ζ2

text: ζ1

text: and

text: ∆2

text: and

text: heating

text: in

text: β2

text: and

text: x,

text: y,

text: z

text: respectively.

text: In

text: (d),

text: resonance

text: heating

text: causes

text: massive

text: heating

text: in

text: the

text: uncooled

text: β2

text: degree

text: of

text: freedom.

text: The

text: dashed

text: lines

text: in

text: (b),

text: (d)

text: and

text: (e)

text: are

text: the

text: heating

text: curves

text: T

text: E˙

text: t

text: with

text: the

text: initial

text: temperature

text: and

text: E˙

text: the

text: corresponding

text: heating

text: rate

text: from

text: Tab.

text: I.

text: Combining

text: the

text: translational

text: and

text: rotational

text: motion,

text: (a

text: nm,

text: nm)

text: to

text: (a

text: nm,

text: b

text: nm).

text: The

text: the

text: classical

text: dynamics

text: of

text: the

text: ellipsoid

text: is

text: governed

text: by

text: corresponding

text: parameters

text: are

text: given

text: in

text: Tab.

text: I.

text: The

text: clas-

text: sical

text: equations

text: of

text: motion

text: are

text: numerically

text: solved

text: using

text: a

text: fourth-order

text: Runga-Kutta

text: algorithm

text: with

text: adaptive

text: time

text: m

text: i

text: ∆)x

text: steps

text: All

text: simulations

text: are

text: repeated

text: many

text: times

text: and

text: i

text: i

text: data

text: is

text: collected

text: by

text: averaging

text: over

text: the

text: diﬀerent

text: runs

text: to

text: I

text: −I

text: ω2

text: ∆)β

text: reduce

text: the

text: random

text: noise.

text: βj

text: j

text: We

text: start

text: by

text: presenting

text: the

text: simulation

text: with

text: zero

text: feed-

text: back

text: (η

text: ζ

text: which

text: corresponds

text: to

text: the

text: pure

text: The

text: small

text: oscillation

text: approximation

text: is

text: used

text: in

text: the

text: shot

text: noise

text: heating

text: process.

text: The

text: system

text: is

text: prepared

text: ini-

text: above

text: equations

text: where

text: all

text: corrections

text: quadratic

text: in

text: the

text: tially

text: at

text: temperature

text: T

text: µK.

text: The

text: result

text: is

text: shown

text: in

text: i

text: amplitude

text: of

text: oscillations

text: have

text: been

text: dropped.

text: x

text: Fig.

text: where

text: each

text: curve

text: depicts

text: the

text: time

text: evolution

text: of

text: i

text: (x,

text: y,

text: z)

text: and

text: β

text: (β

text: β

text: The

text: shot

text: noises

text: in

text: translation

text: the

text: energy

text: in

text: the

text: corresponding

text: degrees

text: of

text: freedom.

text: Fig-

text: j

text: and

text: rotation

text: are

text: added

text: at

text: each

text: time

text: step

text: according

text: to

text: ure

text: and

text: show

text: the

text: case

text: (a

text: nm,

text: b

text: nm)

text: in

text: the

text: ﬁrst

text: ms.

text: The

text: rotational

text: shot

text: noise

text: is

text: about

text: an

text: order

text: of

text: magnitude

text: larger

text: than

text: that

text: in

text: the

text: translational

text: p

text: (t

text: δt)

text: p

text: (t)

text: δW

text: δp

text: i

text: i

text: i

text: i

text: motion.

text: The

text: case

text: (a

text: nm,

text: b

text: nm)

text: is

text: given

text: in

text: L

text: (t

text: δt)

text: L

text: (t)

text: δR

text: δL

text: Fig.

text: and

text: in

text: which

text: the

text: rotational

text: and

text: transla-

text: i

text: i

text: j

text: j

text: tional

text: shot

text: noise

text: heating

text: rates

text: are

text: of

text: similar

text: size.

text: As

text: the

text: ellipticity

text: gets

text: smaller,

text: the

text: shot

text: noise

text: in

text: the

text: rotational

text: where

text: δW

text: δR

text: are

text: the

text: standard

text: normally

text: distributed

text: i

text: j

text: degrees

text: of

text: freedom

text: becomes

text: less

text: than

text: that

text: in

text: the

text: trans-

text: random

text: numbers,

text: and

text: δpi

text: m,

text: δLj

text: Ilational

text: motion,

text: which

text: is

text: shown

text: in

text: the

text: Fig.

text: and

text: are

text: the

text: ﬂuctuation

text: of

text: the

text: momentum

text: and

text: angular

text: mo-

text: for

text: the

text: case

text: (a

text: nm,

text: b

text: nm).

text: From

text: Tab.

text: I,

text: the

text: mentum

text: for

text: each

text: degree

text: of

text: freedom

text: induced

text: by

text: the

text: shot

text: case

text: (a

text: nm,

text: b

text: nm)

text: has

text: a

text: higher

text: rotational

text: than

text: noise.

text: The

text: heating

text: rate

text: in

text: the

text: z

text: direction

text: (optical

text: po-

text: translational

text: oscillating

text: frequency,

text: which

text: suggests

text: that

text: it

text: larization

text: direction)

text: is

text: half

text: that

text: of

text: the

text: other

text: two

text: trans-

text: might

text: be

text: a

text: good

text: candidate

text: for

text: rotational

text: cooling.

text: lational

text: degrees

text: of

text: freedom

text: because

text: the

text: photons

text: scatter

text: The

text: non-zero

text: feedback

text: cooling

text: is

text: performed

text: with

text: the

text: less

text: in

text: the

text: direction

text: of

text: the

text: laser

text: polarization

text: is

text: a

text: system

text: temperature

text: initially

text: prepared

text: at

text: T

text: K.

text: The

text: i

text: scalar

text: which

text: takes

text: the

text: form

text: feedback

text: parameters

text: (η

text: ζ

text: are

text: chosen

text: in

text: a

text: way

text: such

text: that

text: i

text: i

text: Eq.

text: is

text: much

text: smaller

text: than

text: one

text: and

text: the

text: position

text: and

text: velocity

text: are

text: assumed

text: to

text: be

text: measured

text: perfectly.

text: ηixix˙i

text: First,

text: we

text: turn

text: on

text: the

text: feedback

text: in

text: all

text: degrees

text: of

text: freedom.

text: The

text: results

text: are

text: shown

text: in

text: Fig.

text: Because

text: the

text: calcula-

text: tions

text: are

text: classical,

text: the

text: results

text: for

text: occupation

text: less

text: than

text: where

text: r

text: is

text: the

text: size

text: of

text: the

text: nanoparticle.

text: The

text: feedback

text: are

text: qualitative/suggestive.

text: However,

text: we

text: do

text: expect

text: parameters

text: η

text: and

text: ζ

text: have

text: the

text: unit

text: and

text: that

text: the

text: classical

text: results

text: are

text: approximately

text: correct

text: for

text: i

text: i

text: they

text: control

text: the

text: cooling

text: limit

text: and

text: speed.

text: Details

text: about

text: so

text: we

text: do

text: expect

text: this

text: feedback

text: could

text: get

text: to

text: near

text: the

text: parameters

text: and

text: the

text: parametric

text: feedback

text: cooling

text: limit

text: the

text: ground

text: state.

text: By

text: tuning

text: the

text: feedback

text: parameters

text: are

text: given

text: in

text: the

text: appendix.

text: Simulations

text: are

text: performed

text: for

text: from

text: {η

text: ζ

text: three

text: diﬀerent

text: nano-diamonds

text: with

text: decreasing

text: elliptic-

text: to

text: the

text: system

text: is

text: observed

text: to

text: be

text: quickly

text: ity,

text: whose

text: half

text: axes

text: go

text: from

text: (a

text: nm,

text: b

text: nm),

text: cooled.

text: Both

text: the

text: translational

text: and

text: rotational

text: occupa-

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##

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: ##LTLine##


text: (cid:90) (cid:90) (cid:90) ∗ − ∗ → T − → T = dγ dΓs ρ(cid:96)(Γs)δ(Γs ν )eΣ[Γs ( (Γ))s]δ(Y Ξ[Γs ( (Γ))s]) → T − → T = dγ ρ(cid:96)(ν)eΣ[ν ( (Γ))s]δ(Y Ξ[ν ( (Γ))s]). (cid:82) (91) T T ∗ ∗ − Here we used th(cid:90)e relation ( (Γ) ) = Γ . (cid:90)Then, takin(cid:90)g the limit and integration of lim →∞ dY e Y, we have τ (cid:90) − − → T − → T l→im∞ dY e YPFτ(Y) = l→im∞ dY e Y dγ ρ(cid:96)(ν)eΣ[ν ( (Γ))s]δ(Y Ξ[ν ( (Γ))s]) τ τ → T − → T = l→im∞ dγ ρ(cid:96)(ν)eΣ[ν ( (Γ))s]e Ξ[ν ( (Γ))s]. (92) τ T Here we note that γ(cid:90)= ( (Γ))s. We obtain (cid:90) τl→im∞ dY e−YPFτ(Y) = τl→im∞ Z (cid:42) dγ ρs(cid:88)s(γ)(cid:90)e−Ξ[ν→(cid:90)γ] (cid:43) = τl→im∞ Z (cid:42)exp − (cid:88)m (cid:90) dx (cid:90)−τ0 dt jm(Γs, x; t) · λm(x)(cid:43)ss − τ · = l→im∞ Z exp dx dt jm(Γs, x; t) λm(x) . (93) τ m 0 ss In the ﬁrst line, we have used eq. (69). In the last line, we have used the stationarity of the process. Thus, by eqs. (90) and (93), we obtain (cid:42)  (cid:90) (cid:90) (cid:43)  (cid:88)  τl→im∞ (cid:42)exp − (cid:88)m (cid:90) dx (cid:90)0τ dt(cid:48) jm(Γs, x; t(cid:48)) · λm(x) ss (cid:43) − τ (cid:48) (cid:48) · − = l→im∞ exp dx dt jm(Γs, x; t ) (Xm(x) λm(x)) . (94) τ m 0 ss By the deﬁnition of the cumulant generating functional, eq. (82), this gives the ﬂuctuation theorem (i.e., Andrieux- − Gaspard symmetry) Q(λ; X) = Q(X λ; X). 6. On the nonequilibrium detailed balance relation Some readers may feel that the assumption of the nonequilibrium detailed balance relation is a key relation, and that it is ”doubtful” whether it is formed. In this section, we examine the nonequilibrium detailed balance relation, eq.(59). Back to the derivation of the ﬂuctuation theorem for the entropy production, remind that the nonequilibrium detailed balance relation is used at eq.(65) (the McLennan-Zubarev steady state distribution), at eq.(78) (the ﬂuctu- ation theorem for the entropy production), and at eq.(91) (the ﬂuctuation theorem for the current). Suppose that the nonequilibrium detailed balance relation is given by → → ∗ → ∗ P[ν γ] = eΘ[ν γ]P[γ ν ], (95) → → where the function Θ[ν γ] is assumed not to be Σ[ν γ]. Then, following the derivation of the McLennan- Zubarev steady state distribution, we obtain the following steady state distribution. − → ρss(γ) = Z∗ 1ρ(cid:96)(ν) exp(Θ[ν γ]), (96) 15 ##LTLine##

label: equation

font: CMGCCG+txex

font: ZODMTY+txsy

text: T

text: T

font: INKTGB+rtxr

text: dγ

text: dΓs

font: SONBNE+rtxmi

text: ν

text: )eΣ[Γs

text: (Γ))s]δ(Y

text: Ξ[Γs

text: (Γ))s])

text: T

text: T

text: dγ

text: (Γ))s]δ(Y

text: Ξ[ν

text: (Γ))s]).

text: T

text: T

text: Here

text: we

text: used

text: relation

text: (Γ)

text: Γ

text: the

text: limit

text: and

text: integration

text: of

text: lim

text: dY

text: e

text: Y,

text: we

text: have

text: τ

text: T

text: T

text: l→im∞

text: dY

text: e

text: YPFτ(Y)

text: l→im∞

text: dY

text: e

text: Y

text: dγ

text: (Γ))s]δ(Y

text: Ξ[ν

text: (Γ))s])

text: τ

text: τ

text: T

text: T

text: l→im∞

text: dγ

text: (Γ))s]e

text: Ξ[ν

text: (Γ))s].

text: τ

text: T

text: Here

text: we

text: note

text: that

text: (Γ))s.

text: We

text: obtain

text: τl→im∞

text: dY

text: e−YPFτ(Y)

text: τl→im∞

text: Z

text: dγ

text: τl→im∞

text: Z

text: dx

text: dt

text: jm(Γs,

text: x;

text: t)

text: τ

text: l→im∞

text: Z

text: exp

text: dx

text: dt

text: jm(Γs,

text: x;

text: t)

text: λm(x)

text: τ

text: m

text: ss

text: In

text: the

text: ﬁrst

text: line,

text: we

text: have

text: used

text: eq.

text: In

text: the

text: last

text: line,

text: we

text: have

text: used

text: the

text: stationarity

text: of

text: the

text: process.

text: Thus,

text: by

text: eqs.

text: and

text: we

text: obtain

text: τl→im∞

text: dx

text: jm(Γs,

text: x;

text: λm(x)

text: ss

text: τ

text: l→im∞

text: exp

text: dx

text: dt

text: jm(Γs,

text: x;

text: t

text: (Xm(x)

text: λm(x))

text: τ

text: m

text: ss

text: By

text: the

text: deﬁnition

text: of

text: the

text: cumulant

text: generating

text: functional,

text: eq.

text: this

text: gives

text: the

text: ﬂuctuation

text: theorem

text: (i.e.,

text: Andrieux-

text: Gaspard

text: symmetry)

text: Q(λ;

text: X)

text: Q(X

text: λ;

text: X).

text: On

text: the

text: nonequilibrium

text: detailed

text: balance

text: relation

text: Some

text: readers

text: may

text: feel

text: that

text: the

text: assumption

text: of

text: the

text: nonequilibrium

text: detailed

text: balance

text: relation

text: is

text: a

text: key

text: relation,

text: and

text: that

text: it

text: is

text: ”doubtful”

text: whether

text: it

text: is

text: formed.

text: In

text: this

text: section,

text: we

text: examine

text: the

text: nonequilibrium

text: detailed

text: balance

text: relation,

text: Back

text: to

text: the

text: derivation

text: of

text: the

text: ﬂuctuation

text: theorem

text: for

text: the

text: entropy

text: production,

text: remind

text: that

text: the

text: nonequilibrium

text: detailed

text: balance

text: relation

text: is

text: used

text: at

text: (the

text: McLennan-Zubarev

text: steady

text: state

text: distribution),

text: at

text: (the

text: ﬂuctu-

text: ation

text: theorem

text: for

text: the

text: entropy

text: production),

text: and

text: at

text: (the

text: ﬂuctuation

text: theorem

text: for

text: the

text: current).

text: Suppose

text: that

text: the

text: nonequilibrium

text: detailed

text: balance

text: relation

text: is

text: given

text: by

text: P[ν

text: γ]

text: eΘ[ν

text: γ]P[γ

text: ν

text: where

text: the

text: function

text: Θ[ν

text: γ]

text: is

text: assumed

text: not

text: to

text: be

text: Σ[ν

text: γ].

text: Then,

text: following

text: the

text: derivation

text: of

text: the

text: McLennan-

text: Zubarev

text: steady

text: state

text: distribution,

text: we

text: obtain

text: the

text: following

text: steady

text: state

text: distribution.

text: ρss(γ)

text: Z∗

text: exp(Θ[ν

text: γ]),

text: ##LTLine##


text: Therefore, setting λ = 0 and X = 0, we have L 1 δ2Q − 1 δ2Q α,β(x, x1) = kB δλα(x)δXβ(x1)(0; 0) = 2kB δλα(x)δλβ(x1)(0; 0). (109) This gives the Onsager reciprocity relation[31, 32] L L αβ(x, x1) = βα(x1, x). (110) Expanding the McLennan-Zubarev steady state distrib(cid:90)ution in thermodynamic forces, namely expanding the ex- ponential function and the normalization constant Z, we get ∞ L 1 αβ(x, x1) = 2k −∞ dt φ(α2β)(x, x1; t), (111) B where φ(2)(x, x1; t) is the two-point current correlation function, αβ (cid:104) − (cid:104) (cid:105) − (cid:104) (cid:105) (cid:105) φ(α2β)(x, x1; t) = [jα(Γ, x; t) jα(Γ, x; t) eq][jβ(Γ, x1; 0) jβ(Γ, x1; 0) eq] eq. (112) Here note that the average is taken over the local equilibrium state. Comparing the term in eq. (102(cid:90)) with that of eq. (106) in(cid:90)the order of O((cid:15)1), ∞ ∞ − dt φ(2)(x, x1; t) = dt φ(2)(x, x1; t). (113) αβ αβ 0 0 L (cid:90) By eq. (113), αβ(x, x1) is given by ∞ L 1 αβ(x, x1) = k dt φ(α2β)(x, x1; t). (114) B 0 Equation (114) is nothing but the Green-Kubo formula [33, 34, 35]. 7.2. Non-linear response of O((cid:15)2) M The function αβγ(x, x1, x2) is given by M 1 δ3Q αβγ(x, x1, x2) = k2B δλα(x)δXβ(x1)δXγ(x2)(0; 0). (115) In the same way of the previous subsection, diﬀerentiating eq. (84), and setting λ and X = 0, we obtain M − 1 δ3Q αβγ(x, x1, x2) = 2k2B δλα(x)δλβ(x1)δλγ(x2)(0; 0) − 1 δ3Q (0; 0) 2k2B δλα(x)δλβ(x1)δXγ(x2) − 1 δ3Q (0; 0). (116) 2k2B δλα(x)δλγ(x1)δXβ(x2) Evaluating the right hand side of eq. (116), it leads 18 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Therefore,

text: setting

text: λ

font: TNBKMM+rtxbmi

text: and

text: X

text: we

text: have

text: L

text: α,β(x,

text: kB

text: This

text: gives

text: the

text: Onsager

text: reciprocity

text: L

text: L

text: αβ(x,

text: x).

text: Expanding

text: the

text: McLennan-Zubarev

text: steady

text: state

text: in

text: thermodynamic

text: forces,

text: namely

text: expanding

text: the

text: ex-

text: ponential

text: function

text: and

text: the

text: normalization

text: constant

text: Z,

text: we

text: get

text: L

text: αβ(x,

text: dt

text: t),

text: B

text: where

text: t)

text: is

text: the

text: two-point

text: current

text: correlation

text: function,

text: αβ

text: t)

text: [jα(Γ,

text: x;

text: t)

text: jα(Γ,

text: x;

text: t)

text: eq][jβ(Γ,

text: jβ(Γ,

text: eq]

text: eq.

text: Here

text: note

text: that

text: the

text: average

text: is

text: taken

text: over

text: the

text: local

text: equilibrium

text: state.

text: Comparing

text: the

text: term

text: in

text: eq.

text: with

text: that

text: of

text: eq.

text: order

text: of

text: dt

text: t)

text: dt

text: t).

text: αβ

text: αβ

text: L

text: By

text: eq.

text: αβ(x,

text: is

text: given

text: by

text: L

text: αβ(x,

text: k

text: dt

text: t).

text: B

text: Equation

text: is

text: nothing

text: but

text: the

text: Green-Kubo

text: formula

text: Non-linear

text: response

text: of

text: M

text: The

text: function

text: αβγ(x,

text: is

text: given

text: by

text: M

text: αβγ(x,

text: In

text: the

text: same

text: way

text: of

text: the

text: previous

text: subsection,

text: diﬀerentiating

text: eq.

text: and

text: setting

text: λ

text: and

text: X

text: we

text: obtain

text: M

text: αβγ(x,

text: Evaluating

text: the

text: right

text: hand

text: side

text: of

text: eq.

text: it

text: leads

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: ##LTLine##

text: ##LTLine##


text: In this paper, we use the followin{g n}otation f{or t}he variables of position and momentum. Γ = ({q1,}q{2, .}. . , qN, p1, p2, . . . , pN). The Hamiltonian H is a function of qi iN=1 and pi iN=1. The Hamiltonian may written as H = H( qi , pi ). Symmetry which the system possesses is important. This Hamiltonian has a symmetry. { } { } { } −{ } H( qi , pi ) = H( qi , pi ). (12) Time-reversal symmetry of orbits can be written as − − − qi,R(t) = qi( t), pi,R(t) = pi( t). (13) For the orbit Γ(t), the time-reversed orbit is written as Γ (t). R This system has three conservation laws. (1)Particle number conservation law: ∂n(Γ, x) + div(j(Γ, x)) = 0. (14) ∂t n(Γ, x) is the particle density. j(Γ, x) is the current density of particles. (2)Energy conservation law: ∂H(Γ, x) ∂t + div(JH(Γ, x)) = 0. (15) H(Γ, x) is the energy density. JH(Γ, x) is the energy current density. (3)Momentum conservation law: ∂p(Γ, x) + div(T(Γ, x)) = 0. (16) ∂t T(Γ, x) is the momentum tensor. Here the functions appeared in the above conservation laws are the density of particles, (cid:88) N − n(Γ, x) = δ(qi x), (17) i=1 the momentum density, (cid:88) N − p(Γ, x) = piδ(qi x), (18) i=1 and the current of particles, (cid:88) N p − j(Γ, x; t) = mi δ(qi x). (19) i=1 In order to capture heat, we deﬁne the energydensity is given by  (cid:88)  (cid:88)    N p2 1 | − | − H(Γ, x) = 2mi + 2 V( qi qj ) δ(qi x). (20) i=1 j(cid:44)i For heat current, the energy current is deﬁned as 4 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: In

text: this

text: paper,

text: we

text: use

text: the

text: followin{g

text: n}otation

text: f{or

text: t}he

text: variables

text: of

text: position

text: and

text: momentum.

text: Γ

text: qN,

text: pN).

text: The

text: Hamiltonian

text: H

text: is

text: a

text: function

text: of

text: qi

text: and

text: pi

text: The

text: Hamiltonian

text: may

text: written

text: as

text: H

text: H(

text: qi

text: pi

text: Symmetry

text: which

text: the

text: system

text: possesses

text: is

text: important.

text: This

text: Hamiltonian

text: has

text: a

text: symmetry.

text: H(

text: qi

text: pi

text: H(

text: qi

text: pi

text: Time-reversal

text: symmetry

text: of

text: orbits

text: can

text: be

text: written

text: as

text: qi,R(t)

text: qi(

text: t),

text: pi,R(t)

text: pi(

text: t).

text: For

text: the

text: orbit

text: Γ(t),

text: the

text: time-reversed

text: orbit

text: is

text: written

text: as

text: Γ

text: (t).

text: R

text: This

text: system

text: has

text: three

text: conservation

text: laws.

text: number

text: conservation

text: law:

text: ∂n(Γ,

text: x)

text: div(j(Γ,

text: x))

text: ∂t

text: n(Γ,

text: x)

text: is

text: the

text: particle

text: density.

text: j(Γ,

text: x)

text: is

text: the

text: current

text: density

text: of

text: particles.

text: conservation

text: law:

text: ∂H(Γ,

text: x)

text: ∂t

text: div(JH(Γ,

text: x))

text: H(Γ,

text: x)

text: is

text: the

text: energy

text: density.

text: JH(Γ,

text: x)

text: is

text: the

text: energy

text: current

text: density.

text: conservation

text: law:

text: ∂p(Γ,

text: x)

text: div(T(Γ,

text: x))

text: ∂t

text: T(Γ,

text: x)

text: is

text: the

text: momentum

text: tensor.

text: Here

text: the

text: functions

text: appeared

text: in

text: the

text: above

text: conservation

text: laws

text: are

text: the

text: density

text: of

text: particles,

text: N

text: n(Γ,

text: x)

text: δ(qi

text: x),

text: the

text: momentum

text: density,

text: N

text: p(Γ,

text: x)

text: piδ(qi

text: x),

text: and

text: the

text: current

text: of

text: particles,

text: N

text: p

text: j(Γ,

text: x;

text: t)

text: mi

text: δ(qi

text: x).

text: In

text: order

text: to

text: capture

text: heat,

text: we

text: deﬁne

text: the

text: energydensity

text: is

text: given

text: by

text: N

text: H(Γ,

text: x)

text: V(

text: qi

text: qj

text: δ(qi

text: x).

text: For

text: heat

text: current,

text: the

text: energy

text: current

text: is

text: deﬁned

text: as

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: RESOLUTION OF INDECOMPOSABLE INTEGRAL FLOWS ON SIGNED GRAPHS BEIFANG CHEN, JUE WANG, AND THOMAS ZASLAVSKY Abstract. It is well known that each nonnegative integral ﬂow on a graph can be decom- posed into a sum of nonnegative graphic circuit ﬂows, which cannot be further decomposed into nonnegative integral sub-ﬂows. This is equivalent to saying that the indecomposable ﬂows on graphs are those graphic circuit ﬂows. Turning from graphs to signed graphs, the indecomposable ﬂows are much richer than those of unsigned graphs. This paper gives a complete description of indecomposable ﬂows on signed graphs from the viewpoint of resolution of singularities by means of double covering graphs. 1. Introduction A signed graph is a graph in which each edge is given either a positive or a negative sign. A real or integral ﬂow (or “circulation”) on an ordinary unsigned graph is a real- or integer-valued function on (oriented) edges such that the net inﬂow to each vertex is zero. Analogously, a real ﬂow on a signed graph is a real-valued function on (oriented) signed edges such that the net inﬂow to each vertex is zero, and an integral ﬂow, a concept introduced by Bouchet [?], is a ﬂow whose values are integers. The theory of ﬂows on ordinary graphs is the specialization of the signed-graph theory to the case in which all edges are positive. There are many reasons to be interested in integral ﬂows on graphs; important ones are their connection to integer programming through network optimization and their relation- ship to graph structure through the analysis of conformally indecomposable ﬂows, that is, integral ﬂows that cannot be decomposed as the sum of two integral ﬂows whose ﬂow values ≥ ≤ have the same sign on each edge (both 0 or both 0). It is well known, and an impor- tant observation in the theory of integral network ﬂows, that the indecomposable ﬂows are identical to the circuit ﬂows, which are ﬂows on circuits of the graphic matroid and which (in a suitable orientation of the graph) have value 1 on the edges of a graph circuit (i.e., a connected 2-regular subgraph) and 0 elsewhere. The extension of the theory of indecompos- able integral ﬂows to signed graphs by Chen and Wang [?], carried out by an algorithmic method, led to the remarkable discovery that, besides the anticipated circuit ﬂows, which are already more complicated in signed graphs than in ordinary graphs, there are many “strange” indecomposable ﬂows with elaborate self-intersection structure not describable by circuits of the signed graph. Chen and Wang obtained a classiﬁcation of indecomposable ﬂows by means of their algorithm. Date: May 29, 2020. 2000 Mathematics Subject Classiﬁcation. Primary 05C22; Secondary 05C20, 05C21, 05C38. Key words and phrases. Signed graph, double covering graph, sesqui-Eulerian signed graph, prime sesqui- Eulerian signed graph, sesqui-Eulerian circle-tree, indecomposable integral ﬂow. The research of the ﬁrst author was supported by RGC Competitive Earmarked Research Grants 600608, 600409, and 600811. 1 ##LTLine##

text: RESOLUTION

text: OF

text: INDECOMPOSABLE

text: INTEGRAL

text: FLOWS

text: ON

text: SIGNED

text: GRAPHS

text: BEIFANG

text: CHEN,

text: JUE

text: WANG,

text: AND

text: THOMAS

text: ZASLAVSKY

text: Abstract.

text: It

label: abstract

text: is

text: well

text: known

text: that

text: each

text: nonnegative

text: integral

text: ﬂow

text: on

text: a

text: graph

text: can

text: be

text: decom-

text: posed

text: into

text: a

text: sum

text: of

text: nonnegative

text: graphic

text: circuit

text: ﬂows,

text: which

text: cannot

text: be

text: further

text: decomposed

text: into

text: nonnegative

text: integral

text: sub-ﬂows.

text: This

text: is

text: equivalent

text: to

text: saying

text: that

text: the

text: indecomposable

text: ﬂows

text: on

text: graphs

text: are

text: those

text: graphic

text: circuit

text: ﬂows.

text: Turning

text: from

text: graphs

text: to

text: signed

text: graphs,

text: the

text: indecomposable

text: ﬂows

text: are

text: much

text: richer

text: than

text: those

text: of

text: unsigned

text: graphs.

text: This

text: paper

text: gives

text: a

text: complete

text: description

text: of

text: indecomposable

text: ﬂows

text: on

text: signed

text: graphs

text: from

text: the

text: viewpoint

text: of

text: resolution

text: of

text: singularities

text: by

text: means

text: of

text: double

text: covering

text: graphs.

text: Introduction

text: A

text: signed

text: graph

text: is

text: a

text: graph

text: in

text: which

text: each

text: edge

text: is

text: given

text: either

text: a

text: positive

text: or

text: a

text: negative

text: sign.

text: A

text: real

text: or

text: integral

text: ﬂow

text: (or

text: “circulation”)

text: on

text: an

text: ordinary

text: unsigned

text: graph

text: is

text: a

text: real-

text: or

text: integer-valued

text: function

text: on

text: (oriented)

text: edges

text: such

text: that

text: the

text: net

text: inﬂow

text: to

text: each

text: vertex

text: is

text: zero.

text: Analogously,

text: a

text: real

text: ﬂow

text: on

text: a

text: signed

text: graph

text: is

text: a

text: real-valued

text: function

text: on

text: (oriented)

text: signed

text: edges

text: such

text: that

text: the

text: net

text: inﬂow

text: to

text: each

text: vertex

text: is

text: zero,

text: and

text: an

text: integral

text: ﬂow,

text: a

text: concept

text: introduced

text: by

text: Bouchet

text: is

text: a

text: ﬂow

text: whose

text: values

text: are

text: integers.

text: The

text: theory

text: of

text: ﬂows

text: on

text: ordinary

text: graphs

text: is

text: the

text: specialization

text: of

text: the

text: signed-graph

text: theory

text: to

text: the

text: case

text: in

text: which

text: all

text: edges

text: are

text: positive.

text: There

text: are

text: many

text: reasons

text: to

text: be

text: interested

text: in

text: integral

text: ﬂows

text: on

text: graphs;

text: important

text: ones

text: are

text: their

text: connection

text: to

text: integer

text: programming

text: through

text: network

text: optimization

text: and

text: their

text: relation-

text: ship

text: to

text: graph

text: structure

text: through

text: the

text: analysis

text: of

text: conformally

text: indecomposable

text: ﬂows,

text: that

text: is,

text: integral

text: ﬂows

text: that

text: cannot

text: be

text: decomposed

text: as

text: the

text: sum

text: of

text: two

text: integral

text: ﬂows

text: whose

text: ﬂow

text: values

text: have

text: the

text: same

text: sign

text: on

text: each

text: edge

text: (both

text: or

text: both

text: It

text: is

text: well

text: known,

text: and

text: an

text: impor-

text: tant

text: observation

text: in

text: the

text: theory

text: of

text: integral

text: network

text: ﬂows,

text: that

text: the

text: indecomposable

text: ﬂows

text: are

text: identical

text: to

text: the

text: circuit

text: ﬂows,

text: which

text: are

text: ﬂows

text: on

text: circuits

text: of

text: the

text: graphic

text: matroid

text: and

text: which

text: (in

text: a

text: suitable

text: orientation

text: of

text: the

text: graph)

text: have

text: value

text: on

text: the

text: edges

text: of

text: a

text: graph

text: circuit

text: (i.e.,

text: a

text: connected

text: subgraph)

text: and

text: elsewhere.

text: The

text: extension

text: of

text: the

text: theory

text: of

text: indecompos-

text: able

text: integral

text: ﬂows

text: to

text: signed

text: graphs

text: by

text: Chen

text: and

text: Wang

text: carried

text: out

text: by

text: an

text: algorithmic

text: method,

text: led

text: to

text: the

text: remarkable

text: discovery

text: that,

text: besides

text: the

text: anticipated

text: circuit

text: ﬂows,

text: which

text: are

text: already

text: more

text: complicated

text: in

text: signed

text: graphs

text: than

text: in

text: ordinary

text: graphs,

text: there

text: are

text: many

text: “strange”

text: indecomposable

text: ﬂows

text: with

text: elaborate

text: self-intersection

text: structure

text: not

text: describable

text: by

text: circuits

text: of

text: the

text: signed

text: graph.

text: Chen

text: and

text: Wang

text: obtained

text: a

text: classiﬁcation

text: of

text: indecomposable

text: ﬂows

text: by

text: means

text: of

text: their

text: algorithm.

text: Date:

text: May

text: Mathematics

text: Subject

text: Classiﬁcation.

text: Primary

text: Secondary

text: Key

text: words

text: and

text: phrases.

text: Signed

text: graph,

text: double

text: covering

text: graph,

text: sesqui-Eulerian

text: signed

text: graph,

text: prime

text: sesqui-

text: Eulerian

text: signed

text: graph,

text: sesqui-Eulerian

text: circle-tree,

text: indecomposable

text: integral

text: ﬂow.

text: The

text: research

text: of

text: the

text: ﬁrst

text: author

text: was

text: supported

text: by

text: RGC

text: Competitive

text: Earmarked

text: Research

text: Grants

text: and

text: ##LTLine##