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 prior work, classifying which QCA are QLGA has remained an open problem. In the present paper we establish necessary and sufficient conditions for unbounded, finite QCA (finitely many active cells in a quiescent background) to be QLGA. We define a local condition that classifies those QCA that are QLGA, and we show that there are QCA that are not QLGA. We use a number of tools from functional analysis of separable Hilbert spaces and representation theory of associative algebras that enable us to treat QCA on finite but unbounded configurations in full detail.
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 prior work, classifying which QCA are QLGA has remained an open problem. In the present paper we establish necessary and sufficient conditions for unbounded, finite QCA (finitely many active cells in a quiescent background) to be QLGA. We define a local condition that classifies those QCA that are QLGA, and we show that there are QCA that are not QLGA. We use a number of tools from functional analysis of separable Hilbert spaces and representation theory of associative algebras that enable us to treat QCA on finite but unbounded configurations in full detail.
Quantum cellular automata (QCA) constitute space and time homogeneous discrete models for quantum field theories (QFTs). Although QFTs are defined without reference to particles, computations are done in terms of Feynman diagrams, which are explicitly interpreted in terms of interacting particles. Similarly, the easiest QCA to construct are quantum lattice gas automata (QLGA). A natural question then is, which QCA are not QLGA? Here we construct a nontrivial example of such a QCA; it provides a simple model in 1+1 dimensions with no particle interpretation at the scale where the QCA dynamics are homogeneous.
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.
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.
Over an arbitrary commutative ring R, we develop a theory of quantum cellular automata. We then use algebraic K-theory to construct a space Q(X) of quantum cellular automata (QCA) on a given metric space X. In most cases of interest, π0Q(X) classifies QCA up to quantum circuits and stabilization. Notably, the QCA spaces are related by homotopy equivalences Q(∗)≃ΩnQ(Zn) for all n, which shows that the classification of QCA on Euclidean lattices is given by an Ω-spectrum indexed by the dimension n. As a corollary, we also obtain a non-connective delooping of the K-theory of Azumaya R-algebras, which may be of independent interest. We also include a section leading to the Ω-spectrum for QCA over C∗-algebras with unitary circuits.
A quantum cellular automaton (QCA) is a unitary discrete-time evolution of a quantum many-body system, which can be described as a dynamics system , where A is any matrix and is a unitary operator representing the global evolution of QCA. And QCAs are characterized by locality (or causality). Among them, quantum circuits are the special classes of QCAs, which use unitary operators to control and transform the initial quantum state of qubit into a final quantum state, quantum circuits are special and widely studied in quantum information. A group is a set of elements combined with an operation, which satisfies associativity, identity and invertibility. This article shows that group theory provides the right language for studying the relation between QCAs and quantum circuits among them.
Quantum cellular automata (QCA) are discrete models of space and time homogeneous quantum field theories (QFTs) and regarded as natural candidates for quantum simulation. Description of a QCA over the separable Hilbert space of finite, unbounded configurations (UFC Hilbert space) with unitary state evolution is the {\it Schrödinger template}, and over the incomplete infinite tensor product algebra (ITPA) with evolution by algebra automorphism is the {\it Heisenberg template}. Whether every Heisenberg template admits an equivalent Schrödinger template is a foundational question, and one that has persisted as an open problem. In the present paper we prove that for every Heisenberg template an equivalent Schrödinger template exists. We frame the question from a representation theory standpoint, using constructs and results from the representation theory of finite and countably infinite dimensional vector spaces and from category theory to answer it. With the previously known existence of a Heisenberg template for every Schrödinger template, our result establishes the equivalence of the templates.