[go: up one dir, main page]

Next Article in Journal
Einstein-Podolsky-Rosen Steering for Mixed Entangled Coherent States
Next Article in Special Issue
Return Probability of Quantum and Correlated Random Walks
Previous Article in Journal
High-Efficient Syndrome-Based LDPC Reconciliation for Quantum Key Distribution
Previous Article in Special Issue
Quantum Walk on the Generalized Birkhoff Polytope Graph
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Dirac Spatial Search with Electric Fields

by
Julien Zylberman
* and
Fabrice Debbasch
*
Sorbonne Université, Observatoire de Paris, Université PSL, CNRS, LERMA, F-75005 Paris, France
*
Authors to whom correspondence should be addressed.
Entropy 2021, 23(11), 1441; https://doi.org/10.3390/e23111441
Submission received: 12 September 2021 / Revised: 22 October 2021 / Accepted: 28 October 2021 / Published: 31 October 2021
(This article belongs to the Special Issue Quantum Walks: Applications and Fundamentals)
Figure 1
<p>Evolution of <math display="inline"><semantics> <msubsup> <mi>P</mi> <mi>j</mi> <mo>*</mo> </msubsup> </semantics></math> with time <span class="html-italic">j</span> for <math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <msup> <mn>120</mn> <mn>2</mn> </msup> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mo>Ω</mo> <mo>=</mo> <msub> <mo>Ω</mo> <mn>0</mn> </msub> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mi>m</mi> <mo>=</mo> <mn>0</mn> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mi>e</mi> <mi>Q</mi> <mo>=</mo> <mn>0.01</mn> </mrow> </semantics></math> (<b>left</b>) and <math display="inline"><semantics> <mrow> <mi>e</mi> <mi>Q</mi> <mo>=</mo> <mn>1</mn> </mrow> </semantics></math> (<b>right</b>).</p> ">
Figure 2
<p>Evolutions of <math display="inline"><semantics> <msubsup> <mi>P</mi> <mi>j</mi> <mo>*</mo> </msubsup> </semantics></math> with time <span class="html-italic">j</span> for <math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <msup> <mn>120</mn> <mn>2</mn> </msup> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mo>Ω</mo> <mo>=</mo> <msub> <mo>Ω</mo> <mn>0</mn> </msub> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mi>e</mi> <mi>Q</mi> <mo>=</mo> <mn>1</mn> </mrow> </semantics></math> and mass <math display="inline"><semantics> <mrow> <mi>m</mi> <mo>=</mo> <mn>0.08</mn> </mrow> </semantics></math> (<b>left</b>) or <math display="inline"><semantics> <mrow> <mi>m</mi> <mo>=</mo> <mn>0.25</mn> </mrow> </semantics></math> (<b>right</b>).</p> ">
Figure 3
<p>Density profiles at time <math display="inline"><semantics> <mrow> <mi>j</mi> <mo>=</mo> <mn>61</mn> </mrow> </semantics></math> corresponding to the first maximum of <math display="inline"><semantics> <msubsup> <mi>P</mi> <mi>j</mi> <mo>*</mo> </msubsup> </semantics></math> (<b>up</b>) and at time <math display="inline"><semantics> <mrow> <mi>j</mi> <mo>=</mo> <mn>111</mn> </mrow> </semantics></math> corresponding to the first minimum of <math display="inline"><semantics> <msubsup> <mi>P</mi> <mi>j</mi> <mo>*</mo> </msubsup> </semantics></math> (<b>down</b>) for <math display="inline"><semantics> <mrow> <mi>e</mi> <mi>Q</mi> <mo>=</mo> <mn>0.01</mn> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <msup> <mn>120</mn> <mn>2</mn> </msup> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mo>Ω</mo> <mo>=</mo> <msub> <mo>Ω</mo> <mn>0</mn> </msub> </mrow> </semantics></math>.</p> ">
Figure 4
<p>Density profiles at time <math display="inline"><semantics> <mrow> <mi>j</mi> <mo>=</mo> <mn>47</mn> </mrow> </semantics></math> corresponding to the first maximum of <math display="inline"><semantics> <msubsup> <mi>P</mi> <mi>j</mi> <mo>*</mo> </msubsup> </semantics></math> (<b>up</b>) and time <math display="inline"><semantics> <mrow> <mi>j</mi> <mo>=</mo> <mn>137</mn> </mrow> </semantics></math> corresponding to the first minimum of <math display="inline"><semantics> <msubsup> <mi>P</mi> <mi>j</mi> <mo>*</mo> </msubsup> </semantics></math> (<b>down</b>) for <math display="inline"><semantics> <mrow> <mi>e</mi> <mi>Q</mi> <mo>=</mo> <mn>1</mn> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <msup> <mn>120</mn> <mn>2</mn> </msup> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mo>Ω</mo> <mo>=</mo> <msub> <mo>Ω</mo> <mn>0</mn> </msub> </mrow> </semantics></math>.</p> ">
Figure 5
<p>Density profiles at times <math display="inline"><semantics> <mrow> <mi>j</mi> <mo>=</mo> <mn>5</mn> </mrow> </semantics></math> (<b>up</b>) and <math display="inline"><semantics> <mrow> <mi>j</mi> <mo>=</mo> <mn>6</mn> </mrow> </semantics></math> (<b>down</b>) for <math display="inline"><semantics> <mrow> <mi>e</mi> <mi>Q</mi> <mo>=</mo> <mn>1</mn> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <msup> <mn>120</mn> <mn>2</mn> </msup> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mo>Ω</mo> <mo>=</mo> <msub> <mo>Ω</mo> <mn>0</mn> </msub> </mrow> </semantics></math>.</p> ">
Figure 6
<p>Density contours at time <math display="inline"><semantics> <mrow> <mi>j</mi> <mo>=</mo> <mn>61</mn> </mrow> </semantics></math> corresponding to the first maximum of <math display="inline"><semantics> <msubsup> <mi>P</mi> <mi>j</mi> <mo>*</mo> </msubsup> </semantics></math> for <math display="inline"><semantics> <mrow> <mi>e</mi> <mi>Q</mi> <mo>=</mo> <mn>0.01</mn> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <msup> <mn>120</mn> <mn>2</mn> </msup> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mo>Ω</mo> <mo>=</mo> <msub> <mo>Ω</mo> <mn>0</mn> </msub> </mrow> </semantics></math> and two different initial conditions: <math display="inline"><semantics> <mrow> <msup> <mi>ψ</mi> <mi>L</mi> </msup> <mo>=</mo> <msup> <mi>ψ</mi> <mi>R</mi> </msup> </mrow> </semantics></math> (<b>up</b>) and <math display="inline"><semantics> <mrow> <msup> <mi>ψ</mi> <mi>R</mi> </msup> <mo>=</mo> <mn>0</mn> </mrow> </semantics></math> (<b>down</b>).</p> ">
Figure 7
<p>Time <span class="html-italic">T</span> for the first maximum of <math display="inline"><semantics> <msubsup> <mrow> <mover accent="true"> <mi>P</mi> <mo stretchy="false">¯</mo> </mover> </mrow> <mi>j</mi> <mo>*</mo> </msubsup> </semantics></math> in function of <math display="inline"><semantics> <msqrt> <mi>N</mi> </msqrt> </semantics></math> for <math display="inline"><semantics> <mrow> <mi>e</mi> <mi>Q</mi> <mo>=</mo> <mn>0.9</mn> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mo>Ω</mo> <mo>=</mo> <msub> <mo>Ω</mo> <mn>0</mn> </msub> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mi>m</mi> <mo>=</mo> <mn>0</mn> </mrow> </semantics></math>. The function fitting <span class="html-italic">T</span> for small <span class="html-italic">N</span> is approximately <math display="inline"><semantics> <mrow> <mn>0.96</mn> <msqrt> <mi>N</mi> </msqrt> <mo>−</mo> <mn>1.66</mn> </mrow> </semantics></math> and appears in yellow.</p> ">
Figure 8
<p>Renormalised probability <math display="inline"><semantics> <msubsup> <mrow> <mover accent="true"> <mi>P</mi> <mo stretchy="false">¯</mo> </mover> </mrow> <mi>j</mi> <mo>*</mo> </msubsup> </semantics></math> against time <span class="html-italic">j</span> for <math display="inline"><semantics> <mrow> <mi>e</mi> <mi>Q</mi> <mo>=</mo> <mn>0.9</mn> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mo>Ω</mo> <mo>=</mo> <msub> <mo>Ω</mo> <mn>0</mn> </msub> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <msup> <mn>30</mn> <mn>2</mn> </msup> </mrow> </semantics></math> (blue), <math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <msup> <mn>46</mn> <mn>2</mn> </msup> </mrow> </semantics></math> (orange), <math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <msup> <mn>60</mn> <mn>2</mn> </msup> </mrow> </semantics></math> (green) and <math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <msup> <mn>76</mn> <mn>2</mn> </msup> </mrow> </semantics></math> (red), <math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <msup> <mn>90</mn> <mn>2</mn> </msup> </mrow> </semantics></math> (navy blue), <math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <msup> <mn>106</mn> <mn>2</mn> </msup> </mrow> </semantics></math> (brown), <math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <msup> <mn>120</mn> <mn>2</mn> </msup> </mrow> </semantics></math> (cyan), <math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <msup> <mn>180</mn> <mn>2</mn> </msup> </mrow> </semantics></math> (yellow) and <math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <msup> <mn>240</mn> <mn>2</mn> </msup> </mrow> </semantics></math> (purple).</p> ">
Versions Notes

Abstract

:
Electric Dirac quantum walks, which are a discretisation of the Dirac equation for a spinor coupled to an electric field, are revisited in order to perform spatial searches. The Coulomb electric field of a point charge is used as a non local oracle to perform a spatial search on a 2D grid of N points. As other quantum walks proposed for spatial search, these walks localise partially on the charge after a finite period of time. However, contrary to other walks, this localisation time scales as N for small values of N and tends asymptotically to a constant for larger Ns, thus offering a speed-up over conventional methods.

1. Introduction

Quantum Walks (QWs) are automata defined on graphs and lattices. These were first considered by Feynman in studying possible discretisations for the Dirac path integral [1,2]. They were later introduced in a systematic manner by Aharonov et al. [3] and Meyers [4], and they have been realized experimentally in a number of ways [5], which include cold atoms [6], photonic systems [7,8] and trapped ions [9,10]. With the recent development of Noisy Intermediate Scale Quantum (NISQ) devices, it is now possible to implement short-depth quantum circuits with several qubits such as QWs [11,12,13,14]. Unitary QWs are also a universal primitive of unitary computation [15,16,17] useful in quantum information and algorithmic development [5,18,19,20,21,22]. Moreover, several spatial search algorithms based on QWs have been proposed [23,24,25,26,27,28,29]. It appears that the most successful strategies consist in using unitary QWs which (i) incorporate the basic idea behind Grover abstract search algorithm [30,31] and (ii) admit, similarly to massless Dirac equation, a linear dispersion relation at large scales [32,33,34]. Some of these unitary QWs work in continuous time [35,36,37,38,39], while others work in discrete time [40,41,42,43,44].
Unitray QWs are also important for quantum simulation [45,46]. In particular, unitary QWs can be used to simulate Dirac fermions interacting with arbitrary Yang-Mills gauge fields [47,48] and arbitrary relativistic gravitational fields [49,50,51,52,53], and steps have been taken to construct alternatives to Lattice Gauge Theories based on Discrete-Time Quantum Walks (DTQWs) [54]. Finally, geometrical aspects of unitary QWs are discussed in [55].
The idea behind the present article is to merge both lines of thought and present a spatial search algorithm based on QWs interacting with a gauge field. In order to keep the discussion as simple as possible, we focus on 2 D search on a periodic square grid (2D discrete torus) with N points and consider only Discrete-Time Quantum Walks (DTQWs). To permit the introduction of an electric field, the wave function of the walker must have only two components, as the 2 D spinors obey the Dirac equation, and not four. The algorithm is based on QWs already introduced in the literature [47]. These walks admit a continuum limit which coincides with the Dirac equation obeyed by a spin 1 / 2 fermion in flat ( 1 + 2 ) D space-time in the presence of an arbitrary static electric field. This field is encoded in a global phase and acts as the oracle in the search. We first present these DTQWs and recall their continuum limit. We then particularise the electric field to the Coulomb field created by a charge situated at the center of a grid cell Ω and show by numerical simulations that, for spatially homogeneous initial conditions, the algorithm localises partially the walker after a finite time on the four corners of the cell containing the point Ω . The search can then be completed by amplitude amplification. For smaller values of N, the partial localisation time of the Dirac walk scales as N , but this tends asymptotically to a constant value independent of N. If partial localisation after a finite time is standard for spatial search algorithms based on QWs, the fact that the partial localisation time does not scale as N for all Ns but rather tends to a constant for larger Ns is definitely non standard. All results are finally summed up and discussed with special emphasis on possible extensions.

2. Materials and Methods: The Dirac Quantum Walks

2.1. Definition

We consider a 2D square grid where the nodes are indexed by the two positive integers ( p , q ) N M 2 , with M an arbitrary strictly positive integer. The integers p and q can be considered as discrete Cartesian coordinates in 2 D space. The total number of points in the grid is N = M 2 , and we impose periodic boundary conditions. Time is also discrete and indexed by j N . Given a basis ( | b L , | b R ) of an Hilbert space H 2 named the ‘spin’-space, the wave-function ψ H 2 of the DTQW is represented by its two components ψ L and ψ R . The equations of motion of the walks considered in this article are of the form ψ j + 1 = U ψ j where U is a unitary operator independent of the time j. This operator is U = exp ( i e V ) · R ( θ + ) · S q · R ( θ ) · S p where S p and S q are the standard shift operators defined by the following equations:
( S p ψ ) p , q L = ψ p + 1 , q L ( S p ψ ) p , q R = ψ p 1 , q L
and
( S q ψ ) p , q L = ψ p , q + 1 L ( S q ψ ) p , q R = ψ p , q 1 L .
The operator R ( θ ) is a rotation in spin space and is represented in the basis ( | b L , | b R ) by the matrix
R = cos ( θ ) i sin ( θ ) i sin ( θ ) cos ( θ )
where θ ± = ± ( π / 4 ) ( m / 2 ) with m a real positive parameter. The operator V is, at each point, proportional to the identity in spin space; thus, ( exp ( i e V ) ψ ) p , q = exp ( i e V p , q ) ψ p , q where e is another arbitrary real parameter. The interpretation of m and e will be made clear below.

2.2. Continuum Limit

The continuum limit describes situations where the wave-function ψ of the walk varies on time-scales and spatial scales much larger than the step of the grid. Suppose that there exists a real positive number ϵ much lower than unity such that, in a certain domain in ( j , p , q ) -space, the wave-function ψ varies on scales of order ϵ 1 in its three variables j, p and q. Then, define the ‘slow’ variables t = ϵ j , x = ϵ p and y = ϵ q so that ψ varies on scales of order unity in these new variables. Suppose also that, in the same domain, the quantities e V and m are of order ϵ and write e V = ϵ e V ˜ and m = ϵ m ˜ . The discrete equations of the motion for the walk can then be expanded in powers of ϵ around ϵ = 0 . This expansion delivers the identity ψ = ψ at zeroth order in ϵ but, at first order, one obtains he following.
( t i e V ˜ ) ψ L x ψ L i y ψ R + i m ˜ ψ R = 0 ( t i e V ˜ ) ψ R + x ψ R + i y ψ L + i m ˜ ψ L = 0 .
This equation coincides with the flat ( 1 + 2 ) D space-time Dirac equation for a spinor of mass m ˜ and electric charge e propagating in the electric potential V ˜ . More details on the calculations of the continuous limit can be found at [50,56].

3. Results: Search with Coulomb Potential

We now particularise the discussion to the following choice:
V p , q = Q ( p Ω p ) 2 + ( q Ω q ) 2 1 / 2 ,
except on the borders of the grid, where we impose the potential to vanish identically, thus preserving periodicity in both p and q. The above expression coincides with the Coulomb potential created by a point charge Q situated at point Ω = ( Ω p , Ω q ) . To ensure that the walk is defined at all points in the grid, the point Ω where V diverges must not be on the grid. A simple possibility is to choose Ω at the center of a grid-cell equidistant from the four vertices of this cell. The distance in the ( p , q ) Euclidean plane between Ω and these 4 points is then 1 / 2 , and the maximum value taken by the function V on the grid is the following.
V m a x = Q 2 .
At given Ω , m and N, the walk is entirely controlled by the initial condition and the parameter a = e Q . The maximum value of the global phase is α m a x = e V m a x = e Q 2 .
As is usual in spatial search problems, we choose initial conditions that are uniform on the grid and in spin state [30,31]. Considering the chosen potential, the algorithm can be considered successful if it localises the walker on the four vertices of the cell centred on Ω . Let P j * be the probability of finding the walker at time j on any of these four vertices. The explicit expression of P j * is:
P j * = P j , Ω p + 1 / 2 , Ω q + 1 / 2 + P j , Ω p 1 / 2 , Ω q + 1 / 2 + P j , Ω p + 1 / 2 , Ω q 1 / 2 + P j , Ω p 1 / 2 , Ω q 1 / 2
with
P j , p , q = ψ j , p , q L 2 + ψ j , p , q R 2 .
The probability P j * depends in a non trivial manner on the free parameters Ω , m, N and e Q . Exploring systematically this parameter space is out of the scope of this article. What follows is a synthetic presentation of some features observed in extensive numerical simulations.
As expected from the behaviour of other QW based search algorithms, at fixed values of the parameters Ω , m, N and a = e Q , the probability P j * displays strong oscillations in j. For example, Figure 1 displays two typical evolutions of P j * with j, both obtained on a grid of N = 120 2 points, with m = 0 . and with Ω = Ω 0 located at the center of the central grid cell but for different values of a. Changing Ω does not change P j * too much, at least if one does not proceed too close to the border of the grid (data not shown). However, changing m typically increases the oscillation frequency of P j * , as exemplified Figure 2, which plots P j * against time j for N = 120 2 , Ω = Ω 0 , m = 0.08 and m = 0.25 . The introduction of a non-vanishing mass provides greater inertia to the walker, slowing down the localisation process. In Figure 2, the value ∼ 0.21 is reached by function P j * at a later time when compared to the right curve of Figure 1. Note also that the values reached by P j * are larger when the mass vanishes.
Density profiles corresponding to the first maximum and the first minimum of P j * are presented in Figure 3 and Figure 4. It is obvious from the figures that localisation is much more efficient for a = 1 than for a = 0.01 . In particular, for a = 0.01 , localisation does occur on two of the four vertices, but it is accompanied by rather strong anti-localisation on the other two and the background probability, i.e., the probability of finding the walker elsewhere than around Ω 0 is not negligible. Furthermore, there is not much difference between the density profiles corresponding to the first maximum and the first minimum of P j * : Peaks have more or less the same height, and density displays ripples and bumps outside the peaks. The picture changes drastically for a = 1 . There is now practically no anti-localisation, the peak at time j = 47 when P j * is maximal is approximately 10 times higher than the peak at time j = 137 when P j * is minimal, and the density outside the peaks is nearly flat and practically vanishes, even when P * is minimum. In this case, localisation actually happens well before P * reaches its first maximum (see Figure 5); once installed, localisation remains at all explored times.
The density profiles displayed in Figure 3, Figure 4 and Figure 5 are non symmetric around the central point Ω ; in particular, the walker does not distribute evenly among the four vertices that surround Ω . This is due to the choice of initial condition in spin state. The upper part of Figure 6 offers a contour version of the upper Figure 3 and corresponds to an initial condition symmetric in ψ L and ψ R . Switching to an initial condition with vanishing ψ R does not change the time-evolution of P * (data not shown) but produces the other contour plot in Figure 6 where the central peak is nearly symmetric.
A final comment on the density profiles is in order. The absolute values taken by the density P j , p , q may appear to be rather small. The main reason for that is the total number of points N = 120 2 over which the walker moves. A uniform probability spread uniformly over 120 2 points amounts to 6.94 × 10 5 . The density profiles corresponding to a = 0.01 reveal that the peaks are then approximately 4.3 % above this value. However, the peak for a = 1 at time t = 47 corresponding to the first maximum of P j * is approximately 0.006 86 × 6.94 × 10 5 , corresponding to an increase of 8500 % with respect to uniform spreading, which is quite substantial. Whatever the increase, the absolute value of 0.006 may still be considered small compared to unity. However, it is not vanishingly small. Moreover, as already indicated in the introduction and as discussed in the final section, the search procedure offered by the DTQWs presented cannot be considered complete, since the probability of finding the walker on the four vertices surrounding Ω is never equal to unity. The search should, therefore, be complemented by amplitude amplification.
Let us now explore how the time T at which P j * reaches its first maximum evolves with N. Typical results are displayed in Figure 7 and Figure 8 for Ω = Ω 0 and a = 0.9 . Figure 7 displays the time T of the first maximum of P j * as a function of N. At small N, T increases as N but T is asymptotically constant. This unexpected behaviour has been observed numerically for all values of a; the greater a is, the sooner the asymptotic regime in which T is independent of N is reached. For example, for a = 1 , the asymptotic regime is reached around N = 30 .
Figure 8 displays the renormalised probability P ¯ j * = 4 P j * / N plotted against time for N = 30 2 (blue), N = 46 2 (orange), N = 60 2 (green), N = 76 2 (red), N = 90 2 (navy blue), N = 106 2 (brown), N = 120 2 (cyan), N = 180 2 (yellow) and N = 240 2 (purple). The N scaling and the constant asymptotic behaviour can naturally be observed in this figure too. Figure 8 also shows that, quite remarkably, the function P ¯ * is essentially independent of N on the left of the first maximum. Note also that the short N-scaling does not involve log N .
Let us end this section by a qualitative comment for explaining how the localisation time becomes independant of N due to the finite velocity of the walk. Fix all values of the parameters except N and suppose that, for some value N 0 of N, the first maximum of P j * is reached at time T 0 . Since DTQW is a discrete version of the relativistic Dirac equation, it essentially propagates at a finite velocity which, in the units used in this article, is equal to unity. Thus, in time T 0 , the peak around Ω has only been influenced by points at distance T 0 . If N 0 / 2 is sufficiently lower than T 0 , increasing N will allow points around Ω to observe more distant points and will presumably modify T 0 . However, suppose N 0 / 2 is larger than T 0 . Then, increasing N will not modify the dynamics of the peak until times later than T 0 ; thus, T 0 will be independent of N for N larger than N 0 . Observe now Figure 7. The time T becomes independent of N around N = 160 2 and is then approximately equal to T a 84 160 / 2 , which seems to confirm the above reasoning. If this line of reasoning is correct, any walk that propagates at finite velocity c and for which one can find an N 0 such that N 0 / 2 > c T 0 will present the same asymptotic property. Intuitively, the existence of such an N seems linked to the rapid convergence towards Ω exemplified in Figure 5.

4. Discussion

Let us now discuss these results and mention some natural extensions. One should first stress that the DTQWs considered in this article, as previous QWs used in spatial search algorithms, never fully localise on the desired points. In the present context, localisation means that the probability of finding the walker on the desired point is substantially higher than the background probability of finding it at any other point. Fully localising the walk would require adding a step commonly called amplitude amplification.
The most interesting aspect of these walks is their behaviour for large enough values of N. Indeed, localisation times for other spatial search algorithms scale as N or N log N . The partial localisation time of these new walks does scale as N for small enough N but appears to saturate a constant value for larger N. This is possibly the most remarkable property of these walks. Of course, this does not contradict the theorem that states that an optimal quantum search takes O ( N ) steps because the localisation we are speaking of is not total, and completing it with amplitude amplification would take O ( N ) steps. Thus, the saturation property of the walks introduced in this article does not change the order of magnitude of a the minimal time necessary to perform a full quantum search. However, for large enough values of N, it makes the first step of the spatial search much faster than expected and realised in other quantum walks. Stopping after this step may even be enough for some applications.
The results presented in this article should first be generalised not only to higher dimensions but also to general lattices or graphs and and more varied initial conditions, especially in spin space. The simulations presented in this article show that it is possible to use artificial gauge fields as oracles to perform efficient spatial searches. One could also consider using other artificial gauge fields, including magnetic fields, general Yang-Mills fields and gravitational fields, as oracles in quantum search problems. Moreover, one wonders whether problems more complex than the one studied in the present, such as for example the motion of several particles in a gauge field they self-consistently generate, are also susceptible of quantum algorithmic interpretation. As for now, this article adds to the literature showing that physics can be a source of inspiration to develop new strategies in quantum information. Other examples include applications of quantum tunelling [57] and of Anderson localization [58,59].

Author Contributions

All authors worked on all aspects of the article. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Data Availability Statement

Data are available from the authors upon request.

Conflicts of Interest

The authors declare no conflict of interest.

Abbreviations

The following abbreviations were used in this manuscript:
QWQuantum Walk;
DTQWDiscrete Time Quantum Walk.

References

  1. Feynman, R.P.; Hibbs, A.R. Quantum Mechanics and Path Integrals; McGraw-Hill Book: New York, NY, USA, 1965. [Google Scholar]
  2. Schweber, S.S. Feynman and the visualization of space-time processes. Rev. Mod. Phys. 1986, 58, 449. [Google Scholar] [CrossRef]
  3. Aharonov, Y.; Davidovich, L.; Zagury, N. Quantum random walks. Phys. Rev. A 1993, 48, 1687. [Google Scholar] [CrossRef]
  4. Meyer, D.A. From quantum cellular automata to quantum lattice gases. J. Stat. Phys. 1996, 85, 551–574. [Google Scholar] [CrossRef] [Green Version]
  5. Manouchehri, K.; Wang, J.B. Physical Implementation of Quantum Walks; Springer: Berlin/Heidelberg, Germany, 2014. [Google Scholar]
  6. Karski, M.; Förster, L.; Choi, J.M.; Steffen, A.; Alt, W.; Meschede, D.; Widera, A. Quantum Walk in Position Space with Single Optically Trapped Atoms. Science 2009, 325, 174. [Google Scholar] [CrossRef] [Green Version]
  7. Peruzzo, A.; Lobino, M.; Matthews, J.C.F.; Matsuda, N.; Politi, A.; Poulios, K.; Xiao-Qi, Z.; Lahini, Y.; Ismail, N.; Wörhoff, K.; et al. Quantum Walks of Correlated Photons. Science 2010, 329, 1500–1503. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  8. Schreiber, A.; Cassemiro, K.N.; Potocek, V.; Gabris, A.; Mosley, P.; Andersson, E.; Jex, I.; Silberhorn, C. Photons Walking the Line: A quantum walk with adjustable coin operations. Phys. Rev. Lett. 2010, 104, 050502. [Google Scholar] [CrossRef]
  9. Huerta Alderete, C.; Singh, S.; Nguyen, N.H.; Zhu, D.; Balu, R.; Monroe, C.; Chandrashekhar, C.; Linke, N.M. Quantum walks and Dirac cellular automata on a programmable trapped-ion quantum computer. Nat. Commun. 2020, 11, 3720. [Google Scholar] [CrossRef] [PubMed]
  10. Zähringer, F.; Kirchmair, G.; Gerritsma, R.; Solano, E.; Blatt, R.; Roos, C.F. Realization of a quantum walk with one and two trapped ions. Phys. Rev. Lett. 2010, 104, 100503. [Google Scholar] [CrossRef] [PubMed]
  11. Acasiete, F.; Agostini, F.P.; Moqadam, J.K.; Portugal, R. Implementation of quantum walks on IBM quantum computers. Quantum Inf. Process. 2020, 19, 1–20. [Google Scholar] [CrossRef]
  12. Singh, S.; Alderete, C.H.; Balu, R.; Monroe, C.; Linke, N.M.; Chandrashekar, C. Universal one-dimensional discrete-time quantum walks and their implementation on near term quantum hardware. arXiv 2020, arXiv:2001.11197. [Google Scholar]
  13. Georgopoulos, K.; Emary, C.; Zuliani, P. Comparison of quantum-walk implementations on noisy intermediate-scale quantum computers. Phys. Rev. A 2021, 103, 022408. [Google Scholar] [CrossRef]
  14. Shakeel, A. Efficient and scalable quantum walk algorithms via the quantum Fourier transform. Quantum Inf. Process. 2020, 19, 1–26. [Google Scholar] [CrossRef]
  15. Childs, A. Universal Computation by Quantum Walk. Phys. Rev. Lett. 2009, 102, 180501. [Google Scholar] [CrossRef] [Green Version]
  16. Childs, A.M.; Gosset, D.; Webb, Z. Universal computation by multiparticle quantum walk. Science 2013, 339, 791–794. [Google Scholar] [CrossRef] [Green Version]
  17. Lovett, N.; Cooper, S.; Everitt, M.; Trevers, M.; Kendon, V. Universal quantum computation using the discrete-time quantum walk. Phys. Rev. A 2010, 81, 042330. [Google Scholar] [CrossRef] [Green Version]
  18. Ambainis, A. Quantum walks and their algorithmic applications. Int. J. Quantum Inf. 2003, 1, 507–518. [Google Scholar] [CrossRef] [Green Version]
  19. Ambainis, A. Quantum walk algorithm for element distinctness. SIAM J. Comput. 2007, 37, 210–239. [Google Scholar] [CrossRef]
  20. Aaronson, S.; Ambainis, A. Quantum search of spatial regions. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, Cambridge, MA, USA, 10–13 October 2003; pp. 200–209. [Google Scholar]
  21. Magniez, F.; Nayak, A.; Roland, J.; Santha, M. Search via quantum walk. SIAM J. Comput. 2011, 40, 142–164. [Google Scholar] [CrossRef] [Green Version]
  22. Portugal, R. Quantum Walks and Search Algorithms; Springer: Berlin/Heidelberg, Germany, 2013. [Google Scholar]
  23. Ambainis, A. Quantum search algorithms. ACM SIGACT News 2004, 35, 22–35. [Google Scholar] [CrossRef] [Green Version]
  24. Portugal, R.; Santos, R.A.; Fernandes, T.D.; Gonçalves, D.N. The staggered quantum walk model. Quantum Inf. Process. 2016, 15, 85–101. [Google Scholar] [CrossRef]
  25. Portugal, R. Staggered quantum walks on graphs. Phys. Rev. A 2016, 93, 062335. [Google Scholar] [CrossRef] [Green Version]
  26. Abal, G.; Donangelo, R.; Marquezino, F.L.; Portugal, R. Spatial search on a honeycomb network. Math. Struct. Comput. Sci. 2010, 20, 999–1009. [Google Scholar] [CrossRef] [Green Version]
  27. Childs, A.M.; Goldstone, J. Spatial search by quantum walk. Phys. Rev. A 2004, 70, 022314. [Google Scholar] [CrossRef] [Green Version]
  28. Tulsi, A. Faster quantum-walk algorithm for the two-dimensional spatial search. Phys. Rev. A 2008, 78, 012310. [Google Scholar] [CrossRef] [Green Version]
  29. Wong, T.G. Faster search by lackadaisical quantum walk. Quantum Inf. Process. 2018, 17, 1–9. [Google Scholar] [CrossRef] [Green Version]
  30. Grover, L.K. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, PA, USA, 22–24 May 1996; pp. 212–219. [Google Scholar]
  31. Grover, L.K. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 1997, 79, 325. [Google Scholar] [CrossRef] [Green Version]
  32. Childs, A.M.; Goldstone, J. Spatial search and the Dirac equation. Phys. Rev. A 2004, 70, 042312. [Google Scholar] [CrossRef] [Green Version]
  33. Guillet, S.; Roget, M.; Arrighi, P.; Molfetta, G. The Grover search as a naturally occurring phenomenon. arXiv 2019, arXiv:1908.11213. [Google Scholar]
  34. Patel, A.; Rahaman, M.A. Search on a hypercubic lattice using a quantum random walk. I. Phys. Rev. A 2010, 82, 032330. [Google Scholar] [CrossRef] [Green Version]
  35. Wong, T.G. Spatial search by continuous-time quantum walk with multiple marked vertices. Quantum Inf. Process. 2016, 15, 1411–1443. [Google Scholar] [CrossRef] [Green Version]
  36. Chakraborty, S.; Novo, L.; Roland, J. Optimality of spatial search via continuous-time quantum walks. Phys. Rev. A 2020, 102, 032214. [Google Scholar] [CrossRef]
  37. Childs, A.M.; Ge, Y. Spatial search by continuous-time quantum walks on crystal lattices. Phys. Rev. A 2014, 89, 052337. [Google Scholar] [CrossRef] [Green Version]
  38. Osada, T.; Coutinho, B.; Omar, Y.; Sanaka, K.; Munro, W.J.; Nemoto, K. Continuous-time quantum-walk spatial search on the Bollobás scale-free network. Phys. Rev. A 2020, 101, 022310. [Google Scholar] [CrossRef] [Green Version]
  39. Tanaka, H.; Sabri, M.; Portugal, R. Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk. arXiv 2021, arXiv:2108.01992. [Google Scholar]
  40. Lovett, N.B.; Everitt, M.; Trevers, M.; Mosby, D.; Stockton, D.; Kendon, V. Spatial search using the discrete time quantum walk. Nat. Comput. 2012, 11, 23–35. [Google Scholar] [CrossRef]
  41. Lovett, N.B.; Everitt, M.; Heath, R.M.; Kendon, V. The quantum walk search algorithm: Factors affecting efficiency. Math. Struct. Comput. Sci. 2019, 29, 389–429. [Google Scholar] [CrossRef] [Green Version]
  42. Ambainis, A.; Kempe, J.; Rivosh, A. Coins make quantum walks faster. arXiv 2004, arXiv:quant-ph/0402107. [Google Scholar]
  43. Xue, X.L.; Ruan, Y.; Liu, Z.H. Discrete-time quantum walk search on Johnson graphs. Quantum Inf. Process. 2019, 18, 1–10. [Google Scholar] [CrossRef]
  44. Di Molfetta, G.; Arrighi, P. A quantum walk with both a continuous-time limit and a continuous-spacetime limit. Quantum Inf. Process. 2020, 19, 1–16. [Google Scholar] [CrossRef]
  45. Gerritsma, R.; Kirchmair, G.; Zähringer, F.; Solano, E.; Blatt, R.; Roos, C. Quantum simulation of the Dirac equation. Nature 2010, 463, 68–71. [Google Scholar] [CrossRef] [Green Version]
  46. Arnault, P.; Macquet, A.; Anglés-Castillo, A.; Márquez-Martín, I.; Pina-Canelles, V.; Pérez, A.; Di Molfetta, G.; Arrighi, P.; Debbasch, F. Quantum simulation of quantum relativistic diffusion via quantum walks. J. Phys. A Math. Theor. 2020, 53, 205303. [Google Scholar] [CrossRef] [Green Version]
  47. Arnault, P.; Debbasch, F. Quantum walks and discrete gauge theories. Phys. Rev. A 2016, 93, 052301. [Google Scholar] [CrossRef] [Green Version]
  48. Márquez, I.; Arnault, P.; Di Molfetta, G.; Pérez, A. Electromagnetic lattice gauge invariance in two-dimensional discrete-time quantum walks. Phys. Rev. A 2018, 98, 032333. [Google Scholar] [CrossRef] [Green Version]
  49. Di Molfetta, G.; Brachet, M.; Debbasch, F. Quantum walks as massless Dirac fermions in curved space-time. Phys. Rev. A 2013, 88, 042301. [Google Scholar] [CrossRef] [Green Version]
  50. Di Molfetta, G.; Brachet, M.; Debbasch, F. Quantum walks in artificial electric and gravitational fields. Phys. A Stat. Mech. Its Appl. 2014, 397, 157–168. [Google Scholar] [CrossRef] [Green Version]
  51. Arrighi, P.; Facchini, S.; Forets, M. Quantum walking in curved spacetime. Quantum Inf. Process. 2016, 15, 3467–3486. [Google Scholar] [CrossRef] [Green Version]
  52. Arrighi, P.; Facchini, S. Quantum walking in curved spacetime: (3 + 1) dimensions, and beyond. Quantum Inf. Comput. 2017, 17, 810–824. [Google Scholar]
  53. Arnault, P.; Debbasch, F. Quantum walks and gravitational waves. Ann. Phys. 2017, 383, 645–661. [Google Scholar] [CrossRef] [Green Version]
  54. Arnault, P.; Di Molfetta, G.; Brachet, M.; Debbasch, F. Quantum walks and non-Abelian discrete gauge theory. Phys. Rev. A 2016, 94, 012335. [Google Scholar] [CrossRef] [Green Version]
  55. Debbasch, F. Discrete geometry from quantum walks. Condens. Matter 2019, 4, 40. [Google Scholar] [CrossRef] [Green Version]
  56. Arrighi, P.; Nesme, V.; Forets, M. The Dirac equation as a quantum walk: Higher dimensions, observational convergence. J. Phys. A Math. Theor. 2014, 47, 465302. [Google Scholar] [CrossRef] [Green Version]
  57. Campos, E.; Venegas-Andraca, S.E.; Lanzagorta, M. Quantum tunneling and quantum walks as algorithmic resources to solve hard K-SAT instances. Sci. Rep. 2021, 11, 1–18. [Google Scholar] [CrossRef]
  58. Vakulchyk, I.; Fistul, M.V.; Qin, P.; Flach, S. Anderson localization in generalized discrete-time quantum walks. Phys. Rev. B 2017, 96, 144204. [Google Scholar] [CrossRef] [Green Version]
  59. Altshuler, B.; Krovi, H.; Roland, J. Anderson localization makes adiabatic quantum optimization fail. Proc. Natl. Acad. Sci. USA 2010, 107, 12446–12450. [Google Scholar] [CrossRef] [PubMed] [Green Version]
Figure 1. Evolution of P j * with time j for N = 120 2 , Ω = Ω 0 , m = 0 , e Q = 0.01 (left) and e Q = 1 (right).
Figure 1. Evolution of P j * with time j for N = 120 2 , Ω = Ω 0 , m = 0 , e Q = 0.01 (left) and e Q = 1 (right).
Entropy 23 01441 g001
Figure 2. Evolutions of P j * with time j for N = 120 2 , Ω = Ω 0 , e Q = 1 and mass m = 0.08 (left) or m = 0.25 (right).
Figure 2. Evolutions of P j * with time j for N = 120 2 , Ω = Ω 0 , e Q = 1 and mass m = 0.08 (left) or m = 0.25 (right).
Entropy 23 01441 g002
Figure 3. Density profiles at time j = 61 corresponding to the first maximum of P j * (up) and at time j = 111 corresponding to the first minimum of P j * (down) for e Q = 0.01 , N = 120 2 and Ω = Ω 0 .
Figure 3. Density profiles at time j = 61 corresponding to the first maximum of P j * (up) and at time j = 111 corresponding to the first minimum of P j * (down) for e Q = 0.01 , N = 120 2 and Ω = Ω 0 .
Entropy 23 01441 g003
Figure 4. Density profiles at time j = 47 corresponding to the first maximum of P j * (up) and time j = 137 corresponding to the first minimum of P j * (down) for e Q = 1 , N = 120 2 and Ω = Ω 0 .
Figure 4. Density profiles at time j = 47 corresponding to the first maximum of P j * (up) and time j = 137 corresponding to the first minimum of P j * (down) for e Q = 1 , N = 120 2 and Ω = Ω 0 .
Entropy 23 01441 g004
Figure 5. Density profiles at times j = 5 (up) and j = 6 (down) for e Q = 1 , N = 120 2 and Ω = Ω 0 .
Figure 5. Density profiles at times j = 5 (up) and j = 6 (down) for e Q = 1 , N = 120 2 and Ω = Ω 0 .
Entropy 23 01441 g005
Figure 6. Density contours at time j = 61 corresponding to the first maximum of P j * for e Q = 0.01 , N = 120 2 , Ω = Ω 0 and two different initial conditions: ψ L = ψ R (up) and ψ R = 0 (down).
Figure 6. Density contours at time j = 61 corresponding to the first maximum of P j * for e Q = 0.01 , N = 120 2 , Ω = Ω 0 and two different initial conditions: ψ L = ψ R (up) and ψ R = 0 (down).
Entropy 23 01441 g006
Figure 7. Time T for the first maximum of P ¯ j * in function of N for e Q = 0.9 , Ω = Ω 0 and m = 0 . The function fitting T for small N is approximately 0.96 N 1.66 and appears in yellow.
Figure 7. Time T for the first maximum of P ¯ j * in function of N for e Q = 0.9 , Ω = Ω 0 and m = 0 . The function fitting T for small N is approximately 0.96 N 1.66 and appears in yellow.
Entropy 23 01441 g007
Figure 8. Renormalised probability P ¯ j * against time j for e Q = 0.9 , Ω = Ω 0 and N = 30 2 (blue), N = 46 2 (orange), N = 60 2 (green) and N = 76 2 (red), N = 90 2 (navy blue), N = 106 2 (brown), N = 120 2 (cyan), N = 180 2 (yellow) and N = 240 2 (purple).
Figure 8. Renormalised probability P ¯ j * against time j for e Q = 0.9 , Ω = Ω 0 and N = 30 2 (blue), N = 46 2 (orange), N = 60 2 (green) and N = 76 2 (red), N = 90 2 (navy blue), N = 106 2 (brown), N = 120 2 (cyan), N = 180 2 (yellow) and N = 240 2 (purple).
Entropy 23 01441 g008
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Zylberman, J.; Debbasch, F. Dirac Spatial Search with Electric Fields. Entropy 2021, 23, 1441. https://doi.org/10.3390/e23111441

AMA Style

Zylberman J, Debbasch F. Dirac Spatial Search with Electric Fields. Entropy. 2021; 23(11):1441. https://doi.org/10.3390/e23111441

Chicago/Turabian Style

Zylberman, Julien, and Fabrice Debbasch. 2021. "Dirac Spatial Search with Electric Fields" Entropy 23, no. 11: 1441. https://doi.org/10.3390/e23111441

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop