Correlated Markov Quantum Walks

Alain Joye

Description

Correlated Markov Quantum Walks Eman Hamza? Alain Joye†‡ Abstract We consider the discrete time unitary dynamics given by a quantum walk on Zd per- formed by a particle with internal degree of freedom, called coin state, according to the following iterated rule: a unitary update of the coin state takes place, followed by a shift on the lattice, conditioned on the coin state of the particle. We study the large time behavior of the quantum mechanical probability distribution of the position observable in Zd for random updates of the coin states of the following form. The random sequences of unitary updates are given by a site dependent function of a Markov chain in time, with the following properties: on each site, they share the same stationnary Markovian distribution and, for each fixed time, they form a deterministic periodic pattern on the lattice. We prove a Feynman-Kac formula to express the characteristic function of the averaged distribution over the randomness at time n in terms of the nth power of an operator M . By analyzing the spectrum of M , we show that this distribution posesses a drift proportional to the time and its centered counterpart displays a diffusive behavior with a diffusion matrix we compute. Moderate and large deviations principles are also proven to hold for the averaged distribution and the limit of the suitably rescaled corresponding characteristic function is shown to satisfy a diffusion equation. An example of random updates for which the analysis of the distribution can be per- formed without averaging is worked out.

• markovian


• unitary


• characteristic function


• all coin variables


• time behavior


• ?0 ?


• distribution w·


• quantum walks

Sujets

• Cairo University
• Agence nationale de la recherche
• Markov process
• Unitary
• Characteristic function
• multiplication

Informations

• Publié par: pefav
• Nombre de lectures: 18
• Langue: English

Extrait

CorrelatedMarkovQuantumWalks

EmanHamza
∗
AlainJoye
†‡

Abstract
Weconsiderthediscretetimeunitarydynamicsgivenbyaquantumwalkon
Z
d
per-
formedbyaparticlewithinternaldegreeoffreedom,calledcoinstate,accordingtothe
followingiteratedrule:aunitaryupdateofthecoinstatetakesplace,followedbyashifton
thelattice,conditionedonthecoinstateoftheparticle.Westudythelargetimebehavior
ofthequantummechanicalprobabilitydistributionofthepositionobservablein
Z
d
for
randomupdatesofthecoinstatesofthefollowingform.Therandomsequencesofunitary
updatesaregivenbyasitedependentfunctionofaMarkovchainintime,withthefollowing
properties:oneachsite,theysharethesamestationnaryMarkoviandistributionand,for
eachfixedtime,theyformadeterministicperiodicpatternonthelattice.
WeproveaFeynman-Kacformulatoexpressthecharacteristicfunctionoftheaveraged
distributionovertherandomnessattime
n
intermsofthe
n
thpowerofanoperator
M
.By
analyzingthespectrumof
M
,weshowthatthisdistributionposessesadriftproportionalto
thetimeanditscenteredcounterpartdisplaysadiffusivebehaviorwithadiffusionmatrixwe
compute.Moderateandlargedeviationsprinciplesarealsoproventoholdfortheaveraged
distributionandthelimitofthesuitablyrescaledcorrespondingcharacteristicfunctionis
showntosatisfyadiffusionequation.
Anexampleofrandomupdatesforwhichtheanalysisofthedistributioncanbeper-
formedwithoutaveragingisworkedout.Therandomdistributiondisplaysadeterministic
driftproportionaltotimeanditscenteredcounterpartgivesrisetoarandomdiffusion
matrixwhoselawwecompute.Wecompletethepicturebypresentinganuncorrelated
example.

1Introduction
Quantumwalksaresimplemodelsofdiscretetimequantumevolutiontakingplaceona
d
-dimensionallatticewhoseimplementationyieldsaunitarydiscretedynamicalsystemon
aHilbertspace.Thedynamicsdescribesthemotionofaquantumparticlewithinternal
degreeoffreedomonaninfinite
d
-dimensionallatticeaccordingtothefollowingrules.The
one-stepmotionconsistsinanupdateoftheinternaldegreeoffreedombymeansofa
unitarytransformintherelevantpartoftheHilbertspace,followedbyafiniterangeshift
onthelattice,conditionedontheinternaldegreeoffreedomoftheparticle.Duetotheir
∗
DepartmentofPhysics,FacultyofScience,CairoUniversity,Cairo12613,Egypt
†
UJF-Grenoble1,CNRSInstitutFourierUMR5582,Grenoble,38402,France
‡
PartiallysupportedbytheAgenceNationaledelaRecherche,grantANR-09-BLAN-0098-01

similaritywithclassicalrandomwalksonalattice,quantumwalksconstructedthiswayare
oftenconsideredastheirquantumanalogs.Inthiscontext,thespaceoftheinternaldegree
offreedomiscalled
coinspace
,thedegreeoffreedomisthe
coinstate
andtheunitary
operatorsperformingtheupdateare
coinmatrices
.
Quantumwalkshavebecomequitepopularinthequantumcomputingcommunityinthe
recentyears,duetotheroletheyplayincomputerscience,andinparticularforquantum
searchalgorithms.Seeforexample[33],[4],[26],[28],[39],[5],[32]andinthereview
[36].Also,quantumwalksareusedaseffectivedynamicsofquantumsystemsincertain
asymptoticregimes;see
e.g.
[14],[1],[33],[31],[11],[35],forafewmodelsofthistype,and
[7],[10],[15],[17],[6]fortheirmathematicalanalysis.Moreover,quantumwalkdynamics
havebeenshowntodescribeexperimentalrealityforsystemsofcoldatomstrappedin
suitablymonitoredopticallattices[24],andionscaughtinmonitoredPaultraps[42].
Theliteraturecontainsseveralvariantsofthequantumdynamicsonalatticeasde-
scribedabove,whichmayincludedecoherenceeffectsand/ormoregeneralgraph,see
e.g.
thereviewsandpapers[4],[26],[3],[8].Inthiswork,weconsiderthecasewheretheevo-
lutionofthewalkerisunitary,andwheretheunderlyinglatticeis
Z
d
withcoinspaceof
dimension2
d
,whichis,inasense,theclosesttotheclassicalrandomwalk.
Weareinterestedinthelongtimebehaviorofquantummechanicalexpectationvalues
ofobservablesthatarenon-trivialonthelatticeonly,
i.e.
thatdonotdependonthe
internaldegreeoffreedomofthequantumwalker.Equivalently,thisamountstostudyinga
familyofrandomvectors
X
n
onthelattice
Z
d
,indexedbythediscretetimevariable,with
probabilitylaws
P
(
X
n
=
k
)=
W
k
(
n
)definedbytheprescriptionsofquantummechanics.
Theinitialstateofthequantumwalkerisdescribedbyadensitymatrix.
Asiswellknown,whentheunitaryupdateofthecoinvariableisperformedateachtime
stepbymeansofthesamecoinmatrix,thisleadstoaballisticbehavioroftheexpectationof
thepositionvariablecharacterizedby
E
W
(
n
)
(
X
n
)
'
nV
when
n
islarge,forsomevector
V
,
andbyfluctuationsofthecenteredrandomvariable
X
n
−
nV
oforder
n
,see
e.g.
[28].These
featuresarecharacteristicofthecoherentnatureofthequantumdynamicsinhomogeneous
orperiodicmedia.
Thecasewherethecoinmatricesusedtoupdatethecoinvariabledependonthetime
stepinarandomfashion,asituationof
temporaldisorder
,isdealtwithin[21],seealso
[3].Allcoinvariablesareupdatedsimultaneouslyandinthesameway,independentlyof
thepositiononthelattice.Thisyieldsarandomdistribution
W
∙
ω
(
n
),correspondingto
therandomvariable
X
nω
which,oncecenteredandaveragedoverthedisorder,displaysa
diffusivebehaviorinthelongtimelimit.
Ifthecoinmatricesdependonthesiteofthelattice
Z
d
butnotontime,
i.e.
acase
of
spatialdisorder
,oneexpectsdynamicallocalization,characterizedbyfinitevaluesofall
moments,uniformlyboundedintime
n
,andfor(almost)allrealizations.Indimension
d
=1,thiswasprovenin[20]forcertainsetsofrandomcoinmatrices,whichwerefurther
generalizedin[2].Seealso[27],[38]forrelatedaspects.Thehigherdimensionalcaseis
.nepoThesituationaddressedhereisthatofcorrelated
spatio-temporaldisorder
.Weconsider
randomcoinmatriceswhichdependbothontimeandspaceinthefollowingway:The
randomcoinmatrixatsite
x
∈
Z
d
andtime
n
∈
N
isgivenby
C
nω
(
x
)=
σ
x
(
ω
(
n
))
,
where

2

{
ω
(
j
)
}
j
∈
N
isatemporalstationaryMarkovchainonafinitesetΩofunitarymatriceson
C
2
d
,
and
Z
d
3
x
→
σ
x
isagivenrepresentationof
Z
d
intermsofmeasureinvariantbijectionson
Ω.Inparticular,
σ
0
=Id,theidentityonΩ,andΓ=
{
y
∈
Z
d
s.t.
σ
y
=Id
}
formsaperiodic
sub-latticeof
Z
d
.Therefore,ateachsite
x
∈
Z
d
,thesequence
{
C
jω
(
x
)
}
j
∈
N
isMarkovian
withadistributionindependentof
x
,andateachtime
n
∈
N
,theset
{
C
nω
(
x
)
,x
∈
Z
d
}
isΓ-periodic.Thisisanaturalgeneralizationofthecasestudiedin[21]whichdisplaysa
deterministicnontrivialperiodicstructureinthespatialpatternsofrandomcoinmatrices
ateachtimestep.
Thissetupisananalogoftheoneaddressedin[34],[22],[18],wherethedynamics
isgeneratedbyaquantumHamiltonianwithatimedependentpotentialgeneratedbya
randomprocess.Forquantumwalks,theroleoftherandomtimedependentpotentialis
playedbytherandomcoinoperatorswhereastheroleofthedeterministickineticenergyis
playedbytheshift.
Weaddresstheproblembyananalysisofthelarge
n
behaviorofthecharacteristic
functionofthedistribution
w
∙
(
n
),Φ
n
(
y
)=
E
w
(
n
)
(
e
iyX
n
),where
w
∙
(
n
)=
E
(
W
∙
ω
(
n
))isthe
averagedquantummechanicaldistributionon
Z
d
,withinitialcondition
ρ
0
,adensitymatrix
on
l
2
(
Z
d
)
⊗
C
2
d
.Byadaptingthestrategyof[22],[18],inspiredby[34],toourdiscretetime
unitarysetup,wefirstestablisha
Feynman-Kac
typeformulatoexpress
w
∙
(
n
)intermsof
(somematrixelement)ofthe
n
thpowerofacontractionoperator
M
actingonanextended
Hilbertspacewhichinvolvesaspaceof(density)matricesandtheprobabilityspaceofcoin
matrices.Then,weanalyzethespectralpropertiesof
M
,makinguseoftheperiodicity
andinvariancepropertiesof
σ
x
whichyieldafiberdecompositionofageneralizedFourier
transformof
M
.Inturn,thisallowsustoprovideadetaileddescriptiono
√
fthelarge
n
behaviorofthecharacteristicfunctionΦ
n
(
y
)inthediffusiveregime
y
→
y/n
,andat
y
fixed,intermsofthespectraldataof
M
andtheirperturbativebehavior.
Theforegoingisthemaintechnicalresultofthepaper,fromwhichseveralconsequences
canbedrawn,byargumentssimilartothoseusedin[21].Undernaturalassumptionsonthe
spectrumof
M
,theaverageddistribution
w
∙
(
n
)displaysadi@