# Quantum walks and Dirac cellular automata on a programmable trapped-ion quantum computer

Jul 24, 2020

### Review of quantum walks and the connection to the Dirac equation

The DQW consists of two quantum mechanical systems, an effective coin and the position space of the walker, as well as an evolution operator, which is applied to both systems in discrete time-steps. The evolution is given by a unitary operator defined on a tensor product of two Hilbert spaces ({{mathcal{H}}}_{{rm{c}}}otimes {{mathcal{H}}}_{{rm{p}}}) where, ({{mathcal{H}}}_{{rm{c}}}) is the coin Hilbert space spanned by the internal states ({left|0rightrangle }_{{rm{c}}}) and ({left|1rightrangle }_{{rm{c}}}) of a single qubit, while ({{mathcal{H}}}_{p}) represents the position Hilbert space given by the position states (left|xrightrangle) with (xin {mathbb{Z}}) encoded in several qubits as described below. Here, the unitary quantum coin toss operation, ({hat{C}}_{theta }), is a unitary rotation operator that acts on the coin qubit space,

$${hat{C}}_{theta }=left[begin{array}{cc}cos theta &-isin theta \ -isin theta &cos theta end{array}right]otimes {hat{I}}_{{rm{p}}},$$

(1)

where θ is a coin bias parameter that can be varied at each step to modify the QW path superposition weights. The conditional position-shift operator, (hat{S}), translates the particle to the left and right conditioned by the state of the coin qubit,

$$hat{S}={left|0rightrangle }_{{rm{c}},{rm{c}}}langle 0| otimes sum _{xin {mathbb{Z}}}| x-1rangle {langle x| +| 1rangle }_{{rm{c}},{rm{c}}}langle 1| otimes sum _{xin {mathbb{Z}}}| x+1rangle leftlangle xright|.$$

(2)

The state of the particle in position space after t steps of the walk, is accomplished by the repeated action of the operator (hat{W}=hat{S}{hat{C}}_{theta }) on the initial state of the particle ({left|psi rightrangle }_{{rm{c}}}=alpha {left|0rightrangle }_{{rm{c}}}+beta {left|1rightrangle }_{{rm{c}}}) at position x = 0, as shown in Fig. 1,

$$left|Psi (x,t)rightrangle ={hat{W}}^{t}left[{left|psi rightrangle }_{c}otimes left|x=0rightrangle right]=sum _{x}left[begin{array}{c}{psi }_{x,t}^{0}\ {psi }_{x,t}^{1}end{array}right],$$

(3)

where ({psi }_{x,t}^{0(1)}) denotes the left(right) propagating component of the particle at time-step t. The probability of finding the particle at position x and time t will be (P(x,t)=| {psi }_{x,t}^{0}{| }^{2}+| {psi }_{x,t}^{1}{| }^{2}).

Recent works have shown a relationship between DQWs and the Dirac equation14,15,16,17,18,43. Starting form a discrete-time evolution operator and then moving from position space to momentum space, Dirac kinematics can be recovered from the diagonal terms of the unitary evolution operator for small momenta in the small mass regime16,17,18. In contrast with these proposals in the Fourier frame, we focus our implementation on the probability distribution of the DQW, which is analogous to the spreading of a relativistic particle. To realize a DCA and recover the Dirac equation, a split-step quantum walk, one form of the DQW, is used40. Each step of a split-step quantum walk is a composition of two half step evolutions with different coin biases and position-shift operators,

$${hat{W}}_{{rm{ss}}}={hat{S}}_{+}{hat{C}}_{{theta }_{2}}{hat{S}}_{-}{hat{C}}_{{theta }_{1}},$$

(4)

where the coin operation ({hat{C}}_{{theta }_{j}}), with j = 1, 2, is given in Eq. (1). The split-step position-shift operators are,

$${hat{S}}_{-}={left|0rightrangle }_{{rm{c}},{rm{c}}}langle 0| otimes sum _{xin {mathbb{Z}}}| x-1rangle {langle x| +| 1rangle }_{{rm{c}},{rm{c}}}langle 1| otimes sum_{xin {mathbb{Z}}}| xrangle leftlangle xright|,$$

(5)

$${hat{S}}_{+}={left|0rightrangle }_{{rm{c}},{rm{c}}}langle 0| otimes sum_{xin {mathbb{Z}}}| xrangle {langle x| +| 1rangle }_{{rm{c}},{rm{c}}}langle 1| otimes sum_{xin {mathbb{Z}}}| x+1rangle leftlangle xright|.$$

(6)

Following Mallick40 and Kumar44, the particle state at time t and position x after the evolution operation ({hat{W}}_{{rm{ss}}}) is described by the differential equation,

$$frac{partial }{partial t}left[begin{array}{c}{psi }_{x,t}^{0}\ {psi }_{x,t}^{1}end{array}right]= cos {theta }_{2}left[begin{array}{cc}cos {theta }_{1} & -isin {theta }_{1}\ isin {theta }_{1} & -cos {theta }_{1}end{array}right]left[begin{array}{c}frac{partial {psi }_{x,t}^{0}}{partial x}\ frac{partial {psi }_{x,t}^{1}}{partial x}end{array}right]\ +left[begin{array}{cc}cos ({theta }_{1}+{theta }_{2})-1 & -isin ({theta }_{1}+{theta }_{2})\ -isin ({theta }_{1}+{theta }_{2}) & cos ({theta }_{1}+{theta }_{2})-1end{array}right]left[begin{array}{c}{psi }_{x,t}^{0}\ {psi }_{x,t}^{1}end{array}right].$$

(7)

The tunability of parameters θ1 and θ2 on the split-step QW permits the study of one-dimensional Dirac equations effectively, within the low momentum subspace, for spin-1/2 particles40,44. It is important to stress out that, the description of the Dirac equation used here corresponds to the 2 × 2 representation, i.e. no spin degree of freedom. For instance, the massless particle Dirac equation can be recovered for (cos ({theta }_{1}+{theta }_{2})=1). Thereby, Eq. (7) becomes (ihslash [{partial }_{t}-cos {theta }_{2}(cos {theta }_{1}{sigma }_{z}+sin {theta }_{1}{sigma }_{y}){partial }_{x}]Psi (x,t)=0), which is identical to the Dirac equation of a massless particle in the relativistic limit46. In contrast, considering θ1 = 0 and a very small value of θ2 corresponds to the Dirac equation for particles with small mass35,46 in the form (ihslash [{partial }_{t}-(1-{theta }_{2}^{2}/2){sigma }_{z}{partial }_{x}+i{theta }_{2}{sigma }_{x}]Psi (x,t)approx 0).

At the same time, by choosing θ1 = 0, the quantum walk operator ({hat{W}}_{{rm{ss}}}) given in Eq. (4) takes the form of the unitary operator for a DCA40,

$${hat{W}}_{{rm{ss}}}=left[begin{array}{cc}cos ({theta }_{2}){S}_{-}&-isin ({theta }_{2}){mathbb{1}}\ -isin ({theta }_{2}){mathbb{1}}&cos ({theta }_{2}){S}_{+}end{array}right]={U}_{{rm{DCA}}}.$$

(8)

Within this framework, θ2 determines the mass of the Dirac particle. The split-step DQW described by the operator ({hat{W}}_{{rm{ss}}}) is equivalent to the two period DQW with alternate coin operations, θ1 and θ2, when the alternate points in position space with zero probability are ignored47. Therefore, all the dynamics of a DCA can be recovered from the DQW evolution using (hat{W}) and alternating the two coin operations. See Methods for a comparison between DCA and the explicit solution of the Dirac equation. Typical features of the Dirac equation in relativistic quantum mechanics, such as the Zitterbewegung40 and the Klein paradox48, are also dynamical features of the DCA, as well as the spreading of the probability distribution and the entanglement of localized positive-energy states. We note that these effects have also been shown in direct analog simulations of the Dirac equation with trapped ions35 and BECs49.

### Experimental DQW implementation

To realize the DQW on a system of qubits one must pick a mapping of the particle position to the qubit space. As shown in50, there is no unique way to map position states to multi-qubit states, so each circuit decomposition depends on the configuration adopted. A direct mapping of each walker position to one qubit in the chain mimicking the arrangement of the qubit array is inefficient in terms of qubit number and gates required (the former grows linearly and the latter quadratically with the position space size modeled). In order to minimize resource use, we take advantage of a digital representation to map the position space into a multi-qubit state and re-order it in such a way that the state (left|0rightrangle ,(left|1rightrangle )) of the last qubit corresponds to even (odd) position numbers. This allows us to minimize the changes needed in the qubit space configuration during each step of the walk (see Fig. 2). To implement a quantum walk in one-dimensional position Hilbert space of size 2n, (n + 1) qubits are required. One qubit acts as the coin and the other n qubits mimic the position Hilbert space with 2n − 1 positions of a symmetric walk about (left|x=0rightrangle). We note that the particle can be started from any point in the position space, however setting the initial state reduces the gate counting in the circuit and hence reduces the overall error. The coin operation is achieved by single-qubit rotations on the coin-qubit while the shift operators are realized by using the coin as a control qubit to change the position state during the walk.

We realize the walk on a chain of seven individual 171Yb+ ions confined in a Paul trap and laser-cooled close to their motional ground state45,51. Five of these are used to encode qubits in their hyperfine-split 2S1/2 ground level. Single-qubit rotations, or R gates, and two-qubit entangling interactions, or XX gates are achieved by applying two counter-propagating optical Raman beams to the chain, one of which features individual addressing (see Methods for experimental details). We can represent up to 15 positions of a symmetric QW, including the initial position (left|x=0rightrangle).

Based on this position representation a circuit diagram for the DQW on five qubits with the initial state ({left|0rightrangle }_{c}otimes left|0000rightrangle) is composed for up to five steps, see Fig. 3. Each evolution step, (hat{W}), starts with a rotation operation on the coin-qubit, ({hat{C}}_{{theta }_{j}}), followed by a set of controlled gates that change the position state of the particle under (hat{S}). Due to the gratuitous choice of position representation used, it is enough to perform a single-qubit rotation on the last qubit at every step, which could also be done by classical tracking50.

Computational gates such as CNOT, Toffoli, and Toffoli-4 are generated by a compiler which breaks them down into constituent physical-level single- and two-qubit gates45. A circuit diagram detailing the compiled building blocks is shown in Methods. To prepare an initial particle state different from ({left|0rightrangle }_{{rm{c}}}) it is enough to perform a rotation on the coin-qubit before the first step. In some cases this rotation can be absorbed into the first gates in step one. Table 1 summarizes the number of native gates needed per step for initial state. To recover the evolution of the Dirac equation in a DQW after five steps, 81 single qubit gates and 32 XX-gates are required.

After evolving a number of steps, we sample the corresponding probability distribution 3000 times and correct the results for readout errors. For the DQW evolution up to five steps shown in Fig. 3, a balanced coin (θ1 = θ2 = π/4) is used where the initial position is (left|x=0rightrangle) for different initial particle states, ({left|0rightrangle }_{{rm{c}}}) in Fig. 3b i, ({left|1rightrangle }_{{rm{c}}}) in Fig. 3b ii, and an equal superposition of both in Fig. 3b iii. In Fig. 3b iv, b v, and b vi we show the ideal output from classical simulation of the circuit for comparison (see Methods for a plot of the difference). With a balanced coin the particle evolves in equal superposition to the left and right position at each time step and upon measurement, there is a 50/50 probability of finding the particle to the left or right of its previous position, just as in classical walk. If we let the DQW evolve for more than three steps before we perform a position measurement, we will find a very different probability distribution compared to the classical random walk52.

The same experimental setup can be used to recover a DCA with a two-period DQW. Here we set θ1 = 0 and varied θ2 to recover the Dirac equation for different mass values. In Fig. 3c, we show experimental results for θ2 = π/4, π/10 and π/20, corresponding to a mass 1.1357, 0.3305, and 0.159 in units of c−2s−1, with the initial particle state in the superposition ({left|0rightrangle }_{c}+i{left|1rightrangle }_{c}). The main signature of a DCA for small mass values is the presence of peaks moving outward and a flat distribution in the middle as shown for the cases with small values of θ2, Figs. 3c ii-iii. This bimodal probability distribution in position space is an indication of the one-dimensional analog of an initially localized Dirac particle, with positive energy, evolving in time which spreads in all directions in position space at speeds close to the speed of light53. In contrast, a DCA with θ2 = π/4, Fig. 3c i corresponds to a massive particle and hence there is a slow spread rather than a ballistic trajectory in position space.