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

Jan 1, 1996458 citations

Scalar fermionic cellular automata on finite Cayley graphs

Paolo Perinotti, Leopoldo Poggiali

A map on finitely many fermionic modes represents a unitary evolution if and only if it preserves canonical anticommutation relations (CARs). Preliminarily general features of nonlinear fermionic cellular automata (FCAs) that can be extended to the case of cellular automata on infinite graphs are analyzed. We use the preservation of CARs for the classification of FCAs on Cayley graphs of finite groups in two simple but paradigmatic case studies. The physical properties of the solutions are finally discussed. One of the examples allows us to classify all scalar FCAs on the $\mathbb{Z}$ integers.A map on finitely many fermionic modes represents a unitary evolution if and only if it preserves canonical anticommutation relations (CARs). Preliminarily general features of nonlinear fermionic cellular automata (FCAs) that can be extended to the case of cellular automata on infinite graphs are analyzed. We use the preservation of CARs for the classification of FCAs on Cayley graphs of finite groups in two simple but paradigmatic case studies. The physical properties of the solutions are finally discussed. One of the examples allows us to classify all scalar FCAs on the $\mathbb{Z}$ integers.

arXiv:1807.08695Physical Review ANov 26, 20185 citations

Quantum Cellular Automata

Ioannis Liliopoulos, Georgios D. Varsamis, Ioannis G. Karafyllidis

Emergence, complexity and computationJan 1, 20251 citation

Unitarity in one dimensional nonlinear quantum cellular automata

DAVID A. MEYER

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 the local rule is nonlinear. Since the unitary global transition amplitudes are constructed from the product of local transition amplitudes, infinite lattices require different treatment than periodic ones. We prove Unitarity Theorems for both cases, expressing the equivalence in $1+1$ dimensions of global unitarity and certain sets of constraints on the local rule, and then show that these constraints can be solved to give a variety of multiparameter families of nonlinear quantum cellular automata. The Unitarity Theorems, together with a Surjectivity Theorem for the infinite case, also imply that unitarity is decidable for one dimensional cellular automata.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 the local rule is nonlinear. Since the unitary global transition amplitudes are constructed from the product of local transition amplitudes, infinite lattices require different treatment than periodic ones. We prove Unitarity Theorems for both cases, expressing the equivalence in $1+1$ dimensions of global unitarity and certain sets of constraints on the local rule, and then show that these constraints can be solved to give a variety of multiparameter families of nonlinear quantum cellular automata. The Unitarity Theorems, together with a Surjectivity Theorem for the infinite case, also imply that unitarity is decidable for one dimensional cellular automata.

arXiv:quant-ph/9605023May 15, 199620 citations

Structures in quantum cellular automata

Gerhard Grössing, Anton Zeilinger

Physica B+CJul 1, 198829 citations

\mathbb{Z}

integers.

1+1

dimensions of global unitarity and certain sets of constraints on the local rule, and then show that these constraints can be solved to give a variety of multiparameter families of nonlinear quantum cellular automata. The Unitarity Theorems, together with a Surjectivity Theorem for the infinite case, also imply that unitarity is decidable for one dimensional cellular automata.