1 Introduction

Quantum walks are proven to be a universal model of quantum computation, equivalent to the quantum circuit (gate) model [1,2,3,4,5]. Quantum walks can directly be mapped onto quantum circuits and executed by quantum computers [6,7,8] and can also be implemented in various platforms [9]. Furthermore, quantum walks can be combined with quantum cellular automata to perform efficient quantum computations [10,11,12]. Among others, quantum walks have been used in quantum search [13, 14], in data safety [15], in Hash functions generation [16], in quantum encryption [17], in quantum transport, in graphene [18, 19] and in the simulation of bosonic and fermionic quantum systems [20].

In all above quantum walk applications, the quantum walk evolves freely in one and two-dimensional lattices and graphs, i.e., in spaces with no applied potentials. The specificities of each problem enter the quantum computation through the structure of lattices and graphs. Areas in which the quantum walker should not enter are defined using broken links.

In this paper, we extent the quantum walk model of quantum computation by introducing potentials in the spaces where the quantum walk evolves. The quantum walker carries a “charge” which is affected by the applied potential and, therefore, the potential profiles can be used to enter the inputs of the specific quantum computation in addition to the structure of lattices and graphs. The output of the quantum computation is the probability distribution of the possible locations of the quantum walker, or, in specific cases, the final location of the quantum walker. The fact that the quantum walker carries a “charge” along with the fact that the probability amplitudes of its location change with time, allows us to use quantum phase gates to introduce the potential effect on the evolution of the quantum walk.

In the next section, we present the formulation of the quantum walk in spaces with potentials. In the third section, we present the mapping of the model onto quantum circuits and simulate the function of the circuit modules using Qiskit and IBM’s quantum computer. In the fourth section we study the evolution of quantum walks in one-dimensional spaces with applied potentials, with an emphasis on the reproduction of the tunneling through a potential barrier phenomenon. In the next section, we study the quantum walk evolution in two-dimensional spaces with applied potentials. In the sixth section we apply our model to develop a basis for maze-running and routing quantum algorithms and we introduce time-varying potentials and study the possibility of using quantum walks to simulate the motion of vehicles in urban spaces. Immovable obstacles such as curbs and buildings are modeled as impenetrable potential barriers. Traffic lights are modeled as time-varying potential barriers. Red traffic lights are modeled as potential barriers with near-zero transmission coefficients and green lights as zero applied potentials. Finally, we present our conclusions. We believe that quantum walks in spaces with applied potentials can be used as a basis to develop novel quantum algorithms and also novel hybrid quantum/classical algorithms.

2 Model formulation

We formulate our model using the one-dimensional discrete quantum walk. Its extension to more dimensions is straightforward. The quantum walk evolves in a one-dimensional discrete lattice and the associated quantum computational basis is \(|n\rangle\), where n is a positive integer representing the lattice sites. The basis states \(|n\rangle\) label the possible positions of the quantum walker and span the corresponding Hilbert space, HP, which is called the position space [1, 2]. To determine the direction of the quantum walker motion, a two-state quantum system, called a coin, is used. The coin basis states are labeled as \(|0\rangle\) and \(|1\rangle\) and span a two-dimensional Hilbert space, HC, called the coin space [1, 2]. The quantum walk evolves in the Hilbert space, HQW, which comprises HP and HC and is given by their tensor product:

$$\begin{array}{c}{H}_{QW}= {H}_{P} \otimes {H}_{C}\end{array}$$
(1)

Next, we define the unitary operators that act on the basis states and drive the quantum walk. The first operator acts on the coin basis states and is called the coin operator, \(\widehat{C}\). The coin operator is represented by a 2X2 unitary matrix:

$$\begin{array}{c}\widehat{C}= \left[\begin{array}{cc}{a}_{11}& {a}_{12}\\ {a}_{21}& {a}_{22}\end{array}\right] \end{array}$$
(2)

The action of \(\widehat{C}\) on the coin basis states is given by:

$$\begin{array}{c}\widehat{C}|0\rangle = \left[\begin{array}{cc}{a}_{11}& {a}_{12}\\ {a}_{21}& {a}_{22}\end{array}\right] \left[\begin{array}{c}1\\ 0\end{array}\right]=\left[\begin{array}{c}{a}_{11}\\ {a}_{21}\end{array}\right]= {a}_{11}|0\rangle + {a}_{21}|1\rangle \end{array}$$
(3)

and

$$\begin{array}{c}\widehat{C}|1\rangle = \left[\begin{array}{cc}{a}_{11}& {a}_{12}\\ {a}_{21}& {a}_{22}\end{array}\right] \left[\begin{array}{c}0\\ 1\end{array}\right]=\left[\begin{array}{c}{a}_{12}\\ {a}_{22}\end{array}\right]= {a}_{12}|0\rangle + {a}_{22}|1\rangle \end{array}$$
(4)

The second operator is called the shift operator, \(\widehat{S}\), and acts on the position basis states. \(\widehat{S}\) shifts the quantum walker to the left or right according to the current coin state. Suppose that at time step t the quantum walker is located at lattice site i with probability amplitude \({a}_{i,t}\). The coin is tossed at time step t + 1 and if its state is \(|0\rangle\) the action of shift operator moves the walker to lattice site i-1 and the probability amplitude becomes \({a}_{i,t+1}\):

$$\begin{array}{c}\widehat{S} |0\rangle {a}_{i,t} |i\rangle = |0\rangle {a}_{i,t+1} |i-1\rangle \end{array}$$
(5)

If the coin state is \(|1\rangle\) the action of shift operator moves the walker to lattice site i + 1 with amplitude \({a{^{\prime}}}_{i,t+1}\):

$$\begin{array}{c}\widehat{S} |1\rangle {a}_{i,t} |i\rangle = |1\rangle {a{^{\prime}}}_{i,t+1} |i+1\rangle \end{array}$$
(6)

Therefore, the shift operator acting on a lattice with m sites is given by:

$$\begin{array}{c}\widehat{S}= |0\rangle \langle 0| \otimes \sum\limits_{i=1}^{m}|i-1\rangle \langle i|+ |1\rangle \langle 1| \otimes \sum\limits_{i=1}^{m}|i+1\rangle \langle i|\end{array}$$
(7)

The combined operator that acts to evolve the quantum walk, \(\widehat{U}{ }_{QW}\), is given by:

$$\begin{array}{c}\widehat{U}{ }_{QW}= \widehat{S} \left(\widehat{C} \otimes I\right)\end{array}$$
(8)

The quantum walk formulation described above applies to free spaces, i.e., spaces in which no potentials are applied. We extend the quantum walk formulation in spaces with applied potentials. In this case, the quantum walker carries a “charge” that is affected by the applied potential.

As all quantum systems, quantum walks can also be described by the Schrödinger equation. The Hamiltonian operator comprises a kinetic and a potential energy term:

$$\begin{array}{c}\widehat{H}\hspace{0.33em}=\hspace{0.33em}-\frac{{\hslash }^{2}}{2m}\hspace{0.33em}\frac{{\partial }^{2}}{\partial {x}^{2}}\hspace{0.33em}+\hspace{0.33em}V\left(x,t\right)\end{array}$$
(9)

A solution to the Schrödinger equation has the form:

$$\begin{array}{c}\widehat{U}=\mathit{exp}\left(\frac{it}{\hslash }\hspace{0.33em}\frac{{\hslash }^{2}}{2m}\hspace{0.33em}\frac{{\partial }^{2}}{\partial {x}^{2}}\right)\mathit{exp}\hspace{0.33em}\left(\frac{-it}{\hslash }V\left(x,t\right)\right)\end{array}$$
(10)

The first exponential of the unitary operator \(\widehat{U}\) corresponds to the kinetic energy part, which in the quantum walk model is expressed by the operator \(\widehat{U}{ }_{QW}\). The second exponential corresponds to the potential energy. In the case of quantum walks, the potential energy at lattice site i at time step t is \(V(i,t)\) and it is the potential energy of the quantum walker when located at site i. But the motion of the quantum walker is not continuous. During its motion from lattice site i to lattice sites i-1 or i + 1 its motion will be affected by the potential differences between these lattice sites:

$$\begin{array}{c}V\left(i-1,i,t\right)=V\left(i-1,t\right)-V\left(i,t\right)\end{array}$$
(11)

and

$$\begin{array}{c}V\left(i+1,i,t\right)=V\left(i+1,t\right)-V\left(i,t\right)\end{array}$$
(12)

If the applied potential is constant in time, the index t can be dropped.

Consider a quantum walker located at time step t at site i with probability amplitude \({a}_{i,t}\) and coin state \(|0\rangle\). After the action of \(\widehat{U}{ }_{QW}\) the new state of the quantum walker will be:

$$|0\rangle a_{{i,t}} |i\rangle \to |0\rangle a_{{i,t}} a_{{11}} |i - 1\rangle + |1\rangle a_{{i,t}} a_{{21}} |i + 1\rangle = |0\rangle a_{{i,t + 1}} |i - 1\rangle + |1\rangle {\text{ }}a_{{i,t + 1}}^{\prime } |i + 1\rangle$$
(13)

As expressed in Eq. (10), when the quantum walker moves from a site i to the two neighboring sites it peaks up a phase factor that depends on the value of the potential applied in these sites:

$$\begin{array}{c}\mathrm{exp}\left(i \varphi (i,t\right))= \mathit{exp}\hspace{0.33em}\left(\frac{-it}{\hslash }V\left(i,t\right)\right)\end{array}$$
(14)

This potential depended phase factor is introduced using phase quantum gates. In this case Eq. (13) becomes:

$$|0\rangle {a}_{i,t} |i\rangle \to \mathrm{exp}\left(i \varphi \left(i-1,t\right)\right)|0\rangle {a}_{i,t} {a}_{11}|i-1\rangle + \mathrm{exp}\left(i \varphi \left(i+1,t\right)\right)|1\rangle {{a}_{i,t} a}_{21}|i+1\rangle =\begin{array}{c}\mathrm{exp}\left(i \varphi \left(i-1,t\right)\right)|0\rangle {a}_{i,t+1} |i-1\rangle + \mathrm{exp}\left(i \varphi \left(i+1,t\right)\right) |1\rangle {{a}^{^{\prime}}}_{i,t+1}|i+1\rangle \end{array}$$
(15)

Equation (15) describes the motion of the quantum walker from site i to site i-1 and to site i + 1. The formulation presented above is in agreement with the results of experimental realization of electric quantum walks using Cs atoms as lattice sites [21].

3 Quantum circuits for quantum walks

Several implementations of quantum walks in free spaces using quantum circuits have been proposed [6,7,8,9]. Here we implement quantum walks in spaces with applied potentials using quantum circuits and execute one and two-dimensional quantum walks using the Qiskit simulator and IBM’s quantum computer [22, 23]. Phase rotation quantum gates are used to introduce the applied potentials in the evolution of quantum walks.

The quantum circuit implementing quantum walk in a one-dimensional space with five lattice sites is shown in Fig. 1a. The quantum walk starts at site 3. Eight phase rotation gates are used in this circuit to model the effect of any applied potential to the quantum walk.

Fig. 1
figure 1

a Quantum circuit for the one-dimensional quantum walk in spaces with applied potentials implemented using Qiskit. b The computed probability distribution of the quantum walker location after the first time step

Full size image

The probability distribution of the quantum walker location is computed by IBM’s quantum computer. Figure 1b shows the probability distribution after the first time step. The lattice sites 1 to 5 correspond to qubits \(|{q}_{1}\rangle\) to \(|{q}_{5}\rangle\). The quantum coin is qubit \(|{q}_{0}\rangle\). To execute the next step of the quantum walk, the circuit of Fig. 1a is repeated as shown in Fig. 2a and the computed probability distribution after the second step is shown in Fig. 2b.

Fig. 2
figure 2

a Quantum circuit for the second time step of the one-dimensional quantum walk in spaces with applied potentials implemented using Qiskit. b The computed probability distribution of the quantum walker location after the second time step

Full size image

To execute quantum walks in spaces with more lattice sites and for more time steps the circuit of Fig. 1a is repeated both in time (x-axis) and space (y-axis). The computation results are subjected to errors introduced during the quantum computation.

Next, we implement quantum walks in a two-dimensional space. The lattice sites form a cross and the center site corresponds to qubit \(|{q}_{5}\rangle\). The left site corresponds to qubit \(|{q}_{4}\rangle\), the right site to \(|{q}_{6}\rangle\), the up site to qubit \(|{q}_{3}\rangle\) and the down site to qubit \(|{q}_{7}\rangle\). Two quantum coins are used in this case. Figure 3a shows the quantum circuit implementing the two-dimensional quantum walk in spaces with any applied potential. Figure 3b shows the results produced by IBM’s quantum computer for the probability distribution of the quantum walker location after the first time step. Again, the computation results are subjected to errors introduced during the quantum computation. Scaling of the circuit of Fig. 3a to execute two-dimensional quantum walks in larger lattices and for more time steps is straightforward.

Fig. 3
figure 3

a Quantum circuit for the two-dimensional quantum walk in spaces with applied potentials implemented using Qiskit. b The computed probability distribution of the quantum walker location after the first time step

Full size image

4 Quantum walks in one-dimensional spaces with applied potentials

Quantum walks in free spaces are directional depending on the initial state of the quantum coin. Since the quantum walker in potential spaces caries a charge, we use this property to define a “positive” quantum walker charge if the initial coin state is \(|0\rangle\) and a “negative” charge if the initial coin state is \(|1\rangle\).

Figure 4 shows the probability distribution of the quantum walker location in a space with a linear applied potential at time step 150. The potential is represented by the red line. In Fig. 4a the quantum walker carries a “positive” charge and in Fig. 4b a “negative” charge. Attributing a signed charge to quantum walkers in potential spaces opens the way for new applications of quantum walks as models of physical systems and processes.

Fig. 4
figure 4

Probability distribution of the quantum walker location in a space with a linear applied potential at time step 150. a Quantum walker carries a “positive” charge. b Quantum walker carries a negative charge

Full size image

Next, we study the quantum walk evolution is spaces where potential barriers are present. Our aim is to reproduce the tunneling through a barrier phenomenon. Figure 5 shows the probability distribution of the quantum walker location in a space where a potential barrier is present. The potential barrier is represented by the red line. The potential barrier transmission and reflection coefficients are analogous to the total probability of the walker location to the left of the potential barrier and to the total probability of the walker location to the right of the barrier after reaching the barrier and reflected by it.

Fig. 5
figure 5

Probability distribution of the quantum walker location in a space with a potential barrier. The tunneling phenomenon is reproduced

Full size image

5 Quantum walks in two-dimensional spaces with applied potentials

Quantum walks can evolve in two-dimensional spaces with any applied potential distribution. In this case two quantum coins forming a quantum register are used, one for motion along the x-axis and one along the y-axis. Furthermore, depending on the quantum coin initial states four charge configurations can be used.

Figure 6 shows the quantum walk evolution in a space where a linear potential is applied shown by the inclined plane in Fig. 6a. On this potential plane, a potential well, a potential barrier and an L-shaped potential barrier are added. The quantum walk starts at the center of the plane with initial coins states \(|01\rangle\). Figure 6b shows the probability distribution of the quantum walker location at time step 75, and Fig. 6c shows the top view of the probability distribution. Tunneling and reflections from the potential barriers along with localization in the quantum well produce an interesting probability distribution.

Fig. 6
figure 6

Quantum walk evolution in a space with a linear applied potential on which a quantum well, a potential barrier and an L-shaped potential barrier are present. The initial quantum coins state is \(|01\rangle .\) a Potential distribution. b Probability distribution of the quantum walker location. c Top view of the quantum walker location probability distribution

Full size image

Another case is shown in Fig. 7. Again a linear potential is applied with a diagonal potential well facing a potential barrier, as shown in Fig. 7a.

Fig. 7
figure 7

Quantum walk evolution in a space with a linear applied potential on which a diagonal quantum well facing a potential are present. The initial quantum coins state is \(|00\rangle .\) a Potential distribution. b Probability distribution of the quantum walker location. c Top view of the quantum walker location probability distribution

Full size image

The quantum walk starts at the center of the plane with initial coins states \(|00\rangle\). Figure 7b shows the probability distribution of the quantum walker location at time step 75, and Fig. 7c shows the top view of the probability distribution.

6 Applications

The extension of quantum walks in spaces with applied potentials and the assignment of “charge” to the quantum walker breaks new ground for practical quantum computing applications. In this section we present two models which can serve as a basis for applied quantum computing to maze running, routing and to control of moving robots, nano-robots or vehicles.

Maze running and routing algorithms are very useful in many engineering problems such as routing in VLSI physical design, finding shortest paths etc. Quantum walks in free spaces have been proven to achieve shortest hitting times that their classical counterparts. In most applications the point of entrance into the maze (IN) and the exit point (OUT) are known, but classical algorithms cannot exploit this information adequately. In quantum maze running even approximate knowledge of the location of the exit point provides a significant speedup. Such an example is shown in Fig. 8.

Fig. 8
figure 8

Quantum walk for maze running. a Potential distribution forming a maze. The entrance point is labeled with IN and the exit point with OUT. b Top view of the quantum walker location probability distribution

Full size image

In Fig. 8a, the maze is modeled as a number of potential barriers corresponding to maze “walls”. The information of the side on which the exit point is located is used to apply an additional linear potential in which the entrance point is located at a high potential area and the exit point at a low potential area. Figure 8b shows the top view of the quantum walker probability distribution. The path with the highest probability, marked with a black line, connects the entrance to the exit. The quantum walker in the above described potential searches in superposition all possible paths and reaches the exit point very fast. It is worth noting that by increasing the potential barrier heights, their reflection coefficients are increased and the resulting interference accelerates the quantum walk.

The second application incorporates time varying potentials. Figure 9a shows a potential distribution that models a space with immovable obstacles, which are represented by high and thick potential barriers and a time-varying obstacle represented by a lower narrow barrier. If the quantum walker represents a moving vehicle, then immovable obstacles correspond to buildings and curves and the time-varying obstacles to traffic lights. In this context, Fig. 9a shows a vehicle stopped in front of a red traffic light. Green traffic lights correspond to the absence of barriers in road junctions. The additional linear potential models the route the vehicle wishes to follow, which in this case is to turn to the right. Figure 9b shows the probability distribution of the quantum walker location at time step 5.

Fig. 9
figure 9

Quantum walk describing the motion of a moving vehicle or robot in a space with constant and time varying potentials. High potential barriers correspond to immovable obstacles and a lower and narrower potential barrier to time-varying obstacles such as traffic lights. a Initial location of the vehicle (quantum walker) b Probability distribution of the quantum walker location at time step 5

Full size image

In Fig. 10a, the red light turned green and green lights at two other junctions turned red. As sown in Fig. 10b the quantum walker turns to the right and moves along the high probability path indicated by the black line. This quantum walk approach is scalable and can serve as a basis for many moving entities in spaces with immovable and time-varying obstacles. Interference between different quantum walkers can provide useful information about collision probabilities resulting in an effective navigation of the moving entities.

Fig. 10
figure 10

a The lower potential barrier (red light) of Fig. 9a is removed (green light) and low potential barriers appear at two other junctions. b The vehicle turns to the right following the desired direction indicated by the black line

Full size image

7 Conclusion

We extended the universal quantum computation model of quantum walks in spaces with applied potentials. We showed that quantum walks in such spaces can be mapped onto quantum circuits and therefore the resulting quantum algorithms can be executed by quantum computers. We applied quantum walks in one and two dimensional spaces. Furthermore, we demonstrated with two applications that the proposed quantum walk formulation can serve as a basis for the development of novel quantum algorithms for real life applications. In addition, the assignment of “charge” to quantum walkers may facilitate theoretical simulations of quantum field interactions with charge carrying particles.