In this paper we study the space evolution in the Rule 54 reversible cellular automaton, which is a paradigmatic example of a deterministic interacting lattice gas. We show that the spatial translation of time configurations of the automaton is given in terms of local deterministic maps with the support that is small but bigger than that of the time evolution. The model is thus an example of space-time dual reversible cellular automaton, i.e. its dual is also (in general different) reversible cellular automaton. We provide two equivalent interpretations of the result; the first one relies on the dynamics of quasi-particles and follows from an exhaustive check of all the relevant time configurations, while the second one relies on purely algebraic considerations based on the circuit representation of the dynamics. Additionally, we use the properties of the local space evolution maps to provide an alternative derivation of the matrix product representation of multi-time correlation functions of local observables positioned at the same spatial coordinate.
In this paper we study the space evolution in the Rule 54 reversible cellular automaton, which is a paradigmatic example of a deterministic interacting lattice gas. We show that the spatial translation of time configurations of the automaton is given in terms of local deterministic maps with the support that is small but bigger than that of the time evolution. The model is thus an example of space-time dual reversible cellular automaton, i.e. its dual is also (in general different) reversible cellular automaton. We provide two equivalent interpretations of the result; the first one relies on the dynamics of quasi-particles and follows from an exhaustive check of all the relevant time configurations, while the second one relies on purely algebraic considerations based on the circuit representation of the dynamics. Additionally, we use the properties of the local space evolution maps to provide an alternative derivation of the matrix product representation of multi-time correlation functions of local observables positioned at the same spatial coordinate.
In this paper we study the space evolution in the Rule 54 reversible cellular automaton, which is a paradigmatic example of a deterministic interacting lattice gas. We show that the spatial translation of time configurations of the automaton is given in terms of local deterministic maps with the support that is small but bigger than that of the time evolution. The model is thus an example of space-time dual reversible cellular automaton, i.e. its dual is also (in general different) reversible cellular automaton. We provide two equivalent interpretations of the result; the first one relies on the dynamics of quasi-particles and follows from an exhaustive check of all the relevant time configurations, while the second one relies on purely algebraic considerations based on the circuit representation of the dynamics. Additionally, we use the properties of the local space evolution maps to provide an alternative derivation of the matrix product representation of multi-time correlation functions of local observables positioned at the same spatial coordinate.
Abstract For an interacting spatio-temporal lattice system we introduce a formal way of expressing multi-time correlation functions of local observables located at the same spatial point with a time state , i.e. a statistical distribution of configurations observed along a time lattice. Such a time state is defined with respect to a particular equilibrium state that is invariant under space and time translations. The concept is developed within the rule 54 reversible cellular automaton, for which we explicitly construct a matrix product form of the time state, with matrices that act on the three-dimensional auxiliary space. We use the matrix-product state to express equal-space time-dependent density-density correlation function, which, for special maximum-entropy values of equilibrium parameters, agrees with the previous results. Additionally, we obtain an explicit expression for the probabilities of observing all multi-time configurations, which enables us to study distributions of times between consecutive excitations and prove the absence of decoupling of timescales in the rule 54 model.
Abstract We introduce a pair of time-reversible models defined on the discrete space–time lattice with three states per site, specifically, a vacancy and a particle of two flavours (species). The local update rules reproduce the rule 54 reversible cellular automaton when only a single species of particles is present, and satisfy the requirements of flavour exchange ( C ), space-reversal ( P ), and time-reversal ( T ) symmetries. We find closed-form expressions for three local conserved charges and provide an explicit matrix product form of the grand canonical Gibbs states, which are identical for both models. For one of the models this family of Gibbs states seems to be a complete characterisation of equilibrium (i.e. space and time translation invariant) states, while for the other model we empirically find a sequence of local conserved charges, one for each support size larger than 2, hinting to its algebraic integrability. Finally, we numerically investigate the behaviour of spatio-temporal correlation functions of charge densities, and test the hydrodynamic prediction for the model with exactly three local charges. Surprisingly, the numerically observed ‘sound velocity’ does not match the hydrodynamic value. The deviations are either significant, or they decay extremely slowly with the simulation time, which leaves us with an open question for the mechanism of such a glassy behaviour in a deterministic locally interacting system.
We define quantum cellular automata as infinite quantum lattice systems with discrete time dynamics, such that the time step commutes with lattice translations and has strictly finite propagation speed. In contrast to earlier definitions this allows us to give an explicit characterization of all local rules generating such automata. The same local rules also generate the global time step for automata with periodic boundary conditions. Our main structure theorem asserts that any quantum cellular automaton is structurally reversible, i.e., that it can be obtained by applying two blockwise unitary operations in a generalized Margolus partitioning scheme. This implies that, in contrast to the classical case, the inverse of a nearest neighbor quantum cellular automaton is again a nearest neighbor automaton. We present several construction methods for quantum cellular automata, based on unitaries commuting with their translates, on the quantization of (arbitrary) reversible classical cellular automata, on quantum circuits, and on Clifford transformations with respect to a description of the single cells by finite Weyl systems. Moreover, we indicate how quantum random walks can be considered as special cases of cellular automata, namely by restricting a quantum lattice gas automaton with local particle number conservation to the single particle sector.
We propose and discuss two variants of kinetic particle models—cellular automata in 1 + 1 dimensions—that have some appeal due to their simplicity and intriguing properties, which could warrant further research and applications. The first model is a deterministic and reversible automaton describing two species of quasiparticles: stable massless matter particles moving with velocity ±1 and unstable standing (zero velocity) field particles. We discuss two distinct continuity equations for three conserved charges of the model. While the first two charges and the corresponding currents have support of three lattice sites and represent a lattice analogue of the conserved energy–momentum tensor, we find an additional conserved charge and current with support of nine sites, implying non-ergodic behaviour and potentially signalling integrability of the model with a highly nested R-matrix structure. The second model represents a quantum (or stochastic) deformation of a recently introduced and studied charged hardpoint lattice gas, where particles of different binary charge (±1) and binary velocity (±1) can nontrivially mix upon elastic collisional scattering. We show that while the unitary evolution rule of this model does not satisfy the full Yang–Baxter equation, it still satisfies an intriguing related identity which gives birth to an infinite set of local conserved operators, the so-called glider operators.
A natural architecture for nanoscale quantum computation is that of a quantum cellular automaton. Motivated by this observation, in this paper we begin an investigation of exactly unitary cellular automata. After proving that there can be no nontrivial, homogeneous, local, unitary, scalar cellular automaton in one dimension, we weaken the homogeneity condition and show that there are nontrivial, exactly unitary, partitioning cellular automata. We find a one parameter family of evolution rules which are best interpreted as those for a one particle quantum automaton. This model is naturally reformulated as a two component cellular automaton which we demonstrate to limit to the Dirac equation. We describe two generalizations of this automaton, the second of which, to multiple interacting particles, is the correct definition of a quantum lattice gas. KEY WORDS: quantum cellular automaton; quantum lattice gas; quantum computation. to appear in J. Stat. Phys.