Abstract
We present a $2\mathrm{dimensional}$ quantum walker on curved discretesurfaces with dynamical geometry. This walker extends the quantum walker overthe fixed triangular lattice introduced in [PRA, 97(6):062111, 2018]. We writethe discrete equations of the walker on an arbitrary triangulation, whose flatspacetime limit recovers the Dirac equation in (2+1)dimension. The geometry ischanged through Pachner moves, allowing the surface to transform into anytopologically equivalent surface, starting from a flat space. We present thefirst theoretical model which couple in a nonlinear fashion the dynamics ofthe walker and the dynamical lattice. Numerical simulations show that both thenumber of wells and the local curvature grows as $t^a e^{b t^2}$ and that inlong time flatness emerge, in agreement with theory. We also prove that theglobal behaviour is invariant under random fluctuations of the discretemetrics.
Quick Read (beta)
Quantum Walk over a triangular lattice subject to Pachner moves
Abstract
We present a $2\mathrm{dimensional}$ quantum walker on curved discrete surfaces with dynamical geometry. This walker extends the quantum walker over the fixed triangular lattice introduced in [5]. We write the discrete equations of the walker on an arbitrary triangulation, whose flat spacetime limit recovers the Dirac equation in (2+1)dimension. The geometry is changed through Pachner moves, allowing the surface to transform into any topologically equivalent surface, starting from a flat space. We present the first theoretical model which couple in a nonlinear fashion the dynamics of the walker and the dynamical lattice. Numerical simulations show that both the number of wells and the local curvature grows as ${t}^{a}{e}^{b{t}^{2}}$ and that in long time flatness emerge, in agreement with theory. We also prove that the global behaviour is invariant under random fluctuations of the discrete metrics.
Keywords. Discrete time dynamical system, Quantum Walk, Pachner move, dynamical triangulation, general relativity
vertex = [circle, fill = white, draw = black]
1 Introduction
Quantum walks. Quantum cellular automata are an extension of cellular automata to quantum computing : cells can now be in a quantum superposition of states instead of a single state, and their evolution is (i) unitary ; (ii) homogeneous (translationinvariant and timeindependant) ; (iii) causal, id est it only depends on a finite neighborhood of the cell. Just as CAs are Turing complete, that is any algorithm can be simulated by a CA, QCAs can simulate any quantum algorithm [8]. Quantum walks are a particular type of QCAs that represent the propagation of a quantum particle on the lattice [13]. Their study is blossoming, for two parallel reasons.
On the one hand, QWs have enabled the discovery of whole series of novel quantum computing algorithms for the future quantum computers, for instance [2, 25], or allow a natural and intuitive expression of those algorithms, for instance the Grover search [1]: the walker explores a graph encoding the instance of the problem, and converges to the cell encoding the solution to the problem.
On the other hand, QWs have also enabled the discovery of a whole series of novel quantum simulation schemes for the nearfuture simulation devices, and allow more intuitive expressions of these schemes [11, 22]. Quantum simulations are what led Feynman to introduce quantum computing in the first place [17]. Although universal quantum computers are not yet a reality, QWlike quantum simulation devices have already been designed [18, 24] : the walker propagates on the square lattice in such a way that the continuum limit of its behavior converges towards the physics equation that is to be simulated [15, 16]. Those schemes are both (i) stable numerically, even for classical computers—therefore converging as long as they are consistent [10] ; (ii) simple discrete models of the physical phenomena that conserve unitarity, homogeneity, causality and sometimes even Lorentzcovariance [7, 12]—and thus provide playgrounds to discuss foundational questions in Physics [20]. In a nutshell, QWs are becoming a new language to express quantum physical phenomena.
Motivations. Although QWs have already been extensively studied when the lattice is fixed, to the best of our knowledge they have never been studied in cases where we allow the lattice to change. Classical cellular automata on dynamical lattices in one and two dimensions have been introduced recently by [21, 19]. Our goal is thus to develop and study a QW on a $2\mathrm{dimensional}$ lattice, where the dynamics of the lattice depends on the walker’s evolution, and viceversa, which is reminiscent of the basic mechanism of Einstein field equations, governing spacetime dynamics. More particularly, we would like to have two already elegant theories to work together. On the one hand, the family of QWs considered here is one described in [5], as while being very simple, it has the Dirac Equation as a continuous limit and can easily be extended to account for a curved metric [6]. On the other hand, Pachner moves are a kind of transformations of the lattice which change the triangulation but not the topology. The dynamics of a lattice subject to Pachner moves has already been studied, e.g., in the context of lattice gas models [19] or complex networks [14]. Although we focus on the interaction between the dynamical lattice and one walker, we believe that results are already rich enough, displaying the main features of the multiwalkers theory, namely quantum cellular automata.
Plan. The paper is organized as follows. In section 2, we remind the reader of the definition of the quantum walk over the triangular lattice, introduced in [5], and the definition of Pachner moves. In section 3, we extend this quantum walker to a triangular lattice subject to Pachner moves. In section 4 we write the global equation that rules the behavior of the walker and the lattice. Then, in section 5, we show numerical simulations for different families of discrete surfaces and finally discuss local and global properties of the lattice and the walker independently.
2 Recap : Quantum Walk on the triangular lattice and Pachner moves
2.1 Quantum walk on the triangular lattice
To define the quantum walk over the triangular lattice, we consider the Hilbert space $\mathscr{H}={\mathscr{H}}_{e}\otimes {\mathscr{H}}_{s}$ where ${\mathscr{H}}_{e}$ is spanned by the basis states $\text{ket}e$ with $e$ an edge of the lattice and ${\mathscr{H}}_{s}$ is spanned by the basis states $\text{ket}\uparrow $ and $\text{ket}\downarrow $. If $v$ is a triangle and $k\in \{1,2,3\}\cong \mathbb{Z}/3\mathbb{Z}$ we therefore write
$$\psi (t,v,k)=\left(\begin{array}{c}\hfill {\psi}^{\uparrow}(t,v,k)\hfill \\ \hfill {\psi}^{\downarrow}(t,v,k)\hfill \end{array}\right)$$ 
to represent the upper and lower components of the field, that we call spin, carried by the $k\mathrm{th}$ edge of $v$.
A step of the quantum walker is applied to an encoding of the field : $\stackrel{~}{\psi}(t,v,k)={U}_{k}\psi (t,v,k)$. Let us label each triangle with the spin ($\uparrow $ or $\downarrow $), such that any two adjacent triangles have different spins. A step can then be divided into two substeps :

•
first, rotate each triangle according to its label : if triangle $v$’s label is $s$, we set
$${\stackrel{~}{\psi}}^{s}(t+\frac{\u03f5}{2},v,k)={\stackrel{~}{\psi}}^{s}(t,v,k1)$$ 
•
then, apply a unitary to each edge :
$$\stackrel{~}{\psi}(t+\u03f5,v,k)=W\stackrel{~}{\psi}(t+\frac{\u03f5}{2},v,k)$$
Since adjacent triangles have different labels, this can be rewritten as a whole as
$$\stackrel{~}{\psi}(t+\u03f5,v,k)=W\left(\begin{array}{c}\hfill {\stackrel{~}{\psi}}^{\uparrow}(t,v,k1)\hfill \\ \hfill {\stackrel{~}{\psi}}^{\downarrow}(t,v,k1)\hfill \end{array}\right)$$ 
When $W$ and the ${U}_{k}$ are wellchosen, making three steps yields an equation that converges, when $\u03f5$ converges to $0$, to the $(2+1)\mathrm{dimensional}$ Dirac Equation, i.e., the partial differential equation governing the dynamics of matter particles, e.g., electrons. [5].
2.2 Pachner moves
The triangular lattice is a triangulation of the plane and thus a discrete manifold. We can therefore apply Pachner moves to it. An $n\mathrm{to}m$ Pachner move is done by taking a subset of $n$ triangles of a manifold and replacing it by its complementary in the discrete $(n+m)\mathrm{dimensional}$ sphere, $\partial {\mathrm{\Delta}}_{n+m}$. It is easier to visualize in the dual setting of graphs (each triangle of the complex is a vertex and each side of the triangle is an edge between the two triangles it separes, see figure 1) [4], as in figure 2.
Pachner moves are remarkable because any discrete manifold homeomorphism can be seen as a finite sequence of Pachner moves, therefore they do not change the topology of the surface. Thus by allowing Pachner moves on our lattice we actually allow it to transform into any topologically equivalent discrete manifold.
Since $\partial {\mathrm{\Delta}}_{3}$ is a tetrahedron, one can see $1\mathrm{to}3$ Pachner moves as creating a well in the lattice, and $3\mathrm{to}1$ Pachner moves as removing those wells.
3 Coupling the Quantum Walker with Pachner moves
3.1 The lattice
In section 2, the triangles of the lattice labeled with a spin ($\uparrow $ or $\downarrow $), telling us which component of the field the triangle carries. An important property is that two adjacent triangles cannot be labeled with the same spin, as both components of the walker on the edge they share must be propagated. It does not hold true when taking Pachner moves into account as $1\mathrm{to}3$ Pachner moves create $3\mathrm{cycles}$ (it is impossible to find a $2\mathrm{coloration}$ of a graph with $3\mathrm{cycles}$). We thus introduce the following set of labels :
$$\mathrm{\Sigma}=\{(\uparrow ,\uparrow ,\uparrow ),(\downarrow ,\downarrow ,\downarrow ),(\uparrow ,\uparrow ,\downarrow ),(\downarrow ,\downarrow ,\uparrow )\}$$ 
A triangle being labeled $({s}_{1},{s}_{2},{s}_{3})$ means that it carries the ${s}_{k}$ component of its $k\mathrm{th}$ side for each $i\in \mathbb{Z}/3\mathbb{Z}$. The triangular lattice can thus be labeled the same way as in section 2, by identifying $\uparrow $ with $(\uparrow ,\uparrow ,\uparrow )$ and $\downarrow $ with $(\downarrow ,\downarrow ,\downarrow )$.
We therefore define our new lattice as a simplicial complex where each triangle is labeled with an element of $\mathrm{\Sigma}$, or, similarly, as a labeled graph where each vertex represents a triangle, each edge represents a side, the vertices are labeled with elements of $\mathrm{\Sigma}$ and the edges are labeled with elements of $\pi =\mathbb{Z}/3\mathbb{Z}$.
3.2 Evolution of the lattice under Pachner moves
In the simplicial complex setting, Pachner moves can be seen as replacing a subset of the complex with its complementary in a simplicial sphere $\partial {\mathrm{\Delta}}_{n}$. To define them in our labeled simplicial complex setting, we label the $3\mathrm{dimensional}$ sphere as in figure 3.
Making a Pachner move now amounts to taking the complementary in the labeled version of $\partial {\mathrm{\Delta}}_{3}$ and then inverting the labels ($\uparrow $ becomes $\downarrow $ and $\downarrow $ becomes $\uparrow $) so that we still have that two adjacent triangles each carry a different component of the field along their shared edge (figure 4).
Notice that this means the $1\mathrm{to}3$ Pachner move is still the inverse of the $3\mathrm{to}1$ Pachner move and that the $2\mathrm{to}2$ Pachner move is still its own inverse.
We now show that we can make Pachner moves whenever we want to.
Lemma 3.1.
Two adjacent triangles always have different labels.
Proof.
Consider two adjacent triangles with labels $({s}_{1},{s}_{2},{s}_{3})$ and $({s}_{1}^{\prime},{s}_{2}^{\prime},{s}_{3}^{\prime})$, sharing their $k\mathrm{th}$ side. We made sure that after any sequence of Pachner moves two adjacent triangles each carry a different component along their shared edge. Therefore ${s}_{k}\ne {s}_{k}^{\prime}$, hence $({s}_{1},{s}_{2},{s}_{3})\ne ({s}_{1}^{\prime},{s}_{2}^{\prime},{s}_{3}^{\prime})$ : the two triangles have different labels. ∎
Corollary 3.2.
It is always possible to apply a Pachner move on a complete subgraph of the lattice, as long as it has less than $\mathrm{4}$ vertices.
3.3 The quantum walker
At each timestep $t$, the field $\stackrel{~}{\psi}$ and the lattice evolve in the following order :

•
first, each triangle rotates its internal components : if triangle $v$’s label is $({s}_{1},{s}_{2},{s}_{3})$,
$${\stackrel{~}{\psi}}^{{s}_{k}}(t+\mathrm{\Delta}t,v,k)={\stackrel{~}{\psi}}^{{s}_{k1}}(t,v,k1)$$ 
•
second, we apply $W$ to each edge :
$$\stackrel{~}{\psi}(t+\mathrm{\Delta}t,v,k)=W\stackrel{~}{\psi}(t,v,k)$$
Notice that, at this point, if the lattice is the standard triangular lattice, the walker evolves exactly as in section 2.

•
third, we apply the Pachner moves for this timestep.
3.4 Evolution of the walker during $1\mathrm{to}3$ and $2\mathrm{to}2$ Pachner moves
A $1\mathrm{to}3$ Pachner move can be seen as adding three new edges inside a triangle. It therefore makes sense to have $\stackrel{~}{\psi}$ stay the same on the edges that already existed before the Pachner move, and to set it to $0$ on the newly created edges (so that we still have $\text{norm}{\psi}^{2}=1$) (figure 5).
Similarly, a $2\mathrm{to}2$ Pachner move can be seen as changing which edges are part of the same triangle, without changing the edges themselves. It therefore makes sense to have $\stackrel{~}{\psi}$ stay the same on those edges.
3.5 Evolution of the walker during $3\mathrm{to}1$ Pachner moves
The evolution during $3\mathrm{to}1$ Pachner moves is more difficult to define. Indeed, such a move deletes edges. This means that if $\stackrel{~}{\psi}$ changes only on a finite number of edges, reversibility does not hold (the linear transformation acts on a finite vector space but has a nonzero kernel, thus it is not injective). Since we want reversibility to hold true, the evolution has to take into account the value $\stackrel{~}{\psi}$ on an infinite number of edges. This is a problem as it would be best that Pachner moves only act locally, that is on a finite number of edges.
To solve this first problem we make the assumption that at time $t=0$ (and therefore at any time $t$) the walker is in a superposition of a finite number of states, that is $\stackrel{~}{\psi}(t=0)$ is equal to $0$ on a cofinite set of edges. This way, it is possible to have a unitary that acts on a vector space of infinite dimension while having it change only a finite number of values in practice.
This can for example be done with a translation. The most intuitive one we found is depicted on figure 7. If three triangles make a $3\mathrm{cycle}$ onto which a $3\mathrm{to}1$ Pachner move is applied, then any internal component carried by one of those triangles (say, $v$) on one of its edges internal to the $3\mathrm{cycle}$ (say, its $k\mathrm{th}$ side) is translated along the side of $v$ that goes out of the $3\mathrm{cycle}$ into the neighboring triangle $w$, and then is translated again along the $k\mathrm{th}$ side of $w$ to finally replace the internal component of the neighbor of $w$ on its $k\mathrm{th}$ side. The old value of this component is then translated along the same edges and replaces another internal component that also gets translated and replaces another value, etc.
Once the translation is done, the edges internal to the $3\mathrm{cycle}$ can be deleted as the information they carried was sent outside of the $3\mathrm{cycle}$.
It does make sense physically to have a triangle influence another one which is two edges away in the graph as the geometrical distance between the triangles is still one (the triangles share a vertex).
Lemma 3.3.
Consider the triangular lattice and apply a finite number of $\mathrm{1}\mathrm{}\mathrm{to}\mathrm{}\mathrm{3}$ and $\mathrm{3}\mathrm{}\mathrm{to}\mathrm{}\mathrm{1}$ Pachner moves. Then any triangle of the lattice appears at most once in the sequence of the triangles visited during a translation along two edges, as previously described.
Proof.
It is true for the triangular lattice : a translation along two edges amounts to translating along a fixed vector, therefore any triangle is visited at most once.
Let us now consider a lattice where this holds true. Then applying a $1\mathrm{to}3$ or a $3\mathrm{to}1$ Pachner move keeps this property true. Indeed, applying such a Pachner move does not destroy any cycle, as can be seen in figure 8. If we were to find a cycle in the new lattice, we could apply the inverse Pachner move and get the original lattice, without having destroyed the cycle. Therefore the cycle already existed in the original lattice, which contradicts our assumption.
By induction, the property thus holds true after a finite number of such Pachner moves. ∎
Corollary 3.4.
When considering only $\mathrm{1}\mathrm{}\mathrm{to}\mathrm{}\mathrm{3}$ and $\mathrm{3}\mathrm{}\mathrm{to}\mathrm{}\mathrm{1}$ Pachner moves, the previously described unitary is reversible (since no cycle appear in the translations nothing gets translated to the edges that will be removed) but still changes the value of $\stackrel{\mathrm{~}}{\psi}$ on a finite number of edges (since no cycle appear in the translations, at some point all the nonzero edges have been exhausted and we’re only translating zeros).
Unfortunately this does not hold true anymore if we consider $2\mathrm{to}2$ Pachner moves, as they introduce cycles. We were not able to find any unitary for $3\mathrm{to}1$ Pachner moves that worked when considering $2\mathrm{to}2$ Pachner moves as well. We do believe though it should be possible to consider $2\mathrm{to}2$ Pachner moves, either by finding such a unitary or by disallowing $2\mathrm{to}2$ Pachner moves when the lattice has a certain structure.
We therefore decided to restrict ourselvesto $1\mathrm{to}3$ and $3\mathrm{to}1$ Pachner moves here as $2\mathrm{to}2$ Pachner moves also create problems when trying to visualise the lattice in $3$ dimensions.
3.6 When to make Pachner moves
In practice, making a $1\mathrm{to}3$ or a $3\mathrm{to}1$ Pachner move curves the metric, as a particle has to go through more triangles to travel a fixed distance after a $1\mathrm{to}3$ Pachner move then before one. In general relativity, it is matter that curves the metric and viceversa. We adopted this point of view here, choosing to make a $1\mathrm{to}3$ Pachner move (creating a well) on a triangle $v$ whenever the probability to be on that triangle is above a threshold $\alpha $ (if $v$ is labelled $({s}_{1},{s}_{2},{s}_{3})$, whenever ${\sum}_{k=1}^{3}\text{abs}{\psi}^{{s}_{k}}{(t,v,k)}^{2}>\alpha $), and to make a $3\mathrm{to}1$ Pachner move (removing a well) whenever the probability to be inside that well is below a threshold $\beta $ (if $u$ and $v$ are glued along their first side, $v$ and $w$ along their second side and $w$ and $u$ along their third side, we make a Pachner move whenever $$).
4 Discrete equation of the walker
We now write the discrete equation of the walker, that is $\psi (t+\u03f5)$ as a function of $\psi (t)$. To do so, we first change the way we write $\psi $, as thinking of it as a function of the triangles is cumbersome to write the equations for the Pachner moves. Instead, we choose a triangle of the triangular lattice to be its origin. We can keep track of it when it is subject to Pachner moves as a $1\mathrm{to}3$ Pachner moves always create a triangle with the same label as the triangle to which it is applied (this would not be true had we kept $2\mathrm{to}2$ Pachner moves) : this new triangle becomes the origin. This makes the dual graph a pointed graph, and therefore every triangle can be thought of as the language of words that correspond to a path from the origin to the triangle [9]. For example, if a triangle can be thought of as a language $v$, then its neighbor on its first side can be thought of as the language $v.1=\{u.1\mid u\in v\}$. We identify any $u\in v$ with $v$ itself. We can now introduce two ways of writing $\psi $ :

•
if triangle $v$’s label is $({s}_{1},{s}_{2},{s}_{3})$, we write:
$$\psi (t,v:k)={\psi}^{{s}_{k}}(t,v,k)$$ $$\psi (t,v:k:v.k)=\psi (t,v,k)$$ 
•
if triangle $v$ carries the $\uparrow $ component of its $k\mathrm{th}$ side and its neighbor $v.k$ on that side carries the $\downarrow $ component, we write:
$$\psi (t,\begin{array}{c}\hfill v\hfill \\ \hfill k\hfill \\ \hfill w\hfill \end{array})=\left(\begin{array}{c}\hfill \psi (t,v:k)\hfill \\ \hfill \psi (t,v.k:k)\hfill \end{array}\right)$$
After rotating the triangles and applying $W$, we have:
$$\stackrel{~}{\psi}(t+\u03f5,\begin{array}{c}\hfill v\hfill \\ \hfill k\hfill \\ \hfill w\hfill \end{array})=W\left(\begin{array}{c}\hfill \stackrel{~}{\psi}(t,v:k1)\hfill \\ \hfill \stackrel{~}{\psi}(t,w:k1)\hfill \end{array}\right)=(WR\stackrel{~}{\psi}(t))\left(\begin{array}{c}\hfill v\hfill \\ \hfill k\hfill \\ \hfill w\hfill \end{array}\right)$$ 
(we see $W$ as both a $2\mathrm{dimensional}$ operator when it acts on a single edge and an infinite dimensional operator when it acts on all the edges).
After applying all the $1\mathrm{to}3$ Pachner moves, we have:
$\psi $  $(t+3\u03f5,\begin{array}{c}\hfill {\mathrm{\Pi}}_{i=1}^{n}{k}_{i}{({k}_{i+1}{k}_{i})}^{{\mathrm{\U0001d7d9}}_{1{\to}_{t+2\u03f5}3}\left({\mathrm{\Pi}}_{j=1}^{i}{k}_{j}\right)}\hfill \\ \hfill k\hfill \\ \hfill \left({\mathrm{\Pi}}_{i=1}^{n}{k}_{i}{({k}_{i+1}{k}_{i})}^{{\mathrm{\U0001d7d9}}_{1{\to}_{t+2\u03f5}3}\left({\mathrm{\Pi}}_{j=1}^{i}{k}_{j}\right)}\right)k\hfill \end{array})=$  
$\left(1{\mathrm{\U0001d7d9}}_{1{\to}_{t+2\u03f5}3}\left({\mathrm{\Pi}}_{i=1}^{n}{k}_{i}\right)(1{\delta}_{{k}_{n}=k})\right)\psi (t+2\u03f5,\begin{array}{c}\hfill {\mathrm{\Pi}}_{i=1}^{n}{k}_{i}\hfill \\ \hfill k\hfill \\ \hfill \left({\mathrm{\Pi}}_{i=1}^{n}{k}_{i}\right)k\hfill \end{array})$ 
This describes both how triangles are renamed (we add letters in the middle of the word for each Pachner move done on the corresponding path) and what becomes of $\psi $ (it becomes zero only if the triangle is subject to a Pachner move and if the edge referred to is now part of the new $3\mathrm{cycle}$, otherwise it stays the same). The function ${\mathrm{\U0001d7d9}}_{1{\to}_{t}3}$ tells us whether a $1\mathrm{to}3$ Pachner move is to be applied on the triangle at time $t$ :
$${\mathrm{\U0001d7d9}}_{1{\to}_{t}3}(v)=\{\begin{array}{ccc}\hfill 1\hfill & \hfill \mathrm{if}\hfill & \hfill {\sum}_{k=1}^{3}\text{abs}\psi {(t,v:k)}^{2}>\alpha \hfill \\ \hfill 0\hfill & \hfill \mathrm{otherwise}\hfill & \hfill \hfill \end{array}$$ 
Finally, let $3\mathrm{cycles}(t)$ be the set
$$ 
Then, after the $3\mathrm{to}1$ Pachner moves,
$$\stackrel{~}{\psi}(t+2\u03f5)=\left({\mathrm{\Pi}}_{c\in 3\mathrm{cycles}(t+\u03f5)}{D}_{c}\circ {T}_{c}\right)\stackrel{~}{\psi}(t+\u03f5)$$ 
with
$({T}_{c}\stackrel{~}{\psi})(u:k)$  $={\delta}_{\exists n\in {\mathbb{N}}^{*},u.{(k(k+1))}^{n}:k+1\in c}\stackrel{~}{\psi}(u.k(k+1):k)$  
$+{\delta}_{\exists n\in {\mathbb{N}}^{*},u.{(k(k+2))}^{n}:k+2\in c}\stackrel{~}{\psi}(u.k(k+2):k)$  
$+{\delta}_{\forall n\in \mathbb{N},l\in \{k+1,k+2\},u.{(kl)}^{n}:l\notin c}\stackrel{~}{\psi}(u:k)$ 
and
$$({D}_{c}\stackrel{~}{\psi})(u={\mathrm{\Pi}}_{i=1}^{n}{k}_{i}:k)=\stackrel{~}{\psi}\left({\mathrm{\Pi}}_{i\in {I}_{c}^{u}}{k}_{i}\right)$$ 
where
$${I}_{c}^{u}=\left\{i\in \u27e61,n\u27e7\right{\mathrm{\Pi}}_{j=1}^{i}{k}_{j}:{k}_{i+1}:\left({\mathrm{\Pi}}_{j=1}^{i}{k}_{j}\right){k}_{i+1}\notin c\}$$ 
${T}_{c}$ is the unitary that translates the values of $\psi $ and ${D}_{c}$ is the one that renames the triangles after deleting the edges. Notice that we did not specify in which order the $3\mathrm{cycles}$ $c$ should be taken : we chose to do so in descending probability, but it does not seem to influence the overall behavior of the walk.
Putting all those equations together gives
$\stackrel{~}{\psi}$  $(t+3\u03f5,\begin{array}{c}\hfill {\mathrm{\Pi}}_{i=1}^{n}{k}_{i}{({k}_{i+1}{k}_{i})}^{{\mathrm{\U0001d7d9}}_{1{\to}_{t}3}\left({\mathrm{\Pi}}_{j=1}^{i}{k}_{j}\right)}\hfill \\ \hfill k\hfill \\ \hfill \left({\mathrm{\Pi}}_{i=1}^{n}{k}_{i}{({k}_{i+1}{k}_{i})}^{{\mathrm{\U0001d7d9}}_{1{\to}_{t}3}\left({\mathrm{\Pi}}_{j=1}^{i}{k}_{j}\right)}\right)k\hfill \end{array})=$  
$\left(1{\mathrm{\U0001d7d9}}_{1{\to}_{t}3}\left({\mathrm{\Pi}}_{i=1}^{n}{k}_{i}\right)(1{\delta}_{{k}_{n}=k})\right)\times \left(\left({\mathrm{\Pi}}_{c\in 3\mathrm{cycles}}{D}_{c}\circ {T}_{c}\right)WR\stackrel{~}{\psi}(t)\right)\left(\begin{array}{c}\hfill {\mathrm{\Pi}}_{i=1}^{n}{k}_{i}\hfill \\ \hfill k\hfill \\ \hfill \left({\mathrm{\Pi}}_{i=1}^{n}{k}_{i}\right)k\hfill \end{array}\right)$ 
Notice that we chose to apply the $3\mathrm{to}1$ Pachner moves before the $1\mathrm{to}3$ ones : this is because doing the converse would mean instantly deleting the newly created $3\mathrm{cycles}$.
This equation is highly notlinear and prohibitive to study as itself analytically. Still, we can find some limite cases, for instance that choosing $\alpha =1$ yields the quantum walk over the triangular lattice from section 2 (since $3\mathrm{cycles}(t)$ is always empty) or that choosing $\beta =0$ amounts to overlooking $3\mathrm{to}1$ Pachner moves.
5 Numerical simulations
As for any nonlinear dynamical equations, we choose to investigate global and local features of the system with accurate numerical simulations. For our setup, we chose for $\psi (t=0)$ to be $\frac{1}{\sqrt{3}}$ on each of the three internal components of the origin triangle and $0$ elsewhere, in such a way the norm of $\psi $ sums to the unity.
Then, we also chose $\beta $ to be a function of $\alpha $, since, making an analogy with mechanics, usually a surface has a single elasticity constant that is involved in both stretching and relaxation. Thus, $\alpha $ will be the only parameter in the evolution and will represent the response of the discrete surface to the presence of the walker. In particular, an interesting relationship between $\alpha $ and $\beta $ is that when $\beta >6\alpha $, any $3\mathrm{cycle}$ in the lattice is unstable, that is it is always subject to a Pachner move at each step. Indeed, if the probability of being inside the $3\mathrm{cycle}$ is high enough (higher than $\beta $) so that we do not apply a $3\mathrm{to}1$ Pachner moves onto it, than there is an edge $(v,k)$ inside it with probability $\text{abs}\psi {(t,v,k)}^{2}>\beta /6>\alpha $, thus a $1\mathrm{to}3$ Pachner move is applied to $v$. We thus considered, among others, the relationship $\beta =3\alpha $, as a middle ground between full unstability ($\beta >6\alpha $) and quasistability (when $$, no edge can be the sole cause of a $1\mathrm{to}3$ Pachner move once it was subject to a $3\mathrm{to}1$ Pachner move, by a similar reasoning).
At each timestep $t$, we considered the walker and lattice properties independently. In particular,

•
to study the structure of the lattice itself, we measured its discrete global and local curvature: it is well known that curved spacetime can be approximated by equilateral triangles [23, 3], or simplices in higher dimensions, whose lengths ${\u03f5}_{l}$, may ultimately be shrunk to zero to recover a continuum theory. Dynamical triangulation of space can incorporate both negative and positive curvature by suitably gluing the triangles together. Here we use a simple definition of the curvature concentrated in the deficit angles at the vertices, which is reminiscent of Regge calculus: if a vertex of a lattice is shared by $n$ triangles, then the vertex’s curvature is equal to $2\pi n\pi /3$. The global curvature of the lattice is then the sum of the local curvatures of its vertices. For a 2dimensional surface, it must be constant and vanishing, as predicted from General relativity in 2D. For instance in a triangular lattice where each vertex is shared by six triangles, the curvature is equal to $0$. Performing a $1\mathrm{to}3$ Pachner move on a triangle means adding negative local curvature $(\pi )$ to the created vertex and positive local curvature $(\pi /3)$ to each of the three vertices of the former triangle, thus leaving the global curvature unchanged. In particular we consider that at time $t=0$ the lattice is globally and locally flat as in [5], thus at all times the global curvature is equal $0$. To have a meaningful global measurement of the curvature, we also computed the number of wells in the lattice (in other words the number of $1\mathrm{to}3$ Pachner moves carried out minus the number of $3\mathrm{to}1$ Pachner moves carried out).

•
to study the walker itself, we measured the variance of its position $\mathrm{Var}[e]=E[{e}^{2}]E{[e]}^{2}$, with $E[e]={\sum}_{e}e{\mathrm{\Psi}}^{2}$ the expectation value of the position of the walker along edge $\widehat{e}$. More precisely, because we expected that the variance be proportional to ${t}^{\eta}$, we chose to compute $\frac{\mathrm{d}\mathrm{log}(\mathrm{Var}[e])}{\mathrm{d}\mathrm{log}t}$ to have access to the exponent $\eta $. Notice that if the walk is symmetric with respect to $x$ and $y$, ${\eta}_{x}={\eta}_{y}$. Because this condition holds for our walk, we will use $\eta $ as the global variance of the walker. Moreover, note that over the flat triangular lattice described in section 2, $\eta $ converges to $2$ (the blue points in figure LABEL:fig:variance_3alpha_equals_beta), which means that the dynamics is ballistic.
As previously stated, the global curvature of the lattice is equal to $0$, as predicted by the physical model. If we now look at a ball of fixed radius, the local curvature is no longer constant. Actually, whatever the values of $\alpha $ and $\beta $ chosen, the local curvature always evolves following the same scheme, as depicted in figure 9 : (i) first, it increases steadily, as in ${t}^{a}$ : the particle is localized and the surface stretches ; (ii) second, it decreases very fast, as in ${e}^{b{t}^{2}}$ : the particle is not localized anymore and the surface relaxes ; (iii) third, some small wells appear but disappear almost immediately ; (iv) fourth, the local curvature is again constant and equal to zero : the particle’s localisation is completely spread out leaving no place for Pachner moves. The lattice has reached its final state as the flat triangular lattice. The total number of wells follows the same model, although less accurately, as depicted in figure 10.
Notice that the fact that the lattice always ends up as the flat triangular lattice means that when $t\gg 1$, our walker also behaves exactly as the quantum walker over the flat triangular lattice. This is confirmed by how the variance evolves (figure 11) : although it might grow very slowly during a first phase (when the particle is localized), exploring a clear subdiffusion and diffusion regime, it always ends up behaving as ${t}^{2}$, exactly as the variance of the walker over the flat triangular lattice.
Finally, we wanted to investigate how our model behaves when the metrics is subject to internal noise. We chose to add a noise to the value of $\alpha $ (we considered $\alpha ={\alpha}_{0}{e}^{x(t)}$ where $x(t)$ is chosen randomly in $[\frac{\sigma}{2},\frac{\sigma}{2}]$), in a way to produce random fluctuations of the triangulation and thus of the local curvature. We observed the same patterns (figure 12) : this suggest that our dynamics is globally faultresistant but can also highlight how the order of the Pachner moves in the evolution of the metrics doesn’t matter at large scale.
The main global property that we found is that the local curvature for a ball of radius $1$ and the number of wells both behave as $t\mapsto c{t}^{a}{e}^{b{t}^{2}}$ in the deterministic and random case. This is particularly interesting because the exponential decrease (${e}^{b{t}^{2}}$) can be found in multiple models throughout physics and the constant $b$ is usually associated to an internal cutoff of the system. We thus suspected it was a function of $\alpha $. And indeed, plotting the value of $b$ against $\alpha $, as in figure 13, we can see that the constant $1/b$ depends linearly on the logarithm of $\alpha $ (where the ratio depends on the relationship between $\alpha $ and $\beta $), and similarly for the time at which the local curvature goes from decreasing exponentially fast to oscillating at small values (tmax on the graphs). Moreover, the fact that those constants are the same in the model of the curvature and in the model of the number of wells corroborates the idea that they are linked to the physical constants of the lattice.
6 Summary and future work
We introduced, to the best of our knowledge, the first exemple of QW over dynamical triangular lattice, where rules changing the geometry are constructed using Pachner moves. Although, for simplicity, we restricted ourselves to $1\mathrm{to}3$ and $3\mathrm{to}1$ Pachner moves, we do believe it should be possible to extend our walker to $2\mathrm{to}2$ Pachner moves. We then wrote the equation that governs the behavior of the walker. It is highly nonlinear, and represents the strong coupling between the dynamics of the walker and the lattice : the walker evolves according to the state of the lattice at time $t$, and the lattice transforms according to the presence probability of the walker at the same instant. The wave function does not depend directly on the coordinates of the lattice, which makes it prohibitive to compute the continuous limit. Still we think that a differential form can be derived in a mean field approximation or via coarsegraining maps, and we leave it for future research. Finally we found a robust local characterization of the curvature and the global number of wells, which has never been studied before, to the best of our knowledge. The evolution ${t}^{a}{e}^{b{t}^{2}}$ is made of two factors : (i) one is a power law dominant for small $t$, which accounts to the growing of the local curvature, (ii) the other is the exponential decay which eventually overwhelms the powerlaw behavior at very large $t$. Although it does not scale as a power low, it is a good approximation and in particular it naturally capture finite size effects of metrics. Moreover we also studied numerically random oscillations of the metrics, showing that the large scale features of the walker and of the lattice dynamics are kept invariant. In future works, we would like to extend our model in two directions: considering multiparticle QCA and to higher dimensional simplicices complex, e.g. tetrahedra, where global curvature is no longer constant.
References
 [1] G. Abal, R. Donangelo, M. Forets, and R. Portugal. Spatial quantum search in a triangular network. Mathematical Structures in Computer Science, 22:521–531, 5 2012.
 [2] Andris Ambainis, Andrew M Childs, Ben W Reichardt, Robert Špalek, and Shengyu Zhang. Any andor formula of size n can be evaluated in time n^1/2+o(1) on a quantum computer. SIAM Journal on Computing, 39(6):2513–2530, 2010.
 [3] Jan Ambjorn, Mauro Carfora, Annalisa Marzuoli, et al. The geometry of dynamical triangulations, volume 50. Springer Science & Business Media, 1997.
 [4] P Arrighi, C Chouteau, S Facchini, and S Martiel. Causal dynamics of discrete manifolds. In Proceedings of NCMA’2018. Österreichische Computer Gesellschaft, 2018.
 [5] Pablo Arrighi, Giuseppe Di Molfetta, Iván MárquezMartín, and Armando Pérez. Dirac equation as a quantum walk over the honeycomb and triangular lattices. Physical Review A, 97(6):062111, 2018.
 [6] Pablo Arrighi, Giuseppe Di Molfetta, Iván MárquezMartín, and Armando Pérez. From curved spacetime to spacetimedependent local unitaries over the honeycomb and triangular quantum walks. arXiv preprint arXiv:1812.02601, 2018.
 [7] Pablo Arrighi, Stefano Facchini, and Marcelo Forets. Discrete lorentz covariance for quantum walks and quantum cellular automata. New Journal of Physics, 16(9):093007, 2014.
 [8] Pablo Arrighi and Jonathan Grattage. Partitioned quantum cellular automata are intrinsically universal. Natural Computing, 11(1):13–22, 2012.
 [9] Pablo Arrighi, Simon Martiel, and Vincent Nesme. Generalized cayley graphs and cellular automata over them. arXiv preprint arXiv:1212.0027, 2012.
 [10] Pablo Arrighi, Vincent Nesme, and Marcelo Forets. The dirac equation as a quantum walk: higher dimensions, observational convergence. Journal of Physics A: Mathematical and Theoretical, 47(46):465302, 2014.
 [11] Iwo BialynickiBirula. Weyl, dirac, and maxwell equations on a lattice as unitary cellular automata. Physical Review D, 49(12):6920, 1994.
 [12] Alessandro Bisio, Giacomo Mauro D’Ariano, and Paolo Perinotti. Quantum walks, weyl equation and the lorentz group. Foundations of Physics, 47(8):1065–1076, 2017.
 [13] Pedro CS Costa, Renato Portugal, and Fernando de Melo. Quantum walks via quantum cellular automata. Quantum Information Processing, 17(9):226, 2018.
 [14] Diamantino C da Silva, Ginestra Bianconi, Rui A da Costa, Sergey N Dorogovtsev, and José FF Mendes. Complex network view of evolving manifolds. Physical Review E, 97(3):032316, 2018.
 [15] Giuseppe Di Molfetta, Marc Brachet, and Fabrice Debbasch. Quantum walks as massless dirac fermions in curved spacetime. Physical Review A, 88(4):042301, 2013.
 [16] Giuseppe Di Molfetta and Armando Pérez. Quantum walks as simulators of neutrino oscillations in a vacuum and matter. New Journal of Physics, 18(10):103038, 2016.
 [17] Richard P Feynman. Simulating physics with computers. International journal of theoretical physics, 21(6):467–488, 1982.
 [18] Maximilian Genske, Wolfgang Alt, Andreas Steffen, Albert H Werner, Reinhard F Werner, Dieter Meschede, and Andrea Alberti. Electric quantum walks with individual atoms. Physical review letters, 110(19):190601, 2013.
 [19] Anna Klales, Donato Cianci, Zachary Needell, David A Meyer, and Peter J Love. Lattice gas simulations of dynamical geometry in two dimensions. Physical Review E, 82(4):046705, 2010.
 [20] Seth Lloyd. A theory of quantum gravity based on quantum computation. arXiv preprint quantph/0501135, 2005.
 [21] Peter J Love, Bruce M Boghosian, and David A Meyer. Lattice gas simulations of dynamical geometry in one dimension. Philosophical Transactions of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 362(1821):1667–1675, 2004.
 [22] David A Meyer. From quantum cellular automata to quantum lattice gases. Journal of Statistical Physics, 85(56):551–574, 1996.
 [23] Tullio Regge. General relativity without coordinates. Il Nuovo Cimento (19551965), 19(3):558–571, 1961.
 [24] Linda Sansoni, Fabio Sciarrino, Giuseppe Vallone, Paolo Mataloni, Andrea Crespi, Roberta Ramponi, and Roberto Osellame. Twoparticle bosonicfermionic quantum walk via integrated photonics. Physical review letters, 108(1):010502, 2012.
 [25] Guoming Wang. Efficient quantum algorithms for analyzing large sparse electrical networks. Quantum Information & Computation, 17(1112):987–1026, 2017.