From quantum cellular automata to quantum lattice gases

In this paper, in order to investigate natural transformations from discrete CA to QCA, we introduce a new formulation of finite cyclic QCA and generalized notion of partitioned QCA. According to the formulations, we demonstrate the condition of local transition functions, which induce a global transition of well-formed QCA. Following the results, extending a natural correspondence of classical cells and quantum cells to the correspondence of classical CA and QCA, we have the...

One-dimensional quantum cellular automata (QCA) consist in a line of identical, finite dimensional quantum systems. These evolve in discrete time steps according to a local, shift-invariant unitary evolution. By local we mean that no instantaneous long-range communication can occur. In order to define these over a Hilbert space we must restrict to a base of finite, yet unbounded configurations. We show that QCA always admit a two-layered block representation, and hence the in...

We propose a discrete spacetime formulation of quantum electrodynamics in one-dimension (a.k.a the Schwinger model) in terms of quantum cellular automata, i.e. translationally invariant circuits of local quantum gates. These have exact gauge covariance and a maximum speed of information propagation. In this picture, the interacting quantum field theory is defined as a "convergent" sequence of quantum cellular automata, parameterized by the spacetime lattice spacing---encompas...

A general class of discrete unitary models are described whose behavior in the continuum limit corresponds to a many-body Schrodinger equation. On a quantum computer, these models could be used to simulate quantum many-body systems with an exponential speedup over analogous simulations on classical computers. On a classical computer, these models give an explicitly unitary and local prescription for discretizing the Schrodinger equation. It is shown that models of this type c...

We describe a simple n-dimensional quantum cellular automaton (QCA) capable of simulating all others, in that the initial configuration and the forward evolution of any n-dimensional QCA can be encoded within the initial configuration of the intrinsically universal QCA. Several steps of the intrinsically universal QCA 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 o...

The one particle sector of the simplest one dimensional quantum lattice gas automaton has been observed to simulate both the (relativistic) Dirac and (nonrelativistic) Schroedinger equations, in different continuum limits. By analyzing the discrete analogues of plane waves in this sector we find conserved quantities corresponding to energy and momentum. We show that the Klein paradox obtains so that in some regimes the model must be considered to be relativistic and the negat...

Models of areas of physics in terms of cellular automata have become increasingly popular. Cellular automata (CAs) support the modeling of systems with discrete state component values and enforce the comprehensive specification of the dynamic evolution of such systems. Because many areas of physics can be described by starting with a specific Lagrangian, the idea to derive a cellular automaton directly from the Lagrangian (or similar construct, such as the Hamiltonian or acti...

Quantum walks on lattices can give rise to one-particle relativistic wave equations in the long-wavelength limit. In going to multiple particles, quantum cellular automata (QCA) are natural generalizations of quantum walks. In one spatial dimension, the quantum walk can be "promoted" to a QCA that, in the long-wavelength limit, gives rise to the Dirac quantum field theory (QFT) for noninteracting fermions. This QCA/QFT correspondence has both theoretical and practical applica...

Can we reduce Quantum Field Theory (QFT) to a quantum computation? Can physics be simulated by a quantum computer? Do we believe that a quantum field is ultimately made of a numerable set of quantum systems that are unitarily interacting? A positive answer to these questions corresponds to substituting QFT with a theory of quantum cellular automata (QCA), and the present work is examining this hypothesis. These investigations are part of a large research program on a "quantum...

We provide an introduction to Quantum Cellular Automata.