# A Gauge-Invariant Reversible Cellular Automaton

Pablo Arrighi, Giuseppe Di Molfetta, Nathanaël Eon

► To cite this version:

Pablo Arrighi, Giuseppe Di Molfetta, Nathanaël Eon. A Gauge-Invariant Reversible Cellular Automaton. 24th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2018, Ghent, Belgium. pp.1-12, 10.1007/978-3-319-92675-9_1. hal-01824869

HAL Id: hal-01824869

https://inria.hal.science/hal-01824869

Submitted on 27 Jun 2018

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

Distributed under a Creative Commons Attribution 4.0 International License
# A Gauge-Invariant Reversible Cellular Automaton

Pablo Arrighi¹,², Giuseppe Di Molfetta¹,³, and Nathanaël Eon¹,⁴

¹ Aix-Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France

² IXXI, Lyon, France

³ Departamento de Física Terica and IFIC, Universidad de Valencia-CSIC,
Dr. Moliner 50, 46100-Burjassot, Spain

⁴ École Centrale, France

**Abstract.** Gauge-invariance is a fundamental concept in physics—known to provide mathematical justifications for the fundamental forces. In this paper, we provide discrete counterparts to the main gauge theoretical concepts, directly in terms of Cellular Automata. More precisely, we describe a step-by-step gauging procedure to enforce local symmetries upon a given Cellular Automaton. We apply it to a simple Reversible Cellular Automaton for concreteness. From a Computer Science perspective, discretized gauge theories may be of use in numerical analysis, quantum simulation, fault-tolerant (quantum) computation. From a mathematical perspective, discreteness provides a simple yet rigorous route straight to the core concepts.

## 1 Introduction

In Physics, symmetries act as guiding principles towards discovering the laws we put forward to model nature. Among them, Gauge symmetries are absolutely central, as they provide mathematical justifications for all four fundamental forces: electromagnetism and gravity (long range interactions), weak and strong forces (short range interactions) [1]. In this paper we express the key notions of gauge theories natively in Computer Science friendly, Discrete Mathematics terms—we do so in order to make them available to these disciplines, and in order to clarify its concepts. More precisely, we describe a discrete counterpart to the gauging procedure. I.e. we provide a step-by-step procedure to enforce local symmetries within Cellular Automata.

These methods may lead to natural, physics-inspired CA. More importantly, the fields of numerical analysis, quantum simulation, digital physics are constantly looking for discrete schemes that simulate known physics [2]. Quite often, these discrete schemes seek to retain the symmetries of the simulated physics; whether in order to justify the discrete scheme as legitimate, or in order to do the Monte Carlo-counting right [3]. Generally speaking, since gauge symmetries are essential in physics, having a discrete counterpart of it may also be.

Interestingly, this way of enforcing local redundancies also bears some resemblances with error-correction, and echoes the fascinating question of noise resistance within spatially-distributed models of computation [4,5], as was pointed out in the context of quantum computation in [6,7].

Although we authors come from the field of quantum computation and simulation, the formalism we use is totally devoid of any quantum theory, least action principle, nor
Lagrangian. The notions here are directly formulated in terms of the discrete dynamical system. We believe that this provides a uniquely direct route to the root concepts. This discrete mathematics framework makes the presentation original, and simpler. But it also allows for more rigorous definitions, that in turn allow us to prove some essential consistency lemmas that are usually left aside. Our running example provides what seems to be the simplest non-trivial Gauge theory so far and illustrates the key concepts. Given the fame of Gauge theories, we think this may be a remarkable pedagogical asset.

The paper is organized as follows. In Sec. 2 we introduce the notions of local transformations which define the desired symmetry, and of gauge-invariance which captures the (non-)compliance of a given Cellular Automaton (CA) with the desired symmetry. In Sec. 3 we show how a non-gauge-invariant CA can be made gauge-invariant, at the heavy cost of becoming spacetime dependent upon an external parameter, referred to as the gauge field. This new parameter not only implements the symmetry—it leads to new behaviours for the CA. In Sec. 4 the gauge field gets internalized into the configuration space, and a whole family of homogeneous gauge-invariant CA is obtained, leading us to the notions of gauge-fixing and gauge-constraining. A simple Reversible Cellular Automaton (RCA) is used to illustrate each concepts, throughout the paper. In Sec. 5 we summarize, provide related works and perspectives.

## 2 The gauge-invariance requirements

*Theory to be gauged.* In this paper ‘theories’ stand for CA. As our running example, we pick possibly the simplest and most natural physics-like RCA: one that has particles moving left and right. More precisely, each cell of the RCA has a state in $\Sigma = \{\Box, \Box, \Box, \Box\} \cong \{00, 01, 10, 11\}$. Its dynamics $R$ is defined through a local rule $\lambda_R$ which computes the next state of a cell from that of its left and right neighbours, i.e. $\psi(x, t+1) = \lambda_R(\psi(x-1, t), \psi(x+1, t))$, with $\psi(x, t)$ the state of cell $x$ at time $t$. A spacetime diagram $\psi: \mathbb{Z}^2 \to \Sigma$, is said to be $R$-valid if and only if it is produced by applying $\lambda_R$, see for instance Fig-1a. We also say that it is ‘a solution’. We use the shorthand notations $(R\psi)(x, t)$ for $\psi(x, t+1)$, $\psi(x)$ for $\psi(x, 0)$, $\psi(., t)$ for the function mapping $x$ into $\psi(x, t)$.

In our running example, the $R$ that we consider can be expressed in the block circuit form of Fig-1b, with $W$ the gate that swaps two bits:

$$ 
\begin{aligned}
\psi(x, t+1) &= \lambda_R(\psi(x-1, t), \psi(x+1, t)) \\
&= W(\psi^+(x-1, t) \otimes \psi^-(x+1, t)) \\
&= \psi^-(x+1, t) \otimes \psi^+(x-1, t)
\end{aligned}
$$

with $\psi(x, t) = (\psi^-(x) \otimes \psi^+(x))$. RCA presented in such a block circuit form are often referred to as (Margolus–)Partitioned CA in Computer Science vocabulary[8], or as Lattice-gas automata in Physics[9]. This theory is *to-be-gauged*. This means that although it may have a global symmetry (here the CA has global black/white-symmetry, see Fig-2 (a) – (b)), it lacks a certain local symmetry (here no deterministic CA describes Fig-2 (c)). The aim of the so-called *gauging procedure* is to extend a theory order so as to enforce a given local symmetry.
<figure><img src="image_2.png" /><figcaption>(a) An R-valid spacetime diagram with two particles moving in opposite directions</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>(b) Framework of study</figcaption></figure>

<caption>Fig. 1: Representation of the framework of study.</caption>

*Local transformation and its invariant.* In our running example we will be interested in enforcing a *local* black/white-symmetry. We formalize this by giving ourselves a bit field $\varphi: \mathbb{Z}^2 \to \{0, 1\} \cong \mathbb{Z}_2$ that specifies, at each spacetime point, whether the symmetry is to be applied. In other words, the action of the $\mathbb{Z}_2$ group at $(x, t)$ gets represented upon $\Sigma$ by

$$G_{\varphi}(x, t) = (X \otimes X)^{\varphi(x, t)}$$

with $X$ the NOT gate. Then, an entire spacetime diagram $\psi$ transforms into an entire spacetime diagram $G_{\varphi}\psi$ via $(G_{\varphi}\psi)(x, t) = G_{\varphi}(x, t)\psi(x, t)$. This is the symmetry we are trying to enforce. Thus, whenever two spacetime diagrams are related by a transformation $G_{\varphi}$ for some $\varphi$, they are understood as *physically equivalent*. For instance, in Fig-2, the first three diagrams are physically equivalent with respect to the symmetry. They all represent this one particle moving right, which can be understood as an invariant of the symmetry. Given a spacetime diagram $\psi$, we write $\tilde{\psi} = \{G_{\varphi}\psi | \varphi \in \mathbb{Z}^2 \to \mathbb{Z}_2\}$ for its *invariant*, (physical) equivalence class. In the case of our field $\psi$, the bit field $J(x, t) = \psi^+(x, t) - \psi^-(x, t) (\text{mod } 2)$ fully characterizes $\tilde{\psi}$, since for all $\psi$ and $\psi'$, $G_{\varphi}\psi = \psi'$ if and only if $J = J'$. Fig-2d shows the underlying $J$.

*The gauge invariance condition.* Given $\psi(., t)$ and $(G_{\varphi}\psi)(., t)$ two physically equivalent inputs, it should be the case that our theory produces two physically equivalent outputs $\psi(., t+1)$ and $(G_{\varphi}\psi)(., t+1)$. This leads to the following definition.

**Definition 1 (Gauge-invariance).** A theory $T$ is gauge-invariant if and only if there exists $Z$ a theory such that for all $\varphi$

$$G_{Z\varphi} \circ T = T \circ G_{\varphi} \qquad (1)$$

The above-defined RCA fails to meet this requirement. An example of this failure is provided by Fig-2, which shows three physically equivalent spacetime diagrams, i.e. that are $G_{\varphi}$-related. Clearly the first two are R-valid, but the third one is not, as can be seen from looking at $\psi(x, t+1)$.
<figure><img src="image_4.png" /><figcaption>(a) R-valid spacetime diagram showing a particle moving right.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(c) Not an R-valid spacetime diagram after applying the local symmetry $G_\varphi$ with space-dependent $\varphi$.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(b) Still an R-valid spacetime diagram after applying the global symmetry $G_\varphi$ with $\varphi$ constant equal to one.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(d) The J-field that characterizes the invariant under $G_\varphi$, common to the other three spacetime diagrams.</figcaption></figure>

<caption>Fig. 2: Three physically equivalent spacetime diagrams, and their invariant.</caption>

Indeed, on the one hand cell $\psi(x, t + 1)$ of Fig-2c needs have different-color subcells, as it is a $G_\varphi(x, t + 1)$ of that of the other diagrams, and $G_\varphi(x, t + 1)$ conserves same-colorness. But, on the other hand, cell $\psi(x, t + 1)$ of Fig-2c needs have same-color subcells, as it is produced by a W which is fed with same-color subcells—due to the particular choice of $\varphi(x-1, t)$ and $\varphi(x+1, t)$—and since W conserves same-colorness. This cannot be fixed with a better choice of $\varphi(x, t + 1)$. Therefore, our previously defined RCA fails to verify the gauge-invariance condition.

The gauging procedure proceeds by extending R into an inhomogeneous dynamics.

### 3 The gauge field

*Introducing the gauge field.* In order to obtain the gauge-invariance condition (1), the standard procedure is to make the theory R into an inhomogeneous theory $R_\bullet$, and aim at inhomogeneous gauge-invariance:

**Definition 2 (Inhomogeneous gauge-invariance).** A theory $T_\bullet$ is inhomogeneous gauge-invariant if and only if there exists Z a theory such that for all Z-valid $\varphi$,

$$G_{Z\varphi} \circ T_{\bullet} = T_{G_{\varphi}\bullet} \circ G_{\varphi} \qquad (2)$$

The spacetime diagram A, which specifies the spacetime dependency of R, is referred to as the gauge field, or Ehresmann connection in mathematics. Back to our running
example, we are thus looking for an extension of $R$ into an $R_A$ and of $G_\phi$, so that it acts on both $\psi$ and $A$, in order to achieve condition (2). Developing, we need that there exists $Z$ such that for all $Z$-valid $\phi$, for all $A$, for all $R_A$-valid $\psi$, for all $x$,

$$ (G_{Z\phi}(R_A\psi))(x) = (R_{G_\phi A}(G_\phi\psi))(x) $$

which, for our running example, translates into:

$$ (X \otimes X)^{(Z\phi)(x)} (W_A(\psi^+(x-1) \otimes \psi^-(x+1))) \\ = W_{G_\phi A}(X^{\phi(x-1)}\psi^+(x-1) \otimes X^{\phi(x+1)}\psi^-(x+1)) $$

This is equivalent to:

$$ W_{G_\phi A} = (X \otimes X)^{(Z\phi)(x)} W_A(X^{-\phi(x-1)} \otimes X^{-\phi(x+1)}). $$

A somewhat minimal choice verifying the above condition is to take $A: \mathbb{Z}^2 \to \mathbb{Z}_2^2$ a 2-bits field, and

$$ W_A = W(X^{A_r} \otimes X^{A_l}), $$

with $A$ transforming under $G_\phi$ as:

$$ A(x) = \begin{pmatrix} A_r(x) \\ A_l(x) \end{pmatrix} \mapsto \begin{pmatrix} A_r(x) + (Z\phi)(x) - \phi(x-1) \\ A_l(x) + (Z\phi)(x) - \phi(x+1) \end{pmatrix} = (G_\phi A)(x) $$

Indeed,

$$ \begin{aligned} W_{(G_\phi A)(x)} &= W(X^{A_r(x)+(Z\phi)(x)-\phi(x-1)} \otimes X^{A_l(x)+(Z\phi)(x)-\phi(x+1)}) \\ &= W(X \otimes X)^{(Z\phi)(x)} (X^{A_r(x)} \otimes X^{A_l(x)}) (X^{-\phi(x-1)} \otimes X^{-\phi(x+1)}) \\ &= (X \otimes X)^{(Z\phi)(x)} W_A(X^{-\phi(x-1)} \otimes X^{-\phi(x+1)}). \end{aligned} $$

It follows that the induced $R_\bullet$ verifies the inhomogeneous gauge-invariance condition (2). This procedure is reminiscent of the route physics follows to account for a local phase transformation on the state vector $\psi(x, t)$, which leads to the modern formulation of electrodynamics, with $A(x, t)$ playing the role of the electromagnetic potential.

**Invariant of the gauge field.** Since $A$ also transforms under $G_\phi$, we may again seek to characterize its invariant $\tilde{A} = \{G_\phi A | \phi \in \mathbb{Z}^2 \to \mathbb{Z}_2\}$ by means of some field $F$. This time, in order to do so, we introduce the light-like discrete derivatives

$$ \Delta_r A(x, t) = A(x, t+1) - A(x-1, t) $$

$$ \Delta_l A(x, t) = A(x, t+1) - A(x+1, t). $$

**Remark 1 (Gauge-field invariant).** The bit field $F(x, t) = \Delta_r A_l(x, t) - \Delta_l A_r(x, t)$ fully characterizes the invariant of the gauge field. More precisely, for any $A$ and $A'$, there exists $\phi$ such that $G_\phi A = A'$ is equivalent to $F = F'$.
*Proof.* A lengthy but easy computation shows that, given any $A$ and $A'$, $G_\varphi A = A'$ entails that $F = F'$. The converse is harder to prove, but also true. Indeed, suppose that we are given $A$ and $A'$ such that $F = F'$. We want to construct a $\varphi$ such that $G_\varphi A = A'$, i.e. such that we have both

$$ \Delta_r \varphi = A'_r - A_r \quad \text{and} \quad \Delta_l \varphi = A'_l - A_l. \qquad (3) $$

Clearly, starting from an initial spacelike configuration $\varphi$, the requirements (3) fix the rest of $\varphi$ across spacetime. Unless they conflict. This could happen every time we close up a square. Starting from $\varphi(x, t)$, say, the requirements (3) provide two prescriptions for $\varphi(x, t+2)$, namely $\varphi(x, t) + (A'_l - A_l)(x-1, t) + (A'_r - A_r)(x, t+1)$ via the left-then-right path, and $\varphi(x, t) + (A'_r - A_r)(x+1, t) + (A'_l - A_l)(x, t+1)$ via the right-then-left path. These need be equal, i.e we need

$$ (A'_l - A_l)(x, t+1) - (A'_l - A_l)(x-1, t) = (A'_r - A_r)(x, t+1) - (A'_r - A_r)(x+1, t) $$

$$ \Delta_r (A'_l - A_l)(x, t) = \Delta_l (A'_r - A_r)(x, t) $$

$$ \Delta_r A'_l - \Delta_r A_l = \Delta_l A'_r - \Delta_l A_r $$

$$ \Delta_l A_r - \Delta_r A_l = \Delta_l A'_r - \Delta_r A'_l $$

$$ F(x, t) = F'(x, t) $$

which is our hypothesis. It follows that $\varphi$ exists and so the converse holds. $F$ fully characterizes $\tilde{A}$. $\square$

The role played by this discrete bit-field $F$ is analogous to that of the electromagnetic tensor, a differential 2-form, which is the exterior derivative of the electromagnetic potential $A(x, t)$ and whose derivatives are prescribed by the Maxwell equations.

<figure><img src="image_8.png" /><figcaption>Fig. 3: The extended theory $R_\bullet$ now depends on a 2-bits field $A$.</figcaption></figure>

*Gauge field physics.* It is crucial to understand that, even though $A$ was introduced just to enforce a symmetry, i.e. to make sure that physically equivalent states are mapped into physically equivalent states... this newly introduced $A$ is also capable of a range of other things, i.e. it produces new physics. For instance, Fig-4 shows how, starting from the same initial conditions for $J$, but choosing different initial conditions for $A$, can lead to rather different $R_A$-valid spacetime diagrams—which may (Fig-4c) or may
not be (Fig-4d) related by a $G_{\phi}$.

At this stage we can have two points of view upon A. Either A is seen as an independent field, which could be to some extent tuned by the user/experimentalist (e.g. in the case of the electromagnetism, one can physically engineer each component of the electromagnetic tensor, $F$, namely the electric and the magnetic field). Or we must extend the configuration space so as to account for A, as suggested by Fig-3. Of course if we do that we need to provide a dynamics for A, i.e. we need to look for a theory $T$ upon $c(x, t) = (\psi(x, t), A(x, t))$, which still verifies the gauge-invariance condition (1).

<figure><img src="image_9.png" /><figcaption>(a) A spacetime diagram with $S_{\psi} = I$ ($A(x, t+1) = A_{r}(x+1, t) \otimes A_{l}(x-1, t)$) and thus $\tilde{S}_{J} = I$, initialized at $F = 0$.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(b) A spacetime diagram with $S_{\psi} = (X \otimes X)$ inducing $\tilde{S}_{J} = I$ again, initialized at $F = 0$. Observe that the $J$ field is as in (a).</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>(c) A spacetime diagram with $S_{\psi} = I$ and $\tilde{S}_{J} = I$, initialized at $F = 0$ with an initial condition on A differing from that of subfigure (a). Observe that the $J$ field is as in (a).</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>(d) A spacetime diagram with $A(x, t+1) = A(x, t)$ and $\tilde{S}_{J} = I$, initialized with $F = 1$ at position $x$ and $F = 0$ everywhere else. Observe that the $J$ field differs from that of (a).</figcaption></figure>

<caption>Fig. 4: Examples of the influence of $F$, $\tilde{S}_{\bullet}$ and $S_{\bullet}$.</caption>

*Gauge equivalence of two theories.* We need to keep in mind that by its very nature, such a $T$ cannot be unique—in the sense that for every candidate $T$ there will be several other physically equivalent local rules. This is because, as $T$ fully implements the local
symmetry, it is inherently redundant, and thus equivalent to other theories up to this
redundancy.

**Definition 3 (Physically equivalent theories).** *Two gauge-invariant theories T and T' are physically equivalent theories if and only if for any T–valid spacetime diagram c, there exists φ such that G<sub>φ</sub>c is a T'–valid spacetime diagram, and reciprocally.*

This definition ensures that given theory *T* and some input configuration *c*(., *t*), we can always encode the input as *G*<sub>ϕ(.,t)</sub>*c*(., *t*), and have it evolve under *T*', so as to retrieve *G*<sub>ϕ(.,t+1)</sub>*c*(., *t* + 1), which is physically equivalent to *c*(., *t* + 1). We will now build candidate theories *T* and *T*′ by following the standard steps of the gauging procedure.

# 4 Gauge field dynamics

*Dynamics of the invariant of the gauge field.* The dynamics *T* we want to build takes *c*(*.,* *t*) as input and outputs *c*(*.,* *t* + 1). However, we already have *R*<sub>•</sub> which takes *c*(*.,* *t*) = (*ψ*(*.,* *t*), *A*(*.,* *t*)) and outputs *ψ*(*.,* *t* + 1). Therefore, all we need is a rule *S*<sub>•</sub> that takes *c*(*.,* *t*) and outputs *A*(*.,* *t* + 1). The standard procedure indeed proceeds by decomposing *T* into *R*<sub>•</sub> and *S*<sub>•</sub>. For such a *T* to verify (1), we just need *S*<sub>•</sub> to verify (2), for the same *G*<sub>ϕ</sub> and *Z* that work for *R*<sub>•</sub>.

The procedure goes in two steps. The first step is to prescribe a dynamics $\tilde{S}$ not over $A$, but over its invariant $\tilde{A}$, which in our case amounts to a dynamics over $F$. It may even be a $J$-dependent dynamics $\tilde{S}_{\bullet}$. Such a dynamics will be gauge-invariant by definition, since $F$ and $J$ are gauge-invariant. Thus the particular choice of $\tilde{S}_{\bullet}$ is only dictated by the phenomena that we wish to model. A simple choice, for instance, is to take $\tilde{S}$ to be the identity. Then, if initially we had $F=0$ initially, this will remain the case. Beware that this does not mean that the behaviour of the underlying $A$ will be trivial. In fact it will remain largely undetermined, as $F=0$ just means $\Delta_r A_l(x,t) = \Delta_l A_r(x,t)$. But at least this constraint over the dynamics of $A$ is gauge-invariant. Fig-4a, 4b,4c give examples of different $A$ that have $F=0$—illustrating how many different gauge fields can arise from the same prescription for the invariant. Thus, this first step does not suffice to prescribe $S_{\bullet}$. Hence the need for a second step called gauge-fixing.

*Gauge-fixing : completing the dynamics.* Gauge-fixing means choosing an actual *S*•
which induces the *S*• that we had settled for in the first step. In our case, we need to
fix an *S*• such that for all (*ψ*, *A*), if *A* is an *S*ψ–valid spacetime diagram, then *F* is a
*S*J–valid spacetime diagram, with *F* and *J* computed from *A* and ψ.
It is crucial to understand that this time the choice of a particular *S*• is not dictated by
the physics, but by mere convenience. This assertion relies on the following proposition.

**Proposition 1 (Gauge-fixing soundness).** Let $R_{\bullet}$ be an $A$-dependent inhomogeneous theory upon $\psi$, with respect to a given $G_{\phi}$ and $Z$. Let $S_{\bullet}$ and $S'_{\bullet}$ be two $\psi$-dependent inhomogeneous gauge-invariant theories upon $A$, with respect to the same $G_{\phi}$ and $Z$. If the two theories induce the same $\tilde{S}_{\bullet}$, then:
1. For any $A$ an $S_\psi$-valid spacetime diagram, there exists $\varphi$ such that $A'$ is an $S'_{\psi'}$-valid spacetime diagram, with $(A', \psi') = G_\varphi(A, \psi)$.

2. The theories $T = R_\bullet \wedge S_\bullet$ and $T' = R_\bullet \wedge S'_\bullet$ are physically equivalent theories.

*Proof.* 1. $S_\bullet$ and $S'_\bullet$ induce the same $\tilde{S}_\bullet$. Giving $A$ an $S_\bullet$-valid field also gives $F$ an $\tilde{S}_\bullet$-valid field. We can then build $A'$ an $S'_\bullet$-valid field, inducing the same $F$. This is done using an initial condition for $A'$ which gives $F(., 0)$. When evolving with $S'_\bullet$, $F$ will evolve with $\tilde{S}'_A$. Using remark-1 which says that given $A$ and $A'$ inducing the same $F$, there exists $\varphi$ such that $A' = G_\varphi A$, we prove Fact 1 by applying such a $G_\varphi$ to $c = (\psi, A)$. Thus we have built a $\varphi$ such that $A'$ is an $S'_{\psi'}$-valid spacetime diagram with $(\psi', A') = G_\varphi(\psi, A)$.

2. We can now prove Fact 2. Given $c = (\psi, A)$ a $T$-valid spacetime diagram, consider $A$ on its own. $A$ is an $S_\psi$-valid spacetime diagram. But since $S_\bullet$ and $S'_\bullet$ both implement $\tilde{S}_\bullet$, there exists $\varphi$ such that $A' = G_\varphi A$ is an $S'_{G_\varphi\psi}$-valid spacetime diagram (Fact 1). Apply this $G_\varphi$ to the whole of $c = (\psi, A)$. This yields some $c' = (\psi', A')$. Is $c'$ a $T'$-valid spacetime diagram? Yes, because: $A'$ is an $S'_{\psi'}$-valid spacetime diagram by construction and since $\psi$ is an $R_A$-valid spacetime diagram, $\psi'$ is an $R_{A'}$-valid spacetime diagram due to $R_\bullet$ gauge-invariance. Hence $T$ and $T'$ are physically equivalent theories.

☐

Hence, different dynamics $S_\bullet$ can be used to describe the same physics, and choosing between them is a matter of convenience. To illustrate this point, we refer again to Fig-4. In this figure, we can see that sub-figures 4a, 4b, 4c are physically equivalent, the same gauge-field invariant $F=0$ is used. But sub-figure 4b shows that we do have a degree of freedom on $S_\psi$.

*Gauge-constraining : removing redundancies.* Now that we fully described our gauge-invariant theory $T$, we find ourselves confronted with its inherent redundancies—the ones arising precisely from the gauge-symmetry we just managed to implement. Indeed, any two $G_\varphi$-related initial configurations, lead to physically equivalent solutions—as shown in Fig-(4a and 4c). At this stage, and only now that the symmetry has been implemented, we may wish to remove its induced redundancies by suitably restricting the space of configurations. This is usually done by imposing some local constraints directly on the field $c(x, t)$, referred to as gauge-constraining. However we must keep in mind that constraining $c(x, t)$ could potentially restrict the set of physical solutions available. One must therefore check that a gauge-invariant theory $T$, and its gauge-constrained version $T''$, remain physically equivalent theories in the sense of Def. 3.

# 5 Conclusion

*Summary.* The paper followed a discrete counterpart to the gauging procedure, which aims to enforce a local symmetry that was judged missing in some physical theory. Here, theories were captured as Cellular Automata (CA), and local symmetries as local transformations $G_\varphi$ of the spacetime diagrams $c$ of these CA. Gauge-invariance was
formulated as a concrete condition (1), which directly translates into a local constraint upon the local rule of the theory. It was shown how, starting from a homogeneous non-gauge-invariant theory $R$ over configurations $\psi(., t)$, one gets to an $A(x, t)$-dependent inhomogeneous gauge-invariant theory $R_\bullet$, and completes this with a $\psi(x, t)$-dependent gauge-invariant theory $S_\bullet$ over configurations $A(., t)$, in order to finally obtain a homogeneous gauge-invariant theory $T = R_\bullet \cup S_\bullet$ over configurations $c(., t) = (\psi(., t), A(., t))$. The acquired gauge-symmetry then leads to equivalent theories $T'$—equivalent up to the symmetry. A way to go from a $T$ to some equivalent $T'$ is to replace $S_\bullet$ by some $S'_\bullet$ whose spacetime diagrams are $G_\phi$-related—this is called gauge-fixing. Theory equivalence and gauge-fixing were formalized, the fact that the latter respects the former was proven. Moreover, one can sometimes find an equivalent theory on a reduced configuration space $\tilde{c}(., t)$, which can be understood as a canonical representant of $c(., t)$ under the symmetry—this is called gauge-constraining.

*Motivations*. These were twofold: (i) Porting the gauge theoretical tools and concepts to Computer Science, as methods for constructing nature-inspired CA; providing more accurate schemes for numerical analysis; providing quantum simulation algorithms; making spatially distributed (quantum) computation immune to local errors. (ii) Clarifying the gauge theoretical concepts through the simplicity and rigor brought by Discrete Mathematics; providing the most direct route to its core, i.e. without reference to quantum mechanics and least action principle.

*Related works.* A number of discrete counterparts to physics symmetries have been reformulated in terms of CA, including reversibility, Lorentz-covariance[10], conservation laws and invariants[11], but no gauge symmetry. To our knowledge the closest work is the colour-blind CA construction[12] which implements a global colour symmetry without porting it to the local scale. However gauge symmetries have been implemented in the one-particle sector of Quantum CA, a.k.a for Quantum Walks. Indeed, one of the authors had followed a similar procedure in order to introduce the electromagnetic gauge field [13], and that of the weak and strong interactions [14,15]. This again was done in the very fabric of the Quantum Walk and the associated symmetry was therefore an intrinsic property of the Quantum Walk. But the gauge field would remain continuous, and seen as an external field.

There are, of course, numerous other approaches to space-discretized gauge theories, the main ones being Lattice Gauge Theory[16] and the Quantum Link Model[17], which were phrased in terms of Quantum Computation-friendly terms through Tensor Networks[18] and can be linked in a unified framework[19]. Discretized gauge-theories have also arisen from Ising models[19,20]. All of these approaches, however, begin with a well-known continuous gauge theory which is then space-discretized—time is usually kept continuous. An interesting attempt to quantum discretize gauge theories in discrete time, on a general simplicial complex can be found in [21].

*Perspectives.* We believe that the hereby developed methodology is ready to be applied to Quantum CA (QCA) [22], so as to obtain discretized free and interacting Quantum Field Theories [23]. Such discretized theories are of interest in Physics especially in non-perturbative theories [24], but they also represent practical assets as quantum simulation algorithms, i.e. numerical schemes that run on Quantum Computers to efficiently
simulate interacting fundamental particles—a task which is beyond the capabilities of classical computers. This is ongoing work.

# 6 Acknowledgements

The authors would like to thank Cédric Bény, Thomas Krajewski, Terry Farrelly and Pablo Arnault, for very instructive conversations about gauge theories. This work was partially supported by the CNRS PEPS JCJC GQNET and the CNRS PEPS Défi In-FinitTI “Lattice Quantum Simulation Theory” LAQUST.

# References

1. Quigg, C.: Gauge theories of the strong, weak, and electromagnetic interactions. Princeton University Press (2013)

2. Georgescu, I., Ashhab, S., Nori, F.: Quantum simulation. Reviews of Modern Physics **86**(1) (2014) 153

3. Hastings, W.K.: Monte carlo sampling methods using markov chains and their applications. Biometrika **57**(1) (1970) 97–109

4. Harao, M., Noguchi, S.: Fault tolerant cellular automata. Journal of computer and system sciences **11**(2) (1975) 171–185

5. Toom, A.: Cellular automata with errors: Problems for students of probability. Topics in Contemporary Probability and Its Applications (1995) 117–157

6. Kitaev, A.Y.: Fault-tolerant quantum computation by anyons. Annals of Physics **303**(1) (2003) 2–30

7. Nayak, C., Simon, S.H., Stern, A., Freedman, M., Sarma, S.D.: Non-abelian anyons and topological quantum computation. Reviews of Modern Physics **80**(3) (2008) 1083

8. Toffoli, T., Margolus, N.: Cellular Automata Machine – A new Environment for Modelling. MIT Press, Cambridge MA (1987)

9. Wolf-Gladrow, D.A.: Lattice-gas cellular automata and lattice Boltzmann models: an introduction. Springer (2004)

10. Arrighi, P., Facchini, S., Forets, M.: Discrete lorentz covariance for quantum walks and quantum cellular automata. New Journal of Physics **16**(9) (2014) 093007

11. Formenti, E., Kari, J., Taati, S.: On the hierarchy of conservation laws in a cellular automaton. Natural Computing **10**(4) (2011) 1275–1294

12. Salo, V., Trm, I.: Color blind cellular automata. Lecture Notes in Computer Science (2013) 139154

13. Di Molfetta, G., Brachet, M., Debbasch, F.: Quantum walks in artificial electric and gravitational fields. Physica A: Statistical Mechanics and its Applications **397** (2014) 157–168

14. Arnault, P., Di Molfetta, G., Brachet, M., Debbasch, F.: Quantum walks and non-abelian discrete gauge theory. Physical Review A **94**(1) (2016) 012335

15. Di Molfetta, G., Pérez, A.: Quantum walks as simulators of neutrino oscillations in a vacuum and matter. New Journal of Physics **18**(10) (2016) 103038

16. Willson, S.J.: Computing fractal dimensions for additive cellular automata. Physica D **24** (1987) 190–206

17. Chandrasekharan, S., Wiese, U.J.: Quantum link models: A discrete approach to gauge theories. Nuclear Physics B **492**(1-2) (1997) 455–471

18. Rico, E., Pichler, T., Dalmonte, M., Zoller, P., Montangero, S.: Tensor networks for lattice gauge theories and atomic quantum simulation. Physical Review Letters **112**(20) (2014) 201601
19. Silvi, P., Rico, E., Calarco, T., Montangero, S.: Lattice gauge tensor networks. New Journal of Physics **16**(10) (Oct 2014) 103015

20. Wegner, F.J.: Duality in generalized ising models and phase transitions without local order parameters. Journal of Mathematical Physics **12**(10) (Oct 1971) 22592272

21. Kornyak, V.V.: Discrete dynamics: gauge invariance and quantization. In: International Workshop on Computer Algebra in Scientific Computing, Springer (2009) 180–194

22. Arrighi, P., Nesme, V., Werner, R.: One-dimensional quantum cellular automata over finite, unbounded configurations. In: International Conference on Language and Automata Theory and Applications, Springer (2008) 64–75

23. Itzykson, C., Zuber, J.B.: Quantum field theory. Courier Corporation (2006)

24. Strocchi, F.: An introduction to non-perturbative foundations of quantum field theory. Volume 158. Oxford University Press (2013)