Gauge-invariance is a fundamental concept in Physics -- known to provide mathematical justification 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, the notions of gauge-invariance and gauge-equivalence in Cellular Automata are formalized. A step-by-step gauging procedure to enforce this symmetry upon a given Cellular Automaton is developed, and three examples of gauge-invariant Cellular Automata are examined.

We extend the circuit model of quantum computation so that the wiring between gates is soft-coded within registers inside the gates. The addresses in these registers can be manipulated and put into superpositions. This aims at capturing indefinite causal orders and making their geometrical layout explicit: we express the quantum switch and the polarizing beam-splitter within the model. In this context, our main contribution is a full characterization of the anonymity constraints. Indeed, the names used as addresses should not matter beyond the wiring they describe; i.e., quantum evolutions should commute with “renamings.” We show that these quantum evolutions can still act non-trivially upon the names. We specify the structure of “nameblind” matrices.

It is well-known that cellular automata can be characterized as the set of translation-invariant continuous functions over a compact metric space; this point of view makes it easy to extend their definition from grids to Cayley graphs. Cayley graphs have a number of useful features: the ability to graphically represent finitely generated group elements and their relations; to name all vertices relative to an origin; and the fact that they have a well-defined notion of translation. We propose a notion of graphs, which preserves or generalizes these features. Whereas Cayley graphs are very regular, generalized Cayley graphs are arbitrary, although of a bounded degree. We extend cellular automata theory to these arbitrary, bounded degree, time-varying graphs. The obtained notion of cellular automata is stable under composition and under inversion.

We provide a computational definition of the notions of vector space and bilinear functions. We use this result to introduce a minimal language combining higher-order computation and linear algebra. This language extends the Lambda-calculus with the possibility to make arbitrary linear combinations of terms alpha.t + beta.u. We describe how to "execute" this language in terms of a few rewrite rules, and justify them through the two fundamental requirements that the language be a language of linear operators, and that it be higher-order. We mention the perspectives of this work in the field of quantum computation, whose circuits we show can be easily encoded in the calculus. Finally, we prove the confluence of the entire calculus. Comment: The complementary note "On the critical pairs of a rewrite system for vector spaces" is provided in the source files. Short version : "Linear-algebraic Lambda-calculus : higher-order and confluence", Proceedings of RTA 08, Hagenberg, July 2008. LNCS 5117, 17, (2008). Long version : LMCS

This paper introduces a simple formalism for dealing with deterministic, non-deterministic and stochastic cellular automata in an unified and composable manner. This formalism allows for local probabilistic correlations, a feature which is not presen

We give a one-dimensional quantum cellular automaton (QCA) capable of simulating all others. By this we mean that the initial configuration and the local transition rule of any onedimensional QCA can be encoded within the initial configuration of the universal QCA. Several steps of the universal QCA will then correspond to one step of the simulated QCA. The simulation preserves the topology in the sense that each cell of the simulated QCA is encoded as a group of adjacent cells in the universal QCA. The encoding is linear and hence does not carry any of the cost of the computation. We do this in two flavours: a weak one which requires an infinite but periodic initial configuration and a strong one which needs only a finite initial configuration.