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 Sect. 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 Sect. 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 Sect. 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 Sect. 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 \(\varSigma = \{ \square \square , \square \blacksquare , \blacksquare \square , \blacksquare \blacksquare \} \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\rightarrow \varSigma \), 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) and (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.

Fig. 1.
figure 1

Representation of the framework of study.

Full size image

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\rightarrow \{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 \(\varSigma \) by

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

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 \(\widetilde{\psi }=\{ G_\varphi \psi \,|\,\varphi \in \mathbb {Z}^2\rightarrow \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)\) (\(\mod 2\)) fully characterizes \(\widetilde{\psi }\), since for all \(\psi \) and \(\psi '\), \(G_\varphi \psi =\psi '\) if and only if \(J=J'\). Fig. 2d shows the underlying J.

Fig. 2.
figure 2

Three physically equivalent spacetime diagrams, and their invariant.

Full size image

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 \)

$$\begin{aligned} G_{Z\varphi } \circ T=T\circ G_{\varphi } \end{aligned}$$
(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)\).

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 \),

$$\begin{aligned} G_{Z\varphi } \circ T_\bullet =T_{G_\varphi \bullet }\circ G_{\varphi } \end{aligned}$$
(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_\varphi \), 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 \(\varphi \), for all A, for all \(R_A\)–valid \(\psi \), for all x,

$$\begin{aligned} (G_{Z\varphi }(R_A \psi ))(x)&=(R_{G_{\varphi }A}(G_{\varphi }\psi ))(x) \end{aligned}$$

which, for our running example, translates into:

$$\begin{aligned} (X \otimes X)^{(Z\varphi )(x)}&(W_A (\psi ^+(x-1)\otimes \psi ^-(x+1)))\\&= W_{G_\varphi A} (X^{\varphi (x-1)}\psi ^+(x-1)\otimes X^{\varphi (x+1)}\psi ^-(x+1)) \end{aligned}$$

This is equivalent to

$$\begin{aligned} W_{G_\varphi A} = (X \otimes X)^{(Z\varphi )(x)} W_{A} (X^{-\varphi (x-1)} \otimes X^{-\varphi (x+1)}). \end{aligned}$$

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

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

with A transforming under \(G_\varphi \) as:

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

Indeed,

$$\begin{aligned} W_{(G_\varphi A) (x)}&=W (X^{A_r(x)+ (Z\varphi )(x)-\varphi (x-1)} \otimes X^{A_l(x)+ (Z\varphi )(x)-\varphi (x+1)})\\&=W(X \otimes X)^{(Z\varphi )(x)} (X^{A_r(x)} \otimes X^{A_l(x))}) (X^{-\varphi (x-1)} \otimes X^{-\varphi (x+1)})\\&=(X \otimes X)^{(Z\varphi )(x)} W_A (X^{-\varphi (x-1)} \otimes X^{-\varphi (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_\varphi \), we may again seek to characterize its invariant \(\widetilde{A}=\{ G_\varphi A\,|\,\varphi \in \mathbb {Z}^2\rightarrow \mathbb {Z}_2\}\) by means of some field F. This time, in order to do so, we introduce the light-like discrete derivatives

$$\begin{aligned} \varDelta _r A(x,t)&= A(x,t+1) - A(x-1,t) \\ \varDelta _l A(x,t)&= A(x,t+1) - A(x+1,t). \end{aligned}$$

Remark 1

(Gauge-field invariant). The bit field \(F(x,t) = \varDelta _r A_l(x,t) -\varDelta _l A_r(x,t)\) fully characterizes the invariant of the gauge field. More precisely, for any A and \(A'\), there exists \(\varphi \) such that \(G_\varphi 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

$$\begin{aligned} \varDelta _r \varphi = A'_r-A_r \qquad \text {and }\qquad \varDelta _l \varphi = A'_l-A_l. \end{aligned}$$
(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

$$\begin{aligned} (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)\\ \varDelta _r (A'_l-A_l)(x,t)&=\varDelta _l (A'_r-A_r)(x,t)\\ \varDelta _r A'_l- \varDelta _r A_l&=\varDelta _l A'_r- \varDelta _l A_r\\ \varDelta _l A_r-\varDelta _r A_l&=\varDelta _l A'_r-\varDelta _r A'_l\\ F(x,t)&= F'(x,t) \end{aligned}$$

which is our hypothesis. It follows that \(\varphi \) exists and so the converse holds. F fully characterizes \(\widetilde{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.

Fig. 3.
figure 3

The extended theory \(R_\bullet \) now depends on a 2–bits field A.

Full size image

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).

Fig. 4.
figure 4

Examples of the influence of F, \(\widetilde{S}_\bullet \) and \(S_\bullet \)

Full size image

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 \(\varphi \) such that \(G_\phi 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_{\varphi (.,t)} c(.,t)\), and have it evolve under \(T'\), so as to retrieve \(G_{\varphi (.,t+1)} 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_\bullet \) which takes \(c(.,t) = (\psi (.,t), A(.,t))\) and outputs \(\psi (.,t+1)\). Therefore, all we need is a rule \(S_\bullet \) that takes c(., t) and outputs \(A(.,t+1)\). The standard procedure indeed proceeds by decomposing T into \(R_\bullet \) and \(S_\bullet \). For such a T to verify (1), we just need \(S_\bullet \) to verify (2), for the same \(G_\varphi \) and Z that work for \(R_\bullet \).

The procedure goes in two steps. The first step is to prescribe a dynamics \(\widetilde{S}\) not over A, but over its invariant \(\widetilde{A}\), which in our case amounts to a dynamics over F. It may even be a J–dependent dynamics \(\widetilde{S}_\bullet \). Such a dynamics will be gauge-invariant by definition, since F and J are gauge-invariant. Thus the particular choice of \(\widetilde{S}_\bullet \) is only dictated by the phenomena that we wish to model. A simple choice, for instance, is to take \(\widetilde{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 \(\varDelta _r A_l(x,t)=\varDelta _l A_r(x,t)\). But at least this constraint over the dynamics of A is gauge-invariant. Figure 4(a), (b) and (c) 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_\bullet \) which induces the \(\widetilde{S}_\bullet \) that we had settled for in the first step. In our case, we need to fix an \(S_\bullet \) such that for all \((\psi ,A)\), if A is an \(S_\psi \)–valid spacetime diagram, then F is a \(\widetilde{S}_J\)–valid spacetime diagram, with F and J computed from A and \(\psi \).

It is crucial to understand that this time the choice of a particular \(S_\bullet \) 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_\varphi \) and Z. Let \(S_\bullet \) and \(S'_\bullet \) be two \(\psi \)–dependent inhomogeneous gauge-invariant theories upon A, with respect to the same \(G_\varphi \) and Z. If the two theories induce the same \(\widetilde{S}_\bullet \), then:

  1. 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. 2.

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

Proof

  1. 1.

    \(S_\bullet \) and \(S'_\bullet \) induce the same \(\widetilde{S}_\bullet \). Giving A an \(S_\bullet \)–valid field also gives F an \(\widetilde{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 \(\widetilde{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. 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 \(\widetilde{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.

\(\square \)

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 Figs. 4(a), (b) and (c) are physically equivalent, the same gauge-field invariant \(F=0\) is used. But Fig. 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 c). 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 Definition 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_\varphi \)–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 \(\widetilde{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], conservations 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.