Quantum Walk over a triangular lattice subject to Pachner move

  • 2019-08-12 15:14:56
  • Quentin Aristote, Giuseppe Di Molfetta
  • 0


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 non-linear 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

Quentin Aristote, Giuseppe Di Molfetta
Aix-Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France

We present a 2-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 non-linear 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 tae-bt2 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 (translation-invariant and time-independant) ; (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 near-future 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, QW-like 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 Lorentz-covariance [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-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 multi-walkers 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 =es where e is spanned by the basis states \kete with e an edge of the lattice and s is spanned by the basis states \ket and \ket. If v is a triangle and k{1,2,3}/3 we therefore write


to represent the upper and lower components of the field, that we call spin, carried by the k-th edge of v.

A step of the quantum walker is applied to an encoding of the field : ψ~(t,v,k)=Ukψ(t,v,k). Let us label each triangle with the spin ( or ), 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

  • then, apply a unitary to each edge :


Since adjacent triangles have different labels, this can be rewritten as a whole as


When W and the Uk are well-chosen, making three steps yields an equation that converges, when ϵ converges to 0, to the (2+1)-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-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)-dimensional sphere, Δ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.

Figure 1: Discrete manifold / graph duality

(a) Δ3 (b) 1-to-3 Pachner move

Figure 2: Pachner moves

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 Δ3 is a tetrahedron, one can see 1-to-3 Pachner moves as creating a well in the lattice, and 3-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 ( or ), 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-to-3 Pachner moves create 3-cycles (it is impossible to find a 2-coloration of a graph with 3-cycles). We thus introduce the following set of labels :


A triangle being labeled (s1,s2,s3) means that it carries the sk component of its k-th side for each i/3. The triangular lattice can thus be labeled the same way as in section 2, by identifying with (,,) and with (,,).

We therefore define our new lattice as a simplicial complex where each triangle is labeled with an element of Σ, or, similarly, as a labeled graph where each vertex represents a triangle, each edge represents a side, the vertices are labeled with elements of Σ and the edges are labeled with elements of π=/3.

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 Δn. To define them in our labeled simplicial complex setting, we label the 3-dimensional sphere as in figure 3.

Figure 3: Δ3 labeled

Making a Pachner move now amounts to taking the complementary in the labeled version of Δ3 and then inverting the labels ( becomes and becomes ) 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-to-3 Pachner move is still the inverse of the 3-to-1 Pachner move and that the 2-to-2 Pachner move is still its own inverse.

Figure 4: 1-to-3 Pachner move

We now show that we can make Pachner moves whenever we want to.

Lemma 3.1.

Two adjacent triangles always have different labels.


Consider two adjacent triangles with labels (s1,s2,s3) and (s1,s2,s3), sharing their k-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 sksk, hence (s1,s2,s3)(s1,s2,s3) : 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 4 vertices.

3.3 The quantum walker

At each timestep t, the field ψ~ and the lattice evolve in the following order :

  • first, each triangle rotates its internal components : if triangle v’s label is (s1,s2,s3),

  • second, we apply W to each edge :


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-to-3 and 2-to-2 Pachner moves

A 1-to-3 Pachner move can be seen as adding three new edges inside a triangle. It therefore makes sense to have ψ~ 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 \normψ2=1) (figure 5).

Figure 5: Evolution of the walker during a 1-to-3 Pachner move

Similarly, a 2-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 ψ~ stay the same on those edges.

Figure 6: Evolution of the walker during a 2-to-2 Pachner move

3.5 Evolution of the walker during 3-to-1 Pachner moves

The evolution during 3-to-1 Pachner moves is more difficult to define. Indeed, such a move deletes edges. This means that if ψ~ changes only on a finite number of edges, reversibility does not hold (the linear transformation acts on a finite vector space but has a non-zero kernel, thus it is not injective). Since we want reversibility to hold true, the evolution has to take into account the value ψ~ 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 ψ~(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-cycle onto which a 3-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-cycle (say, its k-th side) is translated along the side of v that goes out of the 3-cycle into the neighboring triangle w, and then is translated again along the k-th side of w to finally replace the internal component of the neighbor of w on its k-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.

Figure 7: Translation of the component internal to w on its first side during a 3-to-1 Pachner move

Once the translation is done, the edges internal to the 3-cycle can be deleted as the information they carried was sent outside of the 3-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 1-to-3 and 3-to-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.


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-to-3 or a 3-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. ∎

Figure 8: 1-to-3 and 3-to-1 Pachner have no influence on cycles
Corollary 3.4.

When considering only 1-to-3 and 3-to-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 ψ~ on a finite number of edges (since no cycle appear in the translations, at some point all the non-zero edges have been exhausted and we’re only translating zeros).

Unfortunately this does not hold true anymore if we consider 2-to-2 Pachner moves, as they introduce cycles. We were not able to find any unitary for 3-to-1 Pachner moves that worked when considering 2-to-2 Pachner moves as well. We do believe though it should be possible to consider 2-to-2 Pachner moves, either by finding such a unitary or by disallowing 2-to-2 Pachner moves when the lattice has a certain structure.

We therefore decided to restrict ourselvesto 1-to-3 and 3-to-1 Pachner moves here as 2-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-to-3 or a 3-to-1 Pachner move curves the metric, as a particle has to go through more triangles to travel a fixed distance after a 1-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-to-3 Pachner move (creating a well) on a triangle v whenever the probability to be on that triangle is above a threshold α (if v is labelled (s1,s2,s3), whenever k=13\absψsk(t,v,k)2>α), and to make a 3-to-1 Pachner move (removing a well) whenever the probability to be inside that well is below a threshold β (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 \normψ(t,u,1)2+\normψ(t,v,2)2+\normψ(t,w,3)2<β).

4 Discrete equation of the walker

We now write the discrete equation of the walker, that is ψ(t+ϵ) as a function of ψ(t). To do so, we first change the way we write ψ, 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-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-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.1uv}. We identify any uv with v itself. We can now introduce two ways of writing ψ :

  • if triangle v’s label is (s1,s2,s3), we write:

  • if triangle v carries the component of its k-th side and its neighbor v.k on that side carries the component, we write:


After rotating the triangles and applying W, we have:


(we see W as both a 2-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-to-3 Pachner moves, we have:

ψ (t+3ϵ,Πi=1nki(ki+1ki)𝟙1t+2ϵ3(Πj=1ikj)k(Πi=1nki(ki+1ki)𝟙1t+2ϵ3(Πj=1ikj))k)=

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 ψ (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-cycle, otherwise it stays the same). The function 𝟙1t3 tells us whether a 1-to-3 Pachner move is to be applied on the triangle at time t :


Finally, let 3-cycles(t) be the set


Then, after the 3-to-1 Pachner moves,



(Tcψ~)(u:k) =δn*,u.(k(k+1))n:k+1cψ~(u.k(k+1):k)





Tc is the unitary that translates the values of ψ and Dc is the one that renames the triangles after deleting the edges. Notice that we did not specify in which order the 3-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

ψ~ (t+3ϵ,Πi=1nki(ki+1ki)𝟙1t3(Πj=1ikj)k(Πi=1nki(ki+1ki)𝟙1t3(Πj=1ikj))k)=

Notice that we chose to apply the 3-to-1 Pachner moves before the 1-to-3 ones : this is because doing the converse would mean instantly deleting the newly created 3-cycles.

This equation is highly not-linear and prohibitive to study as itself analytically. Still, we can find some limite cases, for instance that choosing α=1 yields the quantum walk over the triangular lattice from section 2 (since 3-cycles(t) is always empty) or that choosing β=0 amounts to overlooking 3-to-1 Pachner moves.

5 Numerical simulations

As for any non-linear dynamical equations, we choose to investigate global and local features of the system with accurate numerical simulations. For our set-up, we chose for ψ(t=0) to be 13 on each of the three internal components of the origin triangle and 0 elsewhere, in such a way the norm of ψ sums to the unity.

Then, we also chose β to be a function of α, since, making an analogy with mechanics, usually a surface has a single elasticity constant that is involved in both stretching and relaxation. Thus, α 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 α and β is that when β>6α, any 3-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-cycle is high enough (higher than β) so that we do not apply a 3-to-1 Pachner moves onto it, than there is an edge (v,k) inside it with probability \absψ(t,v,k)2>β/6>α, thus a 1-to-3 Pachner move is applied to v. We thus considered, among others, the relationship β=3α, as a middle ground between full unstability (β>6α) and quasi-stability (when β<α, no edge can be the sole cause of a 1-to-3 Pachner move once it was subject to a 3-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 ϵ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π-nπ/3. The global curvature of the lattice is then the sum of the local curvatures of its vertices. For a 2-dimensional 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-to-3 Pachner move on a triangle means adding negative local curvature (-π) to the created vertex and positive local curvature (π/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-to-3 Pachner moves carried out minus the number of 3-to-1 Pachner moves carried out).

  • to study the walker itself, we measured the variance of its position Var[e]=E[e2]-E[e]2, with E[e]=ee|Ψ|2 the expectation value of the position of the walker along edge e^. More precisely, because we expected that the variance be proportional to tη, we chose to compute dlog(Var[e])dlogt to have access to the exponent η. Notice that if the walk is symmetric with respect to x and y, ηx=ηy. Because this condition holds for our walk, we will use η as the global variance of the walker. Moreover, note that over the flat triangular lattice described in section 2, η 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 α and β chosen, the local curvature always evolves following the same scheme, as depicted in figure 9 : (i) first, it increases steadily, as in ta : the particle is localized and the surface stretches ; (ii) second, it decreases very fast, as in e-bt2 : 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.

Figure 9: Local curvatures of the lattice in a ball of a radius 1, fit as tae-bt2c.
Figure 10: Number of wells in the lattice, fit as tae-bt2c
Figure 11: Gradiant of the logarithm of the variance : it always converges to 2.

Notice that the fact that the lattice always ends up as the flat triangular lattice means that when t1, 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 sub-diffusion and diffusion regime, it always ends up behaving as t2, 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 α (we considered α=α0ex(t) where x(t) is chosen randomly in [-σ2,σ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 fault-resistant but can also highlight how the order of the Pachner moves in the evolution of the metrics doesn’t matter at large scale.

(a) Curvature of the ball of radius 1 for α centered on α0=3-3 and β=3α. (b) Number of wells in the lattice for α centered on α0=3-5 and β=3α.

Figure 12: The dynamics is globally fault-resistant

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 tctae-bt2 in the deterministic and random case. This is particularly interesting because the exponential decrease (e-bt2) can be found in multiple models throughout physics and the constant b is usually associated to an internal cut-off of the system. We thus suspected it was a function of α. And indeed, plotting the value of b against α, as in figure 13, we can see that the constant 1/b depends linearly on the logarithm of α (where the ratio depends on the relationship between α and β), 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.

(a) Curvature when β=3α

(b) Number of wells when β=3α

Figure 13: The parameter b as a function of α

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-to-3 and 3-to-1 Pachner moves, we do believe it should be possible to extend our walker to 2-to-2 Pachner moves. We then wrote the equation that governs the behavior of the walker. It is highly non-linear, 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 coarse-graining 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 tae-bt2 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 power-law 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 multi-particle QCA and to higher dimensional simplicices complex, e.g. tetrahedra, where global curvature is no longer constant.


  • [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 and-or 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árquez-Martí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árquez-Martín, and Armando Pérez. From curved spacetime to spacetime-dependent 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 Bialynicki-Birula. 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 space-time. 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 quant-ph/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(5-6):551–574, 1996.
  • [23] Tullio Regge. General relativity without coordinates. Il Nuovo Cimento (1955-1965), 19(3):558–571, 1961.
  • [24] Linda Sansoni, Fabio Sciarrino, Giuseppe Vallone, Paolo Mataloni, Andrea Crespi, Roberta Ramponi, and Roberto Osellame. Two-particle bosonic-fermionic 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(11-12):987–1026, 2017.