From quantum cellular automata to quantum lattice gases

In this paper we present a quantization of Cellular Automata. Our formalism is based on a lattice of qudits, and an update rule consisting of local unitary operators that commute with their own lattice translations. One purpose of this model is to act as a theoretical model of quantum computation, similar to the quantum circuit model. It is also shown to be an appropriate abstraction for space-homogeneous quantum phenomena, such as quantum lattice gases, spin chains and other...

Quantum cellular automata (QCA) are models of quantum computation of particular interest from the point of view of quantum simulation. Quantum lattice gas automata (QLGA - equivalently partitioned quantum cellular automata) represent an interesting subclass of QCA. QLGA have been more deeply analyzed than QCA, whereas general QCA are likely to capture a wider range of quantum behavior. Discriminating between QLGA and QCA is therefore an important question. In spite of much pr...

Quantum cellular automata consist in arrays of identical finite-dimensional quantum systems, evolving in discrete-time steps by iterating a unitary operator G. Moreover the global evolution G is required to be causal (it propagates information at a bounded speed) and translation-invariant (it acts everywhere the same). Quantum cellular automata provide a model/architecture for distributed quantum computation. More generally, they encompass most of discrete-space discrete-time...

We continue our analysis of the physics of quantum lattice gas automata (QLGA). Previous work has been restricted to periodic or infinite lattices; simulation of more realistic physical situations requires finite sizes and non-periodic boundary conditions. Furthermore, envisioning a QLGA as a nanoscale computer architecture motivates consideration of inhomogeneities in the `substrate'; this translates into inhomogeneities in the local evolution rules. Concentrating on the one...

We present a quantum cellular automaton model in one space-dimension which has the Dirac equation as emergent. This model, a discrete-time and causal unitary evolution of a lattice of quantum systems, is derived from the assumptions of homogeneity, parity and time-reversal invariance. The comparison between the automaton and the Dirac evolutions is rigorously set as a discrimination problem between unitary channels. We derive an exact lower bound for the probability of error ...

Unitarity of the global evolution is an extremely stringent condition on finite state models in discrete spacetime. Quantum cellular automata, in particular, are tightly constrained. In previous work we proved a simple No-go Theorem which precludes nontrivial homogeneous evolution for linear quantum cellular automata. Here we carefully define general quantum cellular automata in order to investigate the possibility that there be nontrivial homogeneous unitary evolution when t...

Classical lattice gas automata effectively simulate physical processes such as diffusion and fluid flow (in certain parameter regimes) despite their simplicity at the microscale. Motivated by current interest in quantum computation we recently defined quantum lattice gas automata; in this paper we initiate a project to analyze which physical processes these models can effectively simulate. Studying the single particle sector of a one dimensional quantum lattice gas we find di...

Take a cellular automaton, consider that each configuration is a basis vector in some vector space, and linearize the global evolution function. If lucky, the r esult could actually make sense physically, as a valid quantum evolution; but do es it make sense as a quantum cellular automaton? That is the main question we a ddress in this paper. In every model with discrete time and space, two things ar e required in order to qualify as a cellular automaton: invariance by transl...

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

We consider a general class of discrete unitary dynamical models on the lattice. We show that generically such models give rise to a wavefunction satisfying a Schroedinger equation in the continuum limit, in any number of dimensions. There is a simple mathematical relationship between the mass of the Schroedinger particle and the eigenvalues of a unitary matrix describing the local evolution of the model. Second quantized versions of these unitary models can be defined, descr...