Quantum spatial search with electric potential long-time dynamics and robustness to noise Thibault Fredon1Julien Zylberman2Pablo Arnault1and Fabrice Debbasch2

2025-04-29 0 0 856.8KB 8 页 10玖币

侵权投诉

Quantum spatial search with electric potential : long-time dynamics and robustness

to noise

Thibault Fredon,1, ∗Julien Zylberman,2Pablo Arnault,1and Fabrice Debbasch2

1Université Paris-Saclay, CNRS, ENS Paris-Saclay, INRIA,

Laboratoire Méthodes Formelles, 91190 Gif-sur-Yvette, France

2Sorbonne Université, Observatoire de Paris, Université PSL, CNRS, LERMA, 75005 Paris, France

We present various results on the scheme introduced in Ref. [1], which is a quantum spatial-

search algorithm on a two-dimensional (2D) square spatial grid, realized with a 2D Dirac discrete-

time quantum walk (DQW) coupled to a Coulomb electric ﬁeld centered on the marked node. In

such a walk, the electric term acts as the oracle of the algorithm, and the free walk (i.e., without

electric term) acts as the “diﬀusion” part, as it is called in Grover’s algorithm. The results are

the following. First, we run simulations of this electric Dirac DQW during longer times than

explored in Ref. [1], and observe that there is a second localization peak around the node marked

by the oracle, reached in a time O(√N), where Nis the number of nodes of the 2D grid, with a

localization probability scaling as O(1/ln N). This matches the state-of-the-art 2D DQW search

algorithms before amplitude ampliﬁcation [2]. We then study the eﬀect of adding noise on the

Coulomb potential, and observe that the walk, especially the second localization peak, is highly

robust to spatial noise, more modestly robust to spatiotemporal noise, and that the ﬁrst localization

peak is even highly robust to spatiotemporal noise.

I. INTRODUCTION

Discrete-time quantum walks (DQWs) correspond to

the one-particle sector of quantum cellular automata

[3,4]. They can simulate numerous physical systems,

ranging from particles in arbitrary Yang-Mills gauge

ﬁelds [5] and massless Dirac fermions near black holes

[6], to charged quantum ﬂuids [7], see also Refs. [8–18]

for other physics-oriented applications.

Moreover, DQWs can be seen as quantum analogs of

classical random walks (CRWs) [19], and can be used

to build spatial-search algorithms that outperform [20]

those built with CRWs. Continuous-time quantum walks

can also be used for such a purpose [21]. In 3spatial di-

mensions, DQW-based algorithms [20,21] ﬁnd the loca-

tion of a marked node with a constant localization prob-

ability1after O(√N)time steps, with Nthe number

of nodes of the three-dimensional grid, and this is ex-

actly the bound reached by Grover’s algorithm [22–27].

However, no two-dimensional (2D) QW proposed so far

reaches Grover’s lower bound.

The state-of-the-art result using a 2D DQW was ob-

tained by Tulsi in Ref. [2]: Tulsi’s algorithm ﬁnds a

marked node with a localization probability scaling as

O(1/ln N)in O(√N)time steps, where Nis the total

number of nodes. To reach a probability independent

of N, several amplitude ampliﬁcation time steps have to

be performed after the quantum-walk part. These extra

time steps are Grover’s algorithm time steps, see Ref.

[28]. Taking the amplitude ampliﬁcation into account,

Tulsi’s algorithm reaches an O(1) localization probabil-

ity after O(√Nln N)time steps.

Other schemes of 2D DQW for spatial search have fol-

∗thibault.fredon@ens-paris-saclay.fr

1We call “localization probability” the probability to be at the

marked node, or nodes if there are several of them.

lowed, such as the one by Roget et al. in Ref. [29], where

the 2D DQW simulates a massless Dirac fermion on a

grid with defects. This scheme is inspired by physics,

and it reaches Tulsi’s bound using a coin of dimension 2

instead of 4. Recently, Zylberman and Debbasch intro-

duced in Ref. [1] a new DQW scheme for 2D quantum

spatial search. This scheme implements quantum search

by simulating the dynamics of a massless Dirac fermion

in a Coulomb electric ﬁeld centered on the nodes to be

found. We call this DQW “electric Dirac DQW”2. In this

walk, the oracle is a position-dependent phase.

This oracle is diagonal in the position basis and can be

eﬃciently implemented on nqubits up to an error using

O(1

)primitive quantum gates [30]. This total number of

quantum gates is independant of nand makes possible

the implementation of the oracle on current Noisy Inter-

mediate Scale Quantum (NISQ) devices and on future

universal quantum computers.

Note also that the algorithm proposed in Ref. [1] con-

stitues actually a paradigm change in the construction of

search algorithms, because it is based on the physically

motivated idea that the position of the marked node can

be encoded in the shape of an artiﬁcial force ﬁeld which

acts on the quantum walker.

One of the main results of Zylberman and Debbasch’s

paper [1] is a localization probability which displays a

2We call “Dirac DQW” a DQW that has as a continuum limit

the Dirac equation. Throughout this paper, the terminology

“electric Dirac DQW” will always refer to a Dirac DQW coupled

to a Coulomb electric potential, unless otherwise stated. In the

literature other types of electric potentials have been considered.

The reason why we do not specify the term “Coulomb” in the

present denomination “electric Dirac DQW” is because the idea

we want to convey is that the marked node is encoded in the

shape of the electric potential, but the precise form of the electric

potential, e.g., here, the fact that it is a Coulomb potential, may

not be that relevant.

arXiv:2210.13920v1 [quant-ph] 25 Oct 2022

maximum in ON→∞(1) time steps, the localization prob-

ability scaling as O(1/N)(a detailed analysis is presented

in Sec. III). Since it focuses on this result, Ref. [1] does

not oﬀer an analysis of the walk at times much larger

than O(1). Moreover, practical implementation not only

on current NISQ devices, but also on future, circuit-based

quantum computers, can only be envisaged if the algo-

rithm is robust to noise (see for example Refs. [7,31–37]);

this question is also not addressed in Ref. [1].

The aim of this article is to explore both aspects: long-

time dynamics and robustness to noise. The main results

are the following. First, the electric Dirac DQW exhibits

a second localization peak at a time scaling as O(√N)

with localization probability scaling as O(1/ln N). This

makes this walk state-of-the-art for 2D DQW spatial

search before amplitude ampliﬁcation. Moreover, this

second localization peak is highly robust to spatial noise.

Finally, the peak is also robust to spatiotemporal noise,

but not as much as it is to time-independent spatial noise.

The article is organised as follows. In Sec. II, we oﬀer

a review of the electric Dirac DQW presented in Ref. [1].

In Sec. III, we study in details the ﬁrst two maxima of

the localization probability. We show that the ﬁrst maxi-

mum, already analyzed in Ref. [1], is actually present up

to N= 9 ×106>106'220 (have in mind that 20 is

the current average number of working qubits on most

IBM-Q plateforms3). We also present evidence for the

scaling laws characterizing both the ﬁrst peak and the

second, long-time peak, which reaches Tulsi’s state-of-

the-art bound. In Sec. IV, we analyze the ressources one

needs to implement the quantum spatial search in terms

of qubits and primitive quantum operations. In Sec. V,

we show that the walk, and in particular the second peak,

have a good robustness to spatial oracle noise. We also

show that the ﬁrst peak is robust even to spatiotemporal

noise. In Sec. VI, we propose an analysis of the walker’s

probability distributions. These probability distributions

show that the spatial noise does not aﬀect the shape of

the peaks signiﬁcantly. The peaks remain extremely high

relatively to the background, which shows not only good

but high robustness of the peaks to spatial oracle noise.

The probability distributions also show that the second

peak is sharper than the ﬁrst one.

II. BASICS

A. Deﬁnition of the 2D electric Dirac DQW

We consider a 2D square spatial grid with nodes in-

dexed by two integers (p, q)∈[[0, M]]2, where M∈Nis

the number of nodes along one dimension and N=M2is

the total number of nodes. The time is also discrete and

indexed by a label j∈N. The walker is deﬁned by its

quantum state |Ψjiin the Hilbert space HC⊗HP, where

HC, called coin space, is the two-dimensional Hilbert

3https://quantum-computing.ibm.com/services/resources

space which corresponds to the internal, coin degree of

freedom, and HP, called position space, corresponds to

the spatial degrees of freedom. The wavefunction of the

state will be denoted as Ψj,p,q ≡ψL

j,p,q ψR

j,p,q>, where

>denotes the transposition. The discrete-time evolution

of the walker is deﬁned by the following one-step evolu-

tion equation,

Ψj+1,p,q = (UΨj)p,q .(1)

The one-step evolution operator, also called walk opera-

tor,U, is deﬁned by

U:=e−ieφ R(θ−)S2R(θ+)S1,(2)

where S1,2are standard shift operators,

(S1Ψ)L

p,q :=ψL

p+1,q (3a)

(S1Ψ)R

p,q :=ψR

p−1,q (3b)

(S2Ψ)L

p,q :=ψL

p,q+1 (3c)

(S2Ψ)R

p,q :=ψR

p,q−1,(3d)

R(θ)is a coin-space rotation, also called coin operator,

deﬁned by

R(θ):="cos θ i sin θ

isin θcos θ#,(4)

and

θ±:=±π

4−µ

2,(5)

with µsome real parameter. The operator e−ieφ is diag-

onal in position space, i.e., it acts on Ψjas

(e−ieφΨj)p,q =e−ieφp,q Ψj,p,q ,(6)

with φ: (p, q)7→ φp,q ∈Rsome sequence of the lattice

position, and ea parameter that we can call charge of

the walker, see why further down. The sequence φcan

be called lattice electric potential for at least two rea-

sons: (i) in the continuum limit (see below, Sec. II B),

this sequence indeed becomes, mathematically, an elec-

tric potential coupled to the walker, who then obeys the

Dirac equation, and (ii) beyond the continuum limit, it

has been shown that similar 2D DQWs exhibit an exact

lattice U(1) gauge invariance [38] which, in the contin-

uum limit, becomes the standard U(1) gauge invariance

of the Dirac equation coupled to an electromagnetic po-

tential.

B. Continuum limit

We introduce a spacetime-lattice spacing , and coordi-

nates tj:=j,xp:=p and yq:=q [39,40]. We assume

that Ψj,p,q coincides with the value taken at point tj,xp

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

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

10 玖币 0人已下载

立即下载

摘要：

Quantumspatialsearchwithelectricpotential:long-timedynamicsandrobustnesstonoiseThibaultFredon,1,JulienZylberman,2PabloArnault,1andFabriceDebbasch21UniversitéParis-Saclay,CNRS,ENSParis-Saclay,INRIA,LaboratoireMéthodesFormelles,91190Gif-sur-Yvette,France2SorbonneUniversité,ObservatoiredeParis,Univers...

展开>> 收起<<

Quantum spatial search with electric potential long-time dynamics and robustness to noise Thibault Fredon1Julien Zylberman2Pablo Arnault1and Fabrice Debbasch2.pdf

共8页,预览2页

还剩页未读，继续阅读

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

Quantum spatial search with electric potential long-time dynamics and robustness to noise Thibault Fredon1Julien Zylberman2Pablo Arnault1and Fabrice Debbasch2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: