# Dirac Spatial Search with Electric Fields

Julien Zylberman, Fabrice Debbasch

► To cite this version:

Julien Zylberman, Fabrice Debbasch. Dirac Spatial Search with Electric Fields. Entropy, 2021, 23 (11), pp.1441. 10.3390/e23111441. hal-03457304

HAL Id: hal-03457304

https://hal.science/hal-03457304

Submitted on 17 Jun 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Article

# Dirac Spatial Search with Electric Fields

Julien Zylberman * and Fabrice Debbasch *

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

* Correspondences: julien.zylberman@gmail.com (J.Z.); fabrice.debbasch@gmail.com (F.D.)

**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 $\sqrt{N}$ for small values of *N* and tends asymptotically to a constant for larger *Ns*, thus offering a speed-up over conventional methods.

**Keywords:** spatial search; quantum walks; Dirac equation; electric field

## 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–14]. Unitary QWs are also a universal primitive of unitary computation [15–17] useful in quantum information and algorithmic development [5,18–22]. Moreover, several spatial search algorithms based on QWs have been proposed [23–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–34]. Some of these unitary QWs work in continuous time [35–39], while others work in discrete time [40–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–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 2D 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 2D 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 $\Omega$ and show by

<figure><img src="image_2.png" /></figure>

### check for updates

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

Academic Editor: Paolo Bordone

Received: 12 September 2021

Accepted: 28 October 2021

Published: 31 October 2021

**Publisher's Note:** MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

<figure><img src="image_3.png" /></figure>

**Copyright:** © 2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
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 $\sqrt{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 $\sqrt{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) \in \mathbb{N}_M^2$, with M an arbitrary strictly positive integer. The integers p and q can be considered as discrete Cartesian coordinates in 2D 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 \in \mathbb{N}$. Given a basis $\langle |b_L\rangle, |b_R\rangle \rangle$ of an Hilbert space $\mathcal{H}_2$ named the 'spin'-space, the wave-function $\psi \in \mathcal{H}_2$ of the DTQW is represented by its two components $\psi^L$ and $\psi^R$. The equations of motion of the walks considered in this article are of the form $\psi_{j+1} = U\psi_j$ where U is a unitary operator independent of the time j. This operator is $U = \exp(ieV) \cdot R(\theta^+) \cdot S_q \cdot R(\theta^-) \cdot S_p$ where $S_p$ and $S_q$ are the standard shift operators defined by the following equations:

$$ (S_p \psi)_{p,q}^L = \psi_{p+1,q}^L \\ (S_p \psi)_{p,q}^R = \psi_{p-1,q}^L \qquad (1) $$

and

$$ (S_q \psi)_{p,q}^L = \psi_{p,q+1}^L \\ (S_q \psi)_{p,q}^R = \psi_{p,q-1}^L. \qquad (2) $$

The operator $R(\theta)$ is a rotation in spin space and is represented in the basis $\langle |b_L\rangle, |b_R\rangle \rangle$ by the matrix

$$ R = \begin{bmatrix} \cos(\theta) & -i \sin(\theta) \\ -i \sin(\theta) & \cos(\theta) \end{bmatrix} \qquad (3) $$

where $\theta^\pm = \pm(\pi/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(ieV)\psi)_{p,q} = \exp(ieV_{p,q})\psi_{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 $\psi$ 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 $\epsilon$ much lower than unity such that, in a certain domain in $(j, p, q)$-space, the wave-function $\psi$ varies on scales of order $\epsilon^{-1}$ in its three variables $j, p$ and $q$. Then, define the 'slow' variables $t = \epsilon j, x = \epsilon p$ and $y = \epsilon q$ so that $\psi$ varies on scales of order unity in these new variables. Suppose also that, in the same domain, the quantities $eV$ and $m$ are of order $\epsilon$ and write $eV = \epsilon e \tilde{V}$ and $m = \epsilon \tilde{m}$. The discrete equations of the motion for the walk can then be expanded in powers of $\epsilon$ around $\epsilon = 0$. This expansion delivers the identity $\psi = \psi$ at zeroth order in $\epsilon$ but, at first order, one obtains the following.

$$ (\partial_t - ie\tilde{V})\psi^L - \partial_x\psi^L - i\partial_y\psi^R + i\tilde{m}\psi^R = 0 \\ (\partial_t - ie\tilde{V})\psi^R + \partial_x\psi^R + i\partial_y\psi^L + i\tilde{m}\psi^L = 0. \qquad (4) $$
This equation coincides with the flat (1 + 2)D space-time Dirac equation for a spinor of mass $\tilde{m}$ and electric charge $-e$ propagating in the electric potential $\tilde{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 - \Omega_p)^2 + (q - \Omega_q)^2)^{-1/2}, \qquad (5)$$

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 $\Omega = (\Omega_p, \Omega_q)$. To ensure that the walk is defined at all points in the grid, the point $\Omega$ where $V$ diverges must not be on the grid. A simple possibility is to choose $\Omega$ at the center of a grid-cell equidistant from the four vertices of this cell. The distance in the $(p, q)$ Euclidean plane between $\Omega$ and these 4 points is then $1/\sqrt{2}$, and the maximum value taken by the function $V$ on the grid is the following.

$$V_{\max} = Q\sqrt{2}. \qquad (6)$$

At given $\Omega$, $m$ and $N$, the walk is entirely controlled by the initial condition and the parameter $a = eQ$. The maximum value of the global phase is $a_{\max} = eV_{\max} = eQ\sqrt{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 $\Omega$. 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,\Omega_p+1/2,\Omega_q+1/2} + P_{j,\Omega_p-1/2,\Omega_q+1/2} + P_{j,\Omega_p+1/2,\Omega_q-1/2} + P_{j,\Omega_p-1/2,\Omega_q-1/2} \quad (7)$$

with

$$P_{j,p,q} = |\psi_{j,p,q}^L|^2 + |\psi_{j,p,q}^R|^2. \qquad (8)$$

The probability $P_j^*$ depends in a non trivial manner on the free parameters $\Omega$, $m$, $N$ and $eQ$. 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 $\Omega$, $m$, $N$ and $a = eQ$, 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 $\Omega = \Omega_0$ located at the center of the central grid cell but for different values of $a$. Changing $\Omega$ 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$, $\Omega = \Omega_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 $\sim 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.
<figure><img src="image_4.png" /><figcaption>**Figure 1.** Evolution of $P_j^*$ with time $j$ for $N = 120^2$, $\Omega = \Omega_0$, $m = 0$, $eQ = 0.01$ (**left**) and $eQ = 1$ (**right**).</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Figure 2.** Evolutions of $P_j^*$ with time $j$ for $N = 120^2$, $\Omega = \Omega_0$, $eQ = 1$ and mass $m = 0.08$ (**left**) or $m = 0.25$ (**right**).</figcaption></figure>

Density profiles corresponding to the first maximum and the first minimum of $P_j^*$ are presented in Figures 3 and 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 $\Omega_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 Figures 3–5 are non symmetric around the central point $\Omega$; in particular, the walker does not distribute evenly among the four vertices that surround $\Omega$. 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 $\psi^L$ and $\psi^R$. Switching to an initial condition with vanishing $\psi^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.
<figure><img src="image_6.png" /><figcaption>**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 $eQ = 0.01$, $N = 120^2$ and $\Omega = \Omega_0$.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>**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 $eQ = 1$, $N = 120^2$ and $\Omega = \Omega_0$.</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>**Figure 5.** Density profiles at times $j = 5$ (**up**) and $j = 6$ (**down**) for $eQ = 1$, $N = 120^2$ and $\Omega = \Omega_0$.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>**Figure 6.** Density contours at time $j = 61$ corresponding to the first maximum of $P_j^*$ for $eQ = 0.01$, $N = 120^2$, $\Omega = \Omega_0$ and two different initial conditions: $\psi^L = \psi^R$ (**up**) and $\psi^R = 0$ (**down**).</figcaption></figure>
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 \times 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 \sim 86 \times 6.94 \times 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 $\Omega$ 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 Figures 7 and 8 for $\Omega = \Omega_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 $\sqrt{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 $\bar{P}_j^* = 4P_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 $\sqrt{N}$ scaling and the constant asymptotic behaviour can naturally be observed in this figure too. Figure 8 also shows that, quite remarkably, the function $\bar{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$.

<figure><img src="image_10.png" /><figcaption>**Figure 7.** Time $T$ for the first maximum of $\bar{P}_j^*$ in function of $\sqrt{N}$ for $eQ = 0.9$, $\Omega = \Omega_0$ and $m = 0$. The function fitting $T$ for small $N$ is approximately $0.96\sqrt{N} - 1.66$ and appears in yellow.</figcaption></figure>
<figure><img src="image_11.png" /><figcaption>**Figure 8.** Renormalised probability $\bar{P}_j^*$ against time $j$ for $eQ = 0.9$, $\Omega = \Omega_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).</figcaption></figure>

Let us end this section by a qualitative comment for explaining how the localisation time becomes independent 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 $\Omega$ has only been influenced by points at distance $\sim T_0$. If $\sqrt{N_0}/2$ is sufficiently lower than $T_0$, increasing $N$ will allow points around $\Omega$ to observe more distant points and will presumably modify $T_0$. However, suppose $\sqrt{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 \sim 84 \sim 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 $\sqrt{N_0}/2 > cT_0$ will present the same asymptotic property. Intuitively, the existence of such an $N$ seems linked to the rapid convergence towards $\Omega$ 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 $\sqrt{N}$ or $\sqrt{N} \log N$. The partial localisation time of these new walks does scale as $\sqrt{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(\sqrt{N})$ steps because the localisation we are speaking of is not total, and completing it with amplitude amplification would take $O(\sqrt{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 to 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:

QW Quantum Walk;

DTQW Discrete Time Quantum Walk.

**References**

1. Feynman, R.P.; Hibbs, A.R. *Quantum Mechanics and Path Integrals*; McGraw-Hill Book: New York, NY, USA, 1965.

2. Schweber, S.S. Feynman and the visualization of space-time processes. *Rev. Mod. Phys.* **1986**, *58*, 449. [CrossRef]

3. Aharonov, Y.; Davidovich, L.; Zagury, N. Quantum random walks. *Phys. Rev. A* **1993**, *48*, 1687. [CrossRef]

4. Meyer, D.A. From quantum cellular automata to quantum lattice gases. *J. Stat. Phys.* **1996**, *85*, 551–574. [CrossRef]

5. Manouchehri, K.; Wang, J.B. *Physical Implementation of Quantum Walks*; Springer: Berlin/Heidelberg, Germany, 2014.

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. [CrossRef]

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. [CrossRef] [PubMed]

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. [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. [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. [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. [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.

13. Georgopoulos, K.; Emary, C.; Zuliani, P. Comparison of quantum-walk implementations on noisy intermediate-scale quantum computers. *Phys. Rev. A* **2021**, *103*, 022408. [CrossRef]

14. Shakeel, A. Efficient and scalable quantum walk algorithms via the quantum Fourier transform. *Quantum Inf. Process.* **2020**, *19*, 1–26. [CrossRef]

15. Childs, A. Universal Computation by Quantum Walk. *Phys. Rev. Lett.* **2009**, *102*, 180501. [CrossRef]

16. Childs, A.M.; Gosset, D.; Webb, Z. Universal computation by multiparticle quantum walk. *Science* **2013**, *339*, 791–794. [CrossRef]
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. [CrossRef]

18. Ambainis, A. Quantum walks and their algorithmic applications. *Int. J. Quantum Inf.* **2003**, *1*, 507–518. [CrossRef]

19. Ambainis, A. Quantum walk algorithm for element distinctness. *SIAM J. Comput.* **2007**, *37*, 210–239. [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.

21. Magniez, F.; Nayak, A.; Roland, J.; Santha, M. Search via quantum walk. *SIAM J. Comput.* **2011**, *40*, 142–164. [CrossRef]

22. Portugal, R. *Quantum Walks and Search Algorithms*; Springer: Berlin/Heidelberg, Germany, 2013.

23. Ambainis, A. Quantum search algorithms. *ACM SIGACT News* **2004**, *35*, 22–35. [CrossRef]

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. [CrossRef]

25. Portugal, R. Staggered quantum walks on graphs. *Phys. Rev. A* **2016**, *93*, 062335. [CrossRef]

26. Abal, G.; Donangelo, R.; Marquezino, F.L.; Portugal, R. Spatial search on a honeycomb network. *Math. Struct. Comput. Sci.* **2010**, *20*, 999–1009. [CrossRef]

27. Childs, A.M.; Goldstone, J. Spatial search by quantum walk. *Phys. Rev. A* **2004**, *70*, 022314. [CrossRef]

28. Tulsi, A. Faster quantum-walk algorithm for the two-dimensional spatial search. *Phys. Rev. A* **2008**, *78*, 012310. [CrossRef]

29. Wong, T.G. Faster search by lackadaisical quantum walk. *Quantum Inf. Process.* **2018**, *17*, 1–9. [CrossRef]

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.

31. Grover, L.K. Quantum mechanics helps in searching for a needle in a haystack. *Phys. Rev. Lett.* **1997**, *79*, 325. [CrossRef]

32. Childs, A.M.; Goldstone, J. Spatial search and the Dirac equation. *Phys. Rev. A* **2004**, *70*, 042312. [CrossRef]

33. Guillet, S.; Roget, M.; Arrighi, P.; Molfetta, G. The Grover search as a naturally occurring phenomenon. *arXiv* **2019**, arXiv:1908.11213.

34. Patel, A.; Rahaman, M.A. Search on a hypercubic lattice using a quantum random walk. *I. Phys. Rev. A* **2010**, *82*, 032330. [CrossRef]

35. Wong, T.G. Spatial search by continuous-time quantum walk with multiple marked vertices. *Quantum Inf. Process.* **2016**, *15*, 1411–1443. [CrossRef]

36. Chakraborty, S.; Novo, L.; Roland, J. Optimality of spatial search via continuous-time quantum walks. *Phys. Rev. A* **2020**, *102*, 032214. [CrossRef]

37. Childs, A.M.; Ge, Y. Spatial search by continuous-time quantum walks on crystal lattices. *Phys. Rev. A* **2014**, *89*, 052337. [CrossRef]

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. [CrossRef]

39. Tanaka, H.; Sabri, M.; Portugal, R. Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk. *arXiv* **2021**, arXiv:2108.01992.

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. [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. [CrossRef]

42. Ambainis, A.; Kempe, J.; Rivosh, A. Coins make quantum walks faster. *arXiv* **2004**, arXiv:quant-ph/0402107.

43. Xue, X.L.; Ruan, Y.; Liu, Z.H. Discrete-time quantum walk search on Johnson graphs. *Quantum Inf. Process.* **2019**, *18*, 1–10. [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. [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. [CrossRef]

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. [CrossRef]

47. Arnault, P.; Debbasch, F. Quantum walks and discrete gauge theories. *Phys. Rev. A* **2016**, *93*, 052301. doi:10.1103/PhysRevA.93.052301

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. [CrossRef]

49. Di Molfetta, G.; Brachet, M.; Debbasch, F. Quantum walks as massless Dirac fermions in curved space-time. *Phys. Rev. A* **2013**, *88*, 042301. [CrossRef]

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. [CrossRef]

51. Arrighi, P.; Facchini, S.; Forets, M. Quantum walking in curved spacetime. *Quantum Inf. Process.* **2016**, *15*, 3467–3486. [CrossRef]

52. Arrighi, P.; Facchini, S. Quantum walking in curved spacetime: (3 + 1) dimensions, and beyond. *Quantum Inf. Comput.* **2017**, *17*, 810–824.
53. Arnault, P.; Debbasch, F. Quantum walks and gravitational waves. *Ann. Phys.* **2017**, *383*, 645–661. [CrossRef]

54. Arnault, P.; Di Molfetta, G.; Brachet, M.; Debbasch, F. Quantum walks and non-Abelian discrete gauge theory. *Phys. Rev. A* **2016**, *94*, 012335. [CrossRef]

55. Debbasch, F. Discrete geometry from quantum walks. *Condens. Matter* **2019**, *4*, 40. [CrossRef]

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. [CrossRef]

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. [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. [CrossRef]

59. Altshuler, B.; Krovi, H.; Roland, J. Anderson localization makes adiabatic quantum optimization fail. *Proc. Natl. Acad. Sci. USA* **2010**, *107*, 12446–12450. [CrossRef] [PubMed]