Quantum walks on random lattices Diusion localization and the absence of parametric quantum speed-up Rostislav Duda1 2 3Moein N. Ivaki1 2Isac Sahlberg1 2Kim P oyh onen1 2and Teemu Ojanen1 2

2025-04-29 0 0 4.18MB 13 页 10玖币

侵权投诉

Quantum walks on random lattices: Diﬀusion, localization and the absence of

parametric quantum speed-up

Rostislav Duda,1, 2, 3 Moein N. Ivaki,1, 2 Isac Sahlberg,1, 2 Kim P¨oyh¨onen,1, 2 and Teemu Ojanen1, 2, ∗

1Computational Physics Laboratory, Physics Unit,

Faculty of Engineering and Natural Sciences, Tampere University, FI-33014 Tampere, Finland

2Helsinki Institute of Physics, FI-00014 University of Helsinki, Finland

3Department of Applied Physics, Aalto University, FI-00076 Aalto, Finland

Discrete-time quantum walks, quantum generalizations of classical random walks, provide a

framework for quantum information processing, quantum algorithms and quantum simulation of

condensed matter systems. The key property of quantum walks, which lies at the heart of their

quantum information applications, is the possibility for a parametric quantum speed-up in propa-

gation compared to classical random walks. In this work we study propagation of quantum walks

on percolation-generated two-dimensional random lattices. In large-scale simulations of topological

and trivial split-step walks, we identify distinct pre-diﬀusive and diﬀusive behaviors at diﬀerent

time scales. Importantly, we show that even arbitrarily weak concentrations of randomly removed

lattice sites give rise to a complete breakdown of the superdiﬀusive quantum speed-up, reducing the

motion to ordinary diﬀusion. By increasing the randomness, quantum walks eventually stop spread-

ing due to Anderson localization. Near the localization threshold, we ﬁnd that the quantum walks

become subdiﬀusive. The fragility of quantum speed-up implies dramatic limitations for quantum

information applications of quantum walks on random geometries and graphs.

I. INTRODUCTION

The concept of a random walk occupies a central role

in physics, mathematics, statistics and information pro-

cessing. In the looming quantum information era, it is

no surprise that quantum-mechanical generalizations of

the random walk, quantum walks, have become a sub-

ject of broad interest for physicists with various special-

izations [1–7]. Combining ideas from quantum informa-

tion processing to condensed matter physics and beyond,

discrete-time quantum walks (DTQW) have been pro-

posed as a general framework for a variety of quantum al-

gorithms and studying condensed-matter phenomena [8–

18]. The wide range of possible applications of quantum

walks include quantum computing, quantum cryptogra-

phy, quantum search algorithms on the quantum infor-

mation side and a simulation of fundamental properties

of quantum phases of matter on the condensed-matter

side, some of which have already seen experimental real-

ization [19–26].

The main attractive feature of quantum walks is the

possibility of a parametric quantum speed-up of propa-

gation relative to a classical random walk [27–30]. While

random walks in general give rise to a diﬀusive motion,

characterized by a mean square displacement (MSD)

∆2X∝twhich grows linearly in the number of time

steps t, quantum walks on regular lattices and graphs

may reach a quadratic speed-up ∆2X∝t2corresponding

to a ballistic spreading. The quadratic quantum speed-

up can be harnessed, for example, to realize a version of

the celebrated Grover’s search algorithm [31,32] with a

square root reduction in the execution time compared to

∗Email: teemu.ojanen@tuni.ﬁ

FIG. 1. Quantum walks in random geometry. a): Single

realization of percolation lattices where each site of a square

lattice is present with probability p(ﬁgure corresponds to

p= 0.75). b): Probability distribution of a quantum walk

which started at the origin at t= 0 and propagated t=

256 steps on a single realization of a p= 0.75 lattice. Color

scale logarithmic to improve visibility. c): Phase diagram of

the asymptotic long-time motion of quantum walks on the

studied lattices. The three regions, in the order of decreasing

randomness, correspond to localized (α= 0), subdiﬀusive

(α < 1) and diﬀusive (α= 1) phase. Superdiﬀusive behavior

is restricted to a pristine square lattice with p= 1, where

motion is ballistic.

classical algorithms [33–35]. Thus, it is a matter of cen-

tral importance for applications of quantum walks to un-

derstand under what circumstances quantum walks can

maintain a speed-up compared to the standard diﬀusion.

In particular, can parametric quantum speed-up persist

in irregular or random structures? If so, quantum-walk-

based algorithms could be employed, for example, to

arXiv:2210.05310v1 [quant-ph] 11 Oct 2022

speed up element search in large irregular and random

structures.

In this work, we study the propagation of quantum

walks in random lattice geometries through the lens

of condensed matter physics. We consider a family of

DTQWs [36,37] on inﬁnite random lattices generated by

site percolation, as illustrated in Figs. 1a) and b). Mo-

tivated by the fact that topological states of matter are

generically more robust to random perturbations, we im-

plement split-step quantum walks with a tuneable topo-

logical invariant and explore the spreading of topological

and trivial quantum walks. By carrying out large-scale

numerical simulations up to t= 104time steps, we ﬁnd

that pre-diﬀusive and transient kinetics dominate at in-

termediate time scales tdecay determined by the degree

of randomness. In the long-time limit, we observe that

the conﬁguration-averaged MSD follows the generalized

diﬀusion Ansatz ∆2X∝tα, and extract the exponent α.

Our ﬁndings are summarized in Fig. 1c), which indicates

that even weak randomness will give rise to the break-

down of the superdiﬀusive quantum speed-up. With in-

creasing random dilution, the quantum walks will even-

tually halt due to Anderson lozalization at the critical

density pc. Moreover, in the vicinity of pc, the system

becomes subdiﬀusive. As discussed below, the absence

of superdiﬀusion implies severe limitations for obtaining

quantum speed-up in quantum-walk-based applications

on random lattices and graphs.

II. QUANTUM WALKS ON RANDOM

LATTICES

A. Topological walks on regular lattice

Before discussing random geometries, we ﬁrst explore

the properties of the studied topological split-steps walk

on a regular lattice. In general, a DTQW on a square

lattice is deﬁned for a point-like walker with an internal

n-level degree of freedom referred to as a quantum coin.

The quantum state of a walker belongs to a Hilbert space

H=Z2⊗Cnwith a basis |x, yi⊗|si, where |x, yirefers to

the position states and |sito the internal coin states. In

analogy to a random walk, a quantum walk is deﬁned as

a sequence of quantum coin operations and conditional

translations depending on the coin state. A walker is

initially located at the origin, and a single step of a walk

is generated by a unitary ˆ

Uwhich propagates the walker

state as |ψ(t+ 1)i=ˆ

U|ψ(t)i. Hereinafter we will assume

a spin-1

2quantum walk with n= 2. To deﬁne the unitary,

one needs a translation operator

T(δ) = X

r∈Z2h|↑i h↑| ⊗ |r+δi hr|+|↓i h↓| ⊗ |r−δi hr|i,

which shifts the position of a walker by the vector ±δ

depending on the coin state, and a coin operator

R(θ) = e−iθ

2ˆσy.

Following Ref. [36], by introducing the primitive shift

vectors δ1= (1,1), δ2= (0,1) and δ3= (1,0), we deﬁne

a split-step unitary as

U2D(θ1, θ2) = ˆ

T(δ3)ˆ

R(θ1)ˆ

T(δ2)ˆ

R(θ2)ˆ

T(δ1)ˆ

R(θ1).(1)

This unitary is parameterized by two coin angles, θ1

and θ2, and a single step of the walk consists of three

sequential applications of combined spin ﬂip and shift

operations, as illustrated in Fig. 2a). The unitary (1)

can be represented as ˆ

U2D =e−iˆ

Heff , where the eﬀective

Hamiltonian in the momentum space is deﬁned as

Heﬀ =Zπ

−π

dkhE(k)n(k)·ˆσi⊗ |ki hk|.(2)

Here |kidenotes the Fourier transformed position vec-

tor |ri. While the expressions for E(k) and n(k), derived

in Appendix A, are not particularly illuminating, the ef-

fective Hamiltonian can be analyzed with the tools of

topological condensed matter theory to gain further in-

sight on related quantum walks. In particular, the spec-

trum of the eﬀective Hamiltonian is characterized by a

topological index, the Chern number, which can be ob-

tained by

C=1

4πZΩ

n(k)·(∂kxn(k)×∂kyn(k)) dk,(3)

where Ω denotes a torus (kx, ky)∈−π

2,π

2×−π

2,π

2.

In Fig. 2b) we have presented the topological phase di-

agram in terms of the coin parameters. A substantial

fraction of the coin’s parameter space supports non-zero

Chern numbers, a primary motivation to study the walk

protocol (1). As understood during the last four decades

in condensed matter physics, topological states of mat-

ter are extraordinarily robust to disorder and Anderson

localization. Electronic bands in integer quantum Hall

systems, characterized by nonzero Chern numbers, are

particularly striking examples of this. It is well-known

by now that an arbitrarily weak randomness may lead

to Anderson localization in 1d and 2d systems [38]. This

means that with exponential accuracy, all the eigenstates

of a Hamiltonian and the corresponding time-evolution

unitary have a ﬁnite spatial support. Correspondingly,

quantum walks deﬁned by a unitary incorporating eﬀects

of disorder similarly give rise to walks that are expo-

nentially conﬁned to their initial position. However, as

long as a system supports a nonzero Chern number, it is

guaranteed to support at least some extended states [38].

What this means for quantum walks is that, while proto-

cols with trivial topology may enable extended walks in

the presence of weak disorder, the topologically nontrivial

protocols are always guaranteed to do so. Qualitatively,

one expects topologically nontrivial systems to tolerate

larger random perturbations before localizing. Since our

main focus in this work is on random systems, it is natu-

ral to focus on topological split-step protocols. The prop-

agation of a topological walk with ﬁnite Chern number

FIG. 2. Topologically protected three-step quantum walk on

a square lattice. a): The unitary of the split-step walk con-

sists of three coin operations followed by translations in three

diﬀerent directions indicated by the arrows. b): Topologi-

cal phase diagram of quantum walks as a function of the two

coin parameters θ1, θ2. Colours correspond to diﬀerent Chern

numbers C= 0,1,−1. c): Probability distribution of a topo-

logically nontrivial walk (θ1, θ2)=(π

2,π

2) at t= 256. To

enhance visibility, the colour scale varies linearly in kψk1/2.

on a square lattice is illustrated in Fig. 2c). In Appendix

C, we also discuss two-step quantum walks which support

topological Floquet-type phases. As shown below, these

walks exhibit qualitatively similar properties on random

lattices.

B. Split-step walks on random lattices

In the condensed-matter setting, it has been recognized

for over half a century that any irregularities in a crystal

lattice typically have dramatic eﬀects on particle dynam-

ics and transport properties. In particular, random disor-

der reduces a ballistic quantum propagation to diﬀusive

motion. For quantum walks this implies that small ﬂuc-

tuations in the implementation of the quantum walk pro-

tocol could wipe out the quantum speed-up. This eﬀect

has also been studied in quantum walks by incorporating

various sources of randomness in position and coin sub-

spaces. [39–47]. Even worse, disorder can lead to the An-

derson localization of all wave functions, so the spreading

of the quantum walk could even stop altogether [48–52].

Thus, random irregularities could turn the quantum ad-

vantage of quantum walks into a quantum handicap.

To study the fate of quantum walks on random ge-

ometries, we now generalize quantum walk protocols to

random lattices. We consider an extensively-studied

paradigm of random lattices, the site percolation on a

square lattice [53]. The ensemble of percolation geome-

tries is generated by assigning a probability pfor each

site of a square lattice to be independently populated.

Equivalently, each site is removed with probability 1 −p.

At low p, a single realization consists of a collection of

disconnected clusters, whereas at high pclose to unity,

the lattice resembles a square lattice with rare randomly

missing sites. At the percolation threshold pperc ≈0.59,

the system undergoes a geometric transition above which

the system contains an inﬁnite cluster connected by pop-

ulated nearest-neighbour lattice sites [54]. A ﬁnite snap-

shot of a single realization of the p= 0.75 ensemble is

depicted in Fig. 1 a).

FIG. 3. Quantum walks on lattices with randomly missing

sites. a): Walker located in the center cannot hop on miss-

ing sites. The translations to prohibited sites, indicated by

red color, are substituted by spin ﬂips which reﬂect the walk

to the opposite direction. b)-d): Probability distribution of

quantum walks on a single realization of random lattices with

p= 0.9, p= 0.8, p= 0.7 after t= 256 time steps, shown in

logarithmic scale for improved visibility.

As illustrated in Fig. 3a), to generalize the proto-

col (1) to percolation lattices, it is necessary to modify

translation operators when a walker is encountering ab-

sent sites. We implement a prescription where, instead

of carrying out translation from site rto a missing site

at r+δ, the translation is omitted but the coin state of

a walker is ﬂipped to the opposite state |si→|¯

si. This

will prohibit the walker from entering the missing sites,

eﬀectively reﬂecting it to the opposite direction. A simi-

lar procedure has been employed in generating reﬂecting

boundaries and boundary modes in topological quantum

walks [36]. Thus, this prescription results in a random

walk-generating unitary where the translation operator

Tis replaced by a spin-ﬂip operation ˆ

Swhen encoun-

tering randomly missing site. This construction, derived

in detail in Appendix B, preserves the total probability

associated with the wave function of the quantum walk.

Examples of quantum walks for speciﬁc realizations of

random lattices are illustrated in Figs. 3b)-d). The same

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Quantumwalksonrandomlattices:Diusion,localizationandtheabsenceofparametricquantumspeed-upRostislavDuda,1,2,3MoeinN.Ivaki,1,2IsacSahlberg,1,2KimPoyhonen,1,2andTeemuOjanen1,2,1ComputationalPhysicsLaboratory,PhysicsUnit,FacultyofEngineeringandNaturalSciences,TampereUniversity,FI-33014Tampere,Finlan...

展开>> 收起<<

Quantum walks on random lattices Diusion localization and the absence of parametric quantum speed-up Rostislav Duda1 2 3Moein N. Ivaki1 2Isac Sahlberg1 2Kim P oyh onen1 2and Teemu Ojanen1 2.pdf

共13页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Quantum walks on random lattices Diusion localization and the absence of parametric quantum speed-up Rostislav Duda1 2 3Moein N. Ivaki1 2Isac Sahlberg1 2Kim P oyh onen1 2and Teemu Ojanen1 2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: