Entropy

Dirac Spatial Search with Electric Fields

Julien Zylberman, Fabrice Debbasch

Published Oct 31, 2021• 4 citations

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.

DOI: 10.3390/e23111441

Related papers

Quantum Spatial Search with Electric Potential: Long-Time Dynamics and Robustness to Noise

Thibault Fredon, Julien Zylberman, Pablo Arnault +1 more

arXiv:2210.13920EntropyDec 5, 20224 citations

Spatial search and the Dirac equation

Andrew M. Childs, Jeffrey Goldstone

arXiv:quant-ph/0405120Physical Review AOct 19, 2004145 citations

Dirac quantum walks with conserved angular momentum

Gareth Jay, Pablo Arnault, Fabrice Debbasch

arXiv:2007.06211Jul 13, 20200 citations

Search on a hypercubic lattice using a quantum random walk. I. d>2

Apoorva D. Patel, Md. Aminoor Rahaman

arXiv:1003.0065Physical Review ASep 28, 201035 citations

Spatial search by continuous-time quantum walks on crystal lattices

Andrew M. Childs, Yimin Ge

arXiv:1403.2676Physical Review AMay 30, 201446 citations

A new method to building Dirac quantum walks coupled to electromagnetic fields

Gareth Jay, Fabrice Debbasch, Junjie Wang

arXiv:1812.06729Dec 17, 20181 citation

Entropy

Dirac Spatial Search with Electric Fields

Julien Zylberman, Fabrice Debbasch

Published Oct 31, 2021• 4 citations

Publisher

Abstract

DOI: 10.3390/e23111441

Related papers

Quantum Spatial Search with Electric Potential: Long-Time Dynamics and Robustness to Noise

Thibault Fredon, Julien Zylberman, Pablo Arnault +1 more

We present various results on the scheme introduced in a previous work, 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 field centered on the the node to be found. 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 “diffusion” part, as it is called in Grover’s algorithm. The results are the following. First, we run long time simulations of this electric Dirac DQW, and observe that there is a second localization peak around the node marked by the oracle, reached in a time O(N), where N is the number of nodes of the 2D grid, with a localization probability scaling as O(1/lnN). This matches the state-of-the-art 2D-DQW search algorithms before amplitude amplification We then study the effect 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 first localization peak is even highly robust to spatiotemporal noise.We present various results on the scheme introduced in a previous work, 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 field centered on the the node to be found. 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 “diffusion” part, as it is called in Grover’s algorithm. The results are the following. First, we run long time simulations of this electric Dirac DQW, and observe that there is a second localization peak around the node marked by the oracle, reached in a time O(N), where N is the number of nodes of the 2D grid, with a localization probability scaling as O(1/lnN). This matches the state-of-the-art 2D-DQW search algorithms before amplitude amplification We then study the effect 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 first localization peak is even highly robust to spatiotemporal noise.

arXiv:2210.13920EntropyDec 5, 20224 citations

Spatial search and the Dirac equation

Andrew M. Childs, Jeffrey Goldstone

We consider the problem of searching a $d$ -dimensional lattice of $N$ sites for a single marked location. We present a Hamiltonian that solves this problem in time of order $\sqrt{N}$ for $d>2$ and of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\mathrm{log}\phantom{\rule{0.3em}{0ex}}N$ in the critical dimension $d=2$ . This improves upon the performance of our previous quantum walk search algorithm (which has a critical dimension of $d=4$ ), and matches the performance of a corresponding discrete-time quantum walk algorithm. The improvement uses a lattice version of the Dirac Hamiltonian, and thus requires the introduction of spin (or coin) degrees of freedom.We consider the problem of searching a $d$-dimensional lattice of $N$ sites for a single marked location. We present a Hamiltonian that solves this problem in time of order $\sqrt{N}$ for $d>2$ and of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\mathrm{log}\phantom{\rule{0.3em}{0ex}}N$ in the critical dimension $d=2$. This improves upon the performance of our previous quantum walk search algorithm (which has a critical dimension of $d=4$), and matches the performance of a corresponding discrete-time quantum walk algorithm. The improvement uses a lattice version of the Dirac Hamiltonian, and thus requires the introduction of spin (or coin) degrees of freedom.

arXiv:quant-ph/0405120Physical Review AOct 19, 2004145 citations

Dirac quantum walks with conserved angular momentum

Gareth Jay, Pablo Arnault, Fabrice Debbasch

A Quantum Walk (QW) simulating the flat $(1 + 2)$ D Dirac Eq.\ on a spatial polar grid is constructed. Because fermions are represented by spinors, which do not constitute a representation of the rotation group, but rather of its double cover, the QW can only be defined globally on an extended spacetime where the polar angle extends from $0$ to $4 π$ . The coupling of the QW with arbitrary electromagnetic fields is also presented. Finally, the cylindrical relativistic Landau levels of the Dirac Eq.\ are computed explicitly and simulated by the QW.A Quantum Walk (QW) simulating the flat $(1 + 2)$D Dirac Eq.\ on a spatial polar grid is constructed. Because fermions are represented by spinors, which do not constitute a representation of the rotation group, but rather of its double cover, the QW can only be defined globally on an extended spacetime where the polar angle extends from $0$ to $4 π$. The coupling of the QW with arbitrary electromagnetic fields is also presented. Finally, the cylindrical relativistic Landau levels of the Dirac Eq.\ are computed explicitly and simulated by the QW.

arXiv:2007.06211Jul 13, 20200 citations

Search on a hypercubic lattice using a quantum random walk. I. d>2

Apoorva D. Patel, Md. Aminoor Rahaman

Random walks describe diffusion processes, where movement at every time step is restricted to only the neighboring locations. We construct a quantum random walk algorithm, based on discretization of the Dirac evolution operator inspired by staggered lattice fermions. We use it to investigate the spatial search problem, that is, to find a marked vertex on a $d$ -dimensional hypercubic lattice. The restriction on movement hardly matters for $d>2$ , and scaling behavior close to Grover's optimal algorithm (which has no restriction on movement) can be achieved. Using numerical simulations, we optimize the proportionality constants of the scaling behavior, and demonstrate the approach to that for Grover's algorithm (equivalent to the mean-field theory or the $d\ensuremath{\rightarrow}\ensuremath{\infty}$ limit). In particular, the scaling behavior for $d=3$ is only about $25%$ higher than the optimal $d\ensuremath{\rightarrow}\ensuremath{\infty}$ value.Random walks describe diffusion processes, where movement at every time step is restricted to only the neighboring locations. We construct a quantum random walk algorithm, based on discretization of the Dirac evolution operator inspired by staggered lattice fermions. We use it to investigate the spatial search problem, that is, to find a marked vertex on a $d$-dimensional hypercubic lattice. The restriction on movement hardly matters for $d>2$, and scaling behavior close to Grover's optimal algorithm (which has no restriction on movement) can be achieved. Using numerical simulations, we optimize the proportionality constants of the scaling behavior, and demonstrate the approach to that for Grover's algorithm (equivalent to the mean-field theory or the $d\ensuremath{\rightarrow}\ensuremath{\infty}$ limit). In particular, the scaling behavior for $d=3$ is only about $25%$ higher than the optimal $d\ensuremath{\rightarrow}\ensuremath{\infty}$ value.

arXiv:1003.0065Physical Review ASep 28, 201035 citations

Spatial search by continuous-time quantum walks on crystal lattices

Andrew M. Childs, Yimin Ge

We consider the problem of searching a general $d$ -dimensional lattice of $N$ vertices for a single marked item using a continuous-time quantum walk. We demand locality, but allow the walk to vary periodically on a small scale. By constructing lattice Hamiltonians exhibiting Dirac points in their dispersion relations and exploiting the linear behavior near a Dirac point, we develop algorithms that solve the problem in a time of $O(\sqrt{N})$ for $d>2$ and $O(\sqrt{N}\phantom{\rule{0.16em}{0ex}}logN)$ in $d=2$ . In particular, we show that such algorithms exist even for hypercubic lattices in any dimension. Unlike previous continuous-time quantum walk algorithms on hypercubic lattices in low dimensions, our approach does not use external memory.We consider the problem of searching a general $d$-dimensional lattice of $N$ vertices for a single marked item using a continuous-time quantum walk. We demand locality, but allow the walk to vary periodically on a small scale. By constructing lattice Hamiltonians exhibiting Dirac points in their dispersion relations and exploiting the linear behavior near a Dirac point, we develop algorithms that solve the problem in a time of $O(\sqrt{N})$ for $d>2$ and $O(\sqrt{N}\phantom{\rule{0.16em}{0ex}}logN)$ in $d=2$. In particular, we show that such algorithms exist even for hypercubic lattices in any dimension. Unlike previous continuous-time quantum walk algorithms on hypercubic lattices in low dimensions, our approach does not use external memory.

arXiv:1403.2676Physical Review AMay 30, 201446 citations

A new method to building Dirac quantum walks coupled to electromagnetic fields

Gareth Jay, Fabrice Debbasch, Junjie Wang

A quantum walk whose continuous limit coincides with Dirac equation is usually called a Dirac Quantum Walk (DQW). A new systematic method to build DQWs coupled to electromagnetic (EM) fields is introduced and put to test on several examples of increasing difficulty. It is first used to derive the EM coupling of a well-known $3D$ walk on the cubic lattice. Recently introduced DQWs on the triangular and honeycomb lattice are then re-derived, showing for the first time that these are the only DQWs that can be defined with spinors living on the vertices of these lattices. As a third example of the method's effectiveness, a new $3D$ walk on a parallelepiped lattice is derived. As a fourth, negative example, it is shown that certain lattices like the rhombohedral lattice cannot be used to build DQWs. The effect of changing representation in the Dirac equation is also discussed.A quantum walk whose continuous limit coincides with Dirac equation is usually called a Dirac Quantum Walk (DQW). A new systematic method to build DQWs coupled to electromagnetic (EM) fields is introduced and put to test on several examples of increasing difficulty. It is first used to derive the EM coupling of a well-known $3D$ walk on the cubic lattice. Recently introduced DQWs on the triangular and honeycomb lattice are then re-derived, showing for the first time that these are the only DQWs that can be defined with spinors living on the vertices of these lattices. As a third example of the method's effectiveness, a new $3D$ walk on a parallelepiped lattice is derived. As a fourth, negative example, it is shown that certain lattices like the rhombohedral lattice cannot be used to build DQWs. The effect of changing representation in the Dirac equation is also discussed.

arXiv:1812.06729Dec 17, 20181 citation

We consider the problem of searching a

d

-dimensional lattice of

N

sites for a single marked location. We present a Hamiltonian that solves this problem in time of order

\sqrt{N}

for

d>2

and of order

\sqrt{N}\phantom{\rule{0.3em}{0ex}}\mathrm{log}\phantom{\rule{0.3em}{0ex}}N

in the critical dimension

d=2

. This improves upon the performance of our previous quantum walk search algorithm (which has a critical dimension of

d=4

), and matches the performance of a corresponding discrete-time quantum walk algorithm. The improvement uses a lattice version of the Dirac Hamiltonian, and thus requires the introduction of spin (or coin) degrees of freedom.

A Quantum Walk (QW) simulating the flat

(1 + 2)

D Dirac Eq.\ on a spatial polar grid is constructed. Because fermions are represented by spinors, which do not constitute a representation of the rotation group, but rather of its double cover, the QW can only be defined globally on an extended spacetime where the polar angle extends from

0

4 π

. The coupling of the QW with arbitrary electromagnetic fields is also presented. Finally, the cylindrical relativistic Landau levels of the Dirac Eq.\ are computed explicitly and simulated by the QW.

d

-dimensional hypercubic lattice. The restriction on movement hardly matters for

d>2

, and scaling behavior close to Grover's optimal algorithm (which has no restriction on movement) can be achieved. Using numerical simulations, we optimize the proportionality constants of the scaling behavior, and demonstrate the approach to that for Grover's algorithm (equivalent to the mean-field theory or the $d\ensuremath{\rightarrow}\ensuremath{\infty}$ limit). In particular, the scaling behavior for

d=3

is only about

25%

higher than the optimal $d\ensuremath{\rightarrow}\ensuremath{\infty}$ value.

We consider the problem of searching a general

d

-dimensional lattice of

N

vertices for a single marked item using a continuous-time quantum walk. We demand locality, but allow the walk to vary periodically on a small scale. By constructing lattice Hamiltonians exhibiting Dirac points in their dispersion relations and exploiting the linear behavior near a Dirac point, we develop algorithms that solve the problem in a time of

O(\sqrt{N})

for

d>2

and

O(\sqrt{N}\phantom{\rule{0.16em}{0ex}}logN)

d=2

. In particular, we show that such algorithms exist even for hypercubic lattices in any dimension. Unlike previous continuous-time quantum walk algorithms on hypercubic lattices in low dimensions, our approach does not use external memory.

3D

walk on the cubic lattice. Recently introduced DQWs on the triangular and honeycomb lattice are then re-derived, showing for the first time that these are the only DQWs that can be defined with spinors living on the vertices of these lattices. As a third example of the method's effectiveness, a new

3D

walk on a parallelepiped lattice is derived. As a fourth, negative example, it is shown that certain lattices like the rhombohedral lattice cannot be used to build DQWs. The effect of changing representation in the Dirac equation is also discussed.