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

HAL
open science

# Quantum control using quantum memory

Mathieu Roget, Basile Herzog, Di Molfetta Giuseppe

► To cite this version:

Mathieu Roget, Basile Herzog, Di Molfetta Giuseppe. Quantum control using quantum memory. Scientific Reports, 2020, 10 (1), pp.21354. 10.1038/s41598-020-78455-3. hal-03594724

HAL Id: hal-03594724

https://amu.hal.science/hal-03594724v1

Submitted on 5 Jul 2024

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_3.png" /></figure>

# Quantum control using quantum memory

Mathieu Roget<fnref n="1" />,³,⁵, Basile Herzog<fnref n="1" />,²,⁵ & Giuseppe Di Molfetta<fnref n="1" />,⁴,⁵✉

We propose a new quantum numerical scheme to control the dynamics of a quantum walker in a two dimensional space-time grid. More specifically, we show how, introducing a quantum memory for each of the spatial grid, this result can be achieved simply by acting on the initial state of the whole system, and therefore can be exactly controlled once for all. As example we prove analytically how to encode in the initial state any arbitrary walker's mean trajectory and variance. This brings significantly closer the possibility of implementing dynamically interesting physics models on medium term quantum devices, and introduces a new direction in simulating aspects of quantum field theories (QFTs), notably on curved manifold.

Quantum control refers to the ability to steer a dynamical quantum system from an initial to a desired target or outcome, with a desired accuracy<fnref n="1" />. Several theoretical and experimental approaches to model controlled wave packets and their application are very useful to pave the way for future simulation or quantum calculation schemes²,³. In many of these, the physical system to be controlled is driven by an external potential, which needs to be controlled all along the experience, until the target is achieved. Although in this work we do not claim to offer a general theory of quantum control, we provide a new approach in which the control scheme is encoded once and for all into its initial state. The main protagonist here is not a generic quantum system, but a quantum walks (QW) in discrete time⁴⁻⁶. What may seem like a particular choice, in reality offers great potential, given the recognised versatility of this simple system. In fact, QW are a universal computational model⁷,⁸, that spans a large spectrum of physical and biological phenomena, relevant both for fundamental science and for applications. Applications include search algorithms⁹⁻¹² and graph isomorphism algorithms¹³ to modeling and simulating quantum¹⁴⁻¹⁸ and classical dynamics¹⁹,²⁰. These models have sparked various theoretical investigations covering areas in mathematics, computer science, quantum information and statistical mechanics and have been defined in any physical dimensions²¹,²² and over several topologies²³⁻²⁵. QW appear in multiple variants and can be defined on arbitrary graphs. Essentially, these simple systems have two registers: one for its position on the graph and the other is its internal state, often called coin state. It propagates on the graph, conditioned by its internal state, similarly to the classical case, where at each step we flip a coin to determine the direction of the walker. The essential difference is that in the quantum case, the walker propagates in superposition on the graph in various directions starting from a node. This feature allows the quantum walker to explore the graph quadratically faster a classical one, property that make it very useful to design, e.g., efficient search algorithms. However, we do not know many way to control the quantum walker evolution. For instance we can choose the initial condition and the evolution operator to tune the walker's variance $\sigma(t) = af(t)$, where *a* is a real prefactor and $f(t)$ is typically a linear function of *t*. However, once these are fixed at the initial time, both *f* and *a* remain the same all along the evolution, unless we do not allow the evolution operator to change in an in-homogeneous way at each time-step, as in²⁶,²⁷, which may be very costly. How can we control the walker's dynamics at our will without having to change the evolution operator? Would it be possible to control, having only the initial condition, the variance or its average trajectory? In this manuscript we argue that, at the price of introducing a quantum memory, the answer is affirmative. Quantum walks with memory have already been studied and come in several variants²⁸,²⁹. As an example, these modified quantum walks may have extra coins to record the walker's latest path, as in³⁰,³¹. Here, the idea is to define an additional qubit for each site in the grid, with which the walker interacts throughout the evolution. Surprisingly, we will prove that the initial condition of the whole system, memory + walker, is sufficient to control, e.g., the variance and the mean position of the walker for all times. The interest is double: from one hand we provide a simple distributed quantum computational model to control a single qubit along its dynamics, which will not require us to control and adjust the local update rule at

<footnote n="1">¹Aix-Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France. ²Université de Lorraine, LPCT, Nancy, France. ³Département d'Informatique, ENS de Lyon, Lyon, France. ⁴Quantum Computing Center, Keio University, Tokyo, Japan. ⁵These authors contributed equally: Mathieu Roget, Basile Herzog and Giuseppe Di Molfetta. ✉email: giuseppe.dimolfetta@lis-lab.fr</footnote>
each time step; from a totally different perspective, this simple system may suggest an operational way to model and to unitary discretise curved propagation, as argued in³².

The manuscript is organised as follows: in “The model” we will provide the definition of the model with and without memory, in one spatial dimension; then, in “Control the walker’s dynamics”, we will prove analytically and numerically how to control the variance and the mean trajectory of a quantum walker, solely via the initial condition of the whole system. Finally, in “Discussion” we discuss and conclude.

## The model

Formally, the simplest but non trivial QW is defined on a Hilbert space which has position and velocity (inter- nal “spin” state) components. The position Hilbert space X is the set of states $|x\rangle$ where $x \in \mathbb{Z}_N$, and the velocity Hilbert space is $V = \mathbb{C}^2$, for which we may choose some orthonormal basis labeled $\{|v^-\rangle, |v^+\rangle\}$. Denote the QW Hilbert space by $\mathcal{H}$,

$$ \mathcal{H} = X \otimes V. $$

The overall state of the walker at time $t \in \mathbb{N}$ may thus be written

$$ \Psi(t) = \sum_x \psi_x^+(t) |x\rangle \otimes |v^+\rangle + \psi_x^-(t) |x\rangle \otimes |v^-\rangle, $$

where the scalar field $\psi_x^+$ (resp. $\psi_x^-$) gives, at every position $x \in \mathbb{Z}_N$, the amplitude of the particle being there and about to move right (resp. left). We can write an amplitude vector at time $t$ and position $x$ over the ordered basis of the coin space $\{|v^+\rangle, |v^-\rangle\}$,

$$ \Psi_x(t) = \begin{pmatrix} \psi_x^+(t) \\ \psi_x^-(t) \end{pmatrix}. $$

Let W be the evolution of the QW at each time step,

$$ \Psi_x(t+1) = W \Psi_x(t). $$

W is composed of a coin operator C, an arbitrary element of $U(2)$, acting on the velocity space, e.g.,

$$ C = \begin{pmatrix} \cos \theta & i \sin \theta \\ i \sin \theta & \cos \theta \end{pmatrix}, $$

followed by a shift operator S

$$ S\Psi_x(t) = \begin{pmatrix} \psi_{x-1}^+(t) \\ \psi_{x+1}^-(t) \end{pmatrix}, \qquad (1) $$

with the overall evolution being

$$ W = S(\mathrm{Id}_X \otimes C), $$

where $\mathrm{Id}_X$ is the identity operator on the position Hilbert space.

**Quantum memory.** Now, let us consider that at each site $x$ of the grid we have a supplementary qubit $|m_x\rangle \in \mathcal{M}^x = \mathbb{C}^2$. This extended Hilbert space, as proved in⁶,³³, may be used as a quantum memory to keep track of the past of the walker. Notice that the size of the Hilbert space now seems to be growing exponentially. However, according to³⁴ this is not going to be an issue for infinite lattices as the Hilbert space can be taken to be countably infinite dimensional, even with the memory qubits included. That is because the interactions are only finite neighborhood and a Hilbert space of finite, unbounded configurations suffices³⁵.

The whole state (QW + quantum memory) lies now in $X \otimes V \otimes_{x=1}^N \mathcal{M}^x$. Indeed, one of the main motivation of this history dependent QW is to build a truly self-avoiding walker: one knows that the walker moves towards the left or towards the right according to the internal coin state; thus, in order to avoid sites already visited by the walker, one conditions the coin state on the neighbor memory states, which eventually recorded previous presence of the walker.

The coin operator $\mathcal{C}$ of the previous section is replaced by a different operator Q, that acts on the joint velocity- memory space: $V \otimes \mathcal{H}_{\mathcal{M}^x} \otimes \mathcal{H}_{\mathcal{M}^{x+1}}$—whose basis is the set of $|v^\alpha \beta_1 \delta_r\rangle$, $\alpha = \{+, -\}$, $|\beta_1\rangle$ and $|\delta_r\rangle$ being the memory qubits located respectively at the positions $(x-1)$ and $(x+1)$ - so that the memory qubits adjacent to the position $x$ of the walker are involved:

$$ Q = |v^+ 11\rangle\langle v^+ 00| + |v^- 00\rangle\langle v^- 00| + |v^- 01\rangle\langle v^+ 01| + |v^+ 01\rangle\langle v^- 10| \\ + |v^+ 10\rangle\langle v^+ 10| + |v^- 10\rangle\langle v^- 01| + |v^+ 00\rangle\langle v^+ 11| + |v^- 11\rangle\langle v^- 11| $$

Finally, the shift operator still acts on the joint velocity-position space in the standard manner, as defined in Eq. (1), and trivially on the memory space. Altogether the global evolution, depicted in Fig. 1, is:
<figure><img src="image_4.png" /><figcaption>Figure 1. Schematic evolution of the walker $\Psi_x(0)$ at the initial time conditioned by the neighbors qubits at position $x = -1$ and $x = 1$.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 2. The initial state of the quantum memory on the one dimensional line.</figcaption></figure>

$$ \begin{aligned} \Psi(t+1) &= G\Psi(t) \\ G &= SQ. \end{aligned} $$

## Control the walker's dynamics

To simplify our analysis, we choose a localized set of initial conditions

$$ \Psi(0) = |0\rangle|v^{-}\rangle \left( \bigotimes_{x=-\lfloor \frac{N}{2} \rfloor}^{1} A_{-x}|0\rangle + B_{-x}|1\rangle \right) \left( \bigotimes_{x=0}^{\lfloor \frac{N}{2} \rfloor} |0\rangle \right) \quad (2) $$

which is equivalent to requiring that all those sites with a nonzero internal state have all quantum memories to their right set to $|0\rangle$, as depicted in Fig. 2.

By looking at the single walker subspace, the recurrence relations for each amplitude, detailed in the “Appendix”, read:

$$ \begin{aligned} \psi_x^{-}(t+1) &= A_{-x}\psi_{x+1}^{-}(t) \\ \psi_x^{+}(t+1) &= \psi_{x-1}^{+}(t) + B_{-x+2}\psi_{x-1}^{-}(t) \end{aligned} \quad (3) $$

and given Eq. (2) we prove the following theorem.

**Theorem 1** The left-moving and right-moving amplitudes $\psi_x^{\mp}(t)$, solutions of the linear set of Eqs. (3), reads:

$$ \psi_x^{-}(t) = \begin{cases} \prod_{i=1}^{t} A_i & \text{if } x = -t \\ 0 & \text{else} \end{cases} $$

and

$$ \psi_x^{+}(t) = \begin{cases} 0 & \text{if } |x| > t \\ 0 & \text{if } x = -t \\ 0 & \text{if } x - t \text{ is odd} \\ B_{\frac{t-x}{2}+1} \prod_{j=1}^{\frac{t-x}{2}} A_j & \text{else} \end{cases} $$

**Proof** We can prove the above theorem by induction. Indeed, let us first compute $\psi_x^{-}(t+1)$, we may discern two cases:

* $x \neq -(t+1)$: then $x+1 \neq -t$ and
$$ \psi_{x+1}^{-}(t) = 0 \Rightarrow \psi_{x}^{-}(t+1) = 0 $$

* $x = -(t+1)$; then $x+1 = -t$ and

$$ \psi_x^{-}(t+1) = A_{-x} \psi_{x+1}^{-}(t) = A_{t+1} \prod_{i=1}^{t} A_i = \prod_{i=1}^{t+1} A_i. $$

In order to compute $\psi_x^+(t+1)$, we discern four cases:

* $|x| > t+1$: the celerity of the walk being of one space-step per time-step, and the initial condition being localized, then $\psi_x^+(t+1) = 0$

* $x = -(t+1)$: using the same argument, $\psi_{x-1}^{\pm}(t+1) = 0$ and $\psi_x^+(t+1) = 0$

* $x - (t+1)$ is odd: then $(x-1) - t$ is odd and $x-1 \neq -t$,

$$ \psi_{x-1}^{+}(t) = 0 \text{ and } \psi_{x-1}^{-}(t) = 0 \Rightarrow \psi_{x}^{+}(t+1) = 0 $$

* else (in particular, $x-t-1$ is even): there are two subcases:

- $x-1 = -t$: then $\psi_{x-1}^+(t) = 0$ and

$$ \psi_x^+(t+1) = B_{-x+2} \prod_{i=1}^{t} A_i = B_{\frac{t+1-x}{2}+1} \prod_{j=1}^{\frac{t+1-x}{2}} A_j $$

- $x-1 \neq -t$: then $\psi_{x-1}^-(t) = 0$ and

$$ \psi_x^+(t+1) = B_{\frac{t+1-x}{2}+1} \prod_{j=1}^{\frac{t+1-x}{2}} A_j $$

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

Using Theorem 1, it is straightforward to compute the probability density of the walker, which reads:

$$ \mathbb{P}_x(t) = \begin{cases} \prod_{i=1}^{t} A_i^2 & \text{if } x = -t \\ 0 & \text{if } x - t \text{ is odd} \\ B_{\frac{t-x}{2}+1}^2 \prod_{j=1}^{\frac{t-x}{2}} A_j^2 & \text{else} \end{cases} $$

where, the above probability density is vanishing for $|x| > t$.

Once we know the analytical expression of the probability density, one can compute the mean trajectory and variance. The first one reads:

$$ \mathbb{E}(t) = -t \prod_{i=1}^{t} A_i^2 + \sum_{k=0}^{t-1} (t-2k) B_{k+1}^2 \prod_{j=1}^{k} A_j^2, $$

and the variance:

$$ \mathrm{Var}(t) = t^2 \prod_{i=1}^{t} A_i^2 - \left( t \prod_{i=1}^{t} A_i^2 - \sum_{i=0}^{t-1} (2i-t) B_{i+1}^2 \prod_{j=1}^{i} A_j^2 \right)^2 + \sum_{i=0}^{t-1} (2i-t)^2 B_{i+1}^2 \prod_{j=1}^{i} A_j^2. $$

Notice that the probability density and both the first two momenta, depend solely on the parameters {$A_x, B_x$} which we fix at the initial state. Let us now explore few examples to show how we can recover any arbitrary mean trajectory and variance by controlling the sole initial condition of the system. Suppose we need to recover a linear mean trajectory. The way to do that is setting $A_k = 1$ and $B_k = 0 \forall k > 1$, supposed that $A_1$ and $B_1$ are known. Without lack of generality we set $A_1^2 = (1 - B_1^2)$.

Then the probability density is:

$$ \mathbb{P}_x(t) = \begin{cases} (1 - B_1^2)^2 & \text{if } x = -t \\ B_1^2 & \text{if } x = t \\ 0 & \text{else} \end{cases} $$

In this particular case, the general expression of the mean value of the trajectory reduces to:

$$ \mathbb{E}(t) = -t(1 - 2B_1^2) $$
<figure><img src="image_7.png" /><figcaption>Figure 3. Mean trajectory of the walker for different values of v. Points represents the theoretical prediction, the dashed line coincides with the numerical simulation.</figcaption></figure>

The pre-factor $2B_1^2 - 1 \equiv v$, may be seen as the mean velocity of the walker. As we can see in Fig. 3 the smaller is v, the smaller will be the velocity of the mean trajectory. The variance Var(t) will be of course $\propto t^2$, which coincide with the standard ballistic behaviour of an homogeneous QW.

A second less trivial example may be represented by the parabolic mean trajectory, which translates in a non-linear variance. For example, let's set $B_k = \sqrt{-\frac{z}{z(k-1)-2}}$, $z \in \mathbb{R}^+$.

Now the probability reads:

$$ \mathbb{P}_x(t) = \begin{cases} 1 - \frac{tz}{z+2} & \text{if } x = -t \\ 0 & \text{if } x - t \text{ is odd} \\ \frac{z}{z+2} & \text{else} \end{cases} $$

and we can consequently deduce the mean trajectory

$$ \mathbb{E}(t) = \frac{t(zt - 2)}{z + 2} $$

and the standard deviation $\sigma = \sqrt{\mathrm{Var}(t)}$:

$$ \sigma(t) = \sqrt{\frac{t(-3t(zt - 2)^2 + (z + 2)(-2t^2z + 3tz + 6t + 2z))}{3(z + 2)^2}} $$

Notice that the above standard deviation is not linear in time, as shown in Fig. 4 and the non-linear behaviour of $\sigma$ strongly depends on $z$.

In all previous particular cases, we have shown how to recover linear and non linear moments, keeping the probability density $\mathbb{P}_x(t)$ either constant either linear in $t$. In our last result, we show how it is possible to generalize these results, making the walker's probability density follow arbitrary trajectories. This result is surprising as, although similar results have been obtained before, they required to define a local metrics for each point of the space-time lattice. More specifically, we want to show how, by paying the price of introducing quantum memory, this result can be achieved simply by acting on the initial state and therefore can be exactly controlled once for all. This translates in the following theorem.

**Theorem 2** Let us choose

$$ B_k^2 = \frac{f_{k-1}}{1 - \sum_{i=1}^{k-2} f_i} $$

then the probability density reads:
<figure><img src="image_8.png" /><figcaption>Figure 4. Mean trajectory of the walker for different values of z. (Bottom) Variance of the walker for different values of z. Points represents the theoretical prediction, the dashed line coincides with the numerical simulation.</figcaption></figure>

$$ \mathbb{P}_x(t) = \begin{cases} 1 - \sum_{i=0}^{t-1} f_i & \text{if } x = -t \\ 0 & \text{if } x - t \text{ is odd or } |x| > t \\ f_{\frac{t-x}{2}} & \text{else} \end{cases} $$

for some arbitrary function $f_i$ which verifies

* $\forall t, \sum_{i=0}^{t-1} f_i \le 1$

* $\forall t, 0 \le f_t \le 1$.

**Proof** We take

$$ \begin{cases} B_k^2 = \frac{f_{k-1}}{1 - \sum_{i=0}^{k-2} f_i} \\ A_k^2 = 1 - \frac{f_{k-1}}{1 - \sum_{i=0}^{k-2} f_i} \end{cases} $$

Now, we want to prove that

$$ \begin{cases} \prod_{i=1}^{t} A_i^2 = 1 - \sum_{i=0}^{t-1} f_i \\ B_{\frac{t-x}{2}+1}^2 \prod_{j=1}^{\frac{t-x}{2}} A_j^2 = f_{\frac{t-x}{2}} \end{cases} $$

First let us prove by induction that

$$ \prod_{i=1}^{t} A_i^2 = 1 - \sum_{i=0}^{t-1} f_i. $$

* For $t = 0$:

$$ \prod_{i=1}^{0} A_i^2 = 1 - \sum_{i=0}^{-1} f_i = 1. $$

* If it's true for $t$, then
$$ 
\begin{aligned}
\prod_{i=1}^{t+1} A_i^2 &= A_{t+1}^2 \prod_{i=1}^{t} A_i^2 = \left(1 - \frac{f_t}{1 - \sum_{i=0}^{t-1} f_i}\right) \prod_{i=1}^{t} A_i^2 \\
&= \left(1 - \frac{f_t}{1 - \sum_{i=0}^{t-1} f_i}\right) \left(1 - \sum_{i=0}^{t-1} f_i\right) = 1 - \sum_{i=0}^{t-1} f_i - f_t = 1 - \sum_{i=0}^{t} f_i
\end{aligned}
$$

So it is true for $t + 1$.

Now let us prove that

$$ B_{\frac{t-x}{2}+1}^2 \prod_{j=1}^{\frac{t-x}{2}} A_j^2 = f_{\frac{t-x}{2}} $$

$$ B_{\frac{t-x}{2}+1}^2 \prod_{j=1}^{\frac{t-x}{2}} A_j^2 = B_{\frac{t-x}{2}+1}^2 \left(1 - \sum_{i=0}^{\frac{t-x}{2}-1} f_i\right) = \left(\frac{f_{\frac{t-x}{2}}}{1 - \sum_{i=0}^{\frac{t-x}{2}-1} f_i}\right) \left(1 - \sum_{i=0}^{\frac{t-x}{2}-1} f_i\right) = f_{\frac{t-x}{2}} $$

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

## Discussion

In conclusion, we introduced a quantum walker which interacts with a memory at each site, allowing the walker's dynamics to depend on the state of the memory qubits in the particle's neighborhood. We considered a scheme that parametrizes the initial states of the memory qubits, and we analytically obtain the probability density of the walker's position, and consequently, its mean trajectory and variance. Varying these parameters alone suffices to generate a range of trajectories that may simulate motion on curved manifolds. This pave the way to implement dynamically interesting physics models, especially quantum particle propagation on curved spacetime. Indeed, embedding the mean trajectory, once for all, in the initial state of the overall QCA, is a clear computational advantage, which may reduce the resources needed for the simulation of a wide variety of dynamical physical models. Possible extensions of these results may also concern quantum algorithms. For example, such a model could inspire efficient spatial search algorithms, as an extension of single quantum walk based schemes. We also leave to future research the extension of the model in higher dimensional space than one.

Received: 22 September 2020; Accepted: 25 November 2020

Published online: 07 December 2020

## References

1. Glaser, S. J. et al. Training schrödinger's cat: Quantum optimal control. Eur. Phys. J. D 69, 1–24 (2015).

2. Dong, D. & Petersen, I. R. Quantum control theory and applications: A survey. IET Control Theory Appl. 4, 2651–2671 (2010).

3. Georgescu, I. M., Ashhab, S. & Nori, F. Quantum simulation. Rev. Modern Phys. 86, 153 (2014).

4. Aharonov, Y., Davidovich, L. & Zagury, N. Quantum random walks. Phys. Rev. A 48, 1687 (1993).

5. Grossing, G. & Zeilinger, A. Quantum cellular automata. Complex Syst. 2, 11 (1988).

6. Shakeel, A., Meyer, D. A. & Love, P. J. History dependent quantum random walks as quantum lattice gas automata. J. Math. Phys. 55, 122204 (2014).

7. Childs, A. M. Universal computation by quantum walk. Phys. Rev. Lett. 102, 180501 (2009).

8. Lovett, N. B., Cooper, S., Everitt, M., Trevers, M. & Kendon, V. Universal quantum computation using the discrete-time quantum walk. Phys. Rev. A 81, 042330 (2010).

9. Grover, L. K. A fast quantum mechanical algorithm for database search. in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. STOC '96, 212–219. https://doi.org/10.1145/237814.237866 (ACM, New York, NY, USA, 1996).

10. Ambainis, A. Quantum search algorithms. SIGACT News 35, 22–35. https://doi.org/10.1145/992287.992296 (2004).

11. Portugal, R. Quantum Walks and Search Algorithms (Springer Publishing Company, Incorporated, New York, 2013).

12. Roget, M., Guillet, S., Arrighi, P. & Di Molfetta, G. Grover search as a naturally occurring phenomenon. Phys. Rev. Lett. 124, 180501 (2020).

13. Berry, S. D. & Wang, J. B. Two-particle quantum walks: Entanglement and graph isomorphism testing. Phys. Rev. A 83, 042317 (2011).

14. Arrighi, P., Di Molfetta, G. & Facchini, S. Quantum walking in curved spacetime: Discrete metric. Quantum 2, 84 (2018).

15. Arrighi, P., Di Molfetta, G., Márquez-Martín, I. & Pérez, A. From curved spacetime to spacetime-dependent local unitaries over the honeycomb and triangular quantum walks. Sci. Rep. 9, 1–10 (2019).

16. Hatifi, M., Di Molfetta, G., Debbasch, F. & Brachet, M. Quantum walk hydrodynamics. Sci. Rep. 9, 1–7 (2019).

17. Arrighi, P., Bény, C. & Farrelly, T. A quantum cellular automaton for one-dimensional qed. Quant. Inf. Process. 19, 88 (2020).

18. Di Molfetta, G. & Pérez, A. Quantum walks as simulators of neutrino oscillations in a vacuum and matter. N. J. Phys. 18, 103038 (2016).

19. Di Molfetta, G. & Debbasch, F. Discrete-time quantum walks in random artificial gauge fields. Quant. Stud. Math. Foundations 3, 293–311 (2016).

20. Brun, T. A., Carteret, H. A. & Ambainis, A. Quantum to classical transition for random walks. Phys. Rev. Lett. 91, 130602 (2003).

21. Mackay, T. D., Bartlett, S. D., Stephenson, L. T. & Sanders, B. C. Quantum walks in higher dimensions. J. Phys. A Math. General 35, 2745 (2002).

22. Márquez-Martín, I., Di Molfetta, G. & Pérez, A. Fermion confinement via quantum walks in (2+1)-dimensional and (3+1)-dimensional space-time. Phys. Rev. A 95, 042112 (2017).

23. Acevedo, O. L. & Gobron, T. Quantum walks on Cayley graphs. J. Phys. A Math. General 39, 585 (2005).

24. Rohde, P. P., Schreiber, A., Štefaňák, M., Jex, I. & Silberhorn, C. Multi-walker discrete time quantum walks on arbitrary graphs, their properties and their photonic implementation. N. J. Phys. 13, 013001 (2011).
25. Aristote, Q., Eon, N. & Di Molfetta, G. Dynamical triangulation induced by quantum walk. *Symmetry* **12**, 128 (2020).

26. Di Molfetta, G., Brachet, M. & Debbasch, F. Quantum walks in artificial electric and gravitational fields. *Physica A Stat. Mech. Appl.* **397**, 157–168 (2014).

27. Di Molfetta, G., Brachet, M. & Debbasch, F. Quantum walks as massless dirac fermions in curved space. *Phys. Rev. A* **88**, 042301 (2013).

28. Konno, N. & Machida, T. Limit theorems for quantum walks with memory. *Quant. Inf. Comput.* **10**, 1004–1017 (2010).

29. Li, D., Gettrick, M. M., Gao, F., Xu, J. & Wen, Q.-Y. Generic quantum walks with memory on regular graphs. *Phys. Rev. A* **93**, 042323 (2016).

30. McGettrick, M. One dimensional quantum walks with memory. *Quant. Inf. Comput.* **10**, 509–524 (2010).

31. Rohde, P. P., Brennen, G. K. & Gilchrist, A. Quantum walks with memory provided by recycled coins and a memory of the coin-flip history. *Phys. Rev. A* **87**, 052302 (2013).

32. Arrighi, P., Di Molfetta, G. & Facchini, S. Quantum walking in curved spacetime: Discrete metric. *arXiv preprint*. arXiv:1711.04662 (2017).

33. Shakeel, A. Neighborhood-history quantum walk. *Physica Scripta* **94**, 065207. https://doi.org/10.1088/1402-4896/ab0254 (2019).

34. Shakeel, A. Quantum cellular automata: Schrödinger and heisenberg pictures. *arXiv preprint*. arXiv:1807.01192 (2018).

35. Arrighi, P., Nesme, V. & Werner, R. Unitarity plus causality implies localizability. *J. Comput. Syst. Sci.* **77**, 372–378 (2011).

## Acknowledgements

The authors acknowledge inspiring conversations with Asif Shakeel, David Meyer, Pablo Arrighi and Nathanael Eon. This work has been funded by the Pépinière d'Excellence 2018, AMIDEX fondation, project DiTiQuS and the ID 60609 grant from the John Templeton Foundation, as part of the “The Quantum Information Structure of Spacetime (QISS)” Project.

## Author contributions

G.D.M. conceives the model and supervises. M.R. proved the main theorems. M.R. and B.H. wrote the main manuscript, M.R. wrote the code, prepared all figures. All authors reviewed the manuscript.

## Competing interests

The authors declare no competing interests.

## Additional information

**Supplementary Information** The online version contains supplementary material available at https://doi.org/10.1038/s41598-020-78455-3.

**Correspondence** and requests for materials should be addressed to G.D.M.

**Reprints and permissions information** is available at www.nature.com/reprints.

**Publisher's note** Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

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

**Open Access** This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

© The Author(s) 2020