Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/9605023

Unitarity in one dimensional nonlinear quantum cellular automata

DAVID A. MEYER

Published May 15, 1996• 20 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.quant-ph/9605023

Related papers

From Quantum Cellular Automata To Quantum Lattice Gases

DAVID A. MEYER, From Qca, Qlga David +1 more

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, 1996•458 citations

Reversible quantum cellular automata

Benjamin W. Schumacher, Reinhard F. Werner

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.

arXiv:quant-ph/0405174•May 28, 2004•98 citations

An algebraic study of unitary one dimensional quantum cellular automata

Pablo J. Arrighi

We provide algebraic criteria for the unitarity of linear quantum cellular automata, i.e. one dimensional quantum cellular automata. We derive these both by direct combinatorial arguments, and by adding constraints into the model which do not change the quantum cellular automata's computational power. The configurations we consider have finite but unbounded size.

arXiv:quant-ph/0512040•Dec 5, 2005•0 citations

Are nonlinear discrete cellular automata compatible with quantum mechanics?

Hans-Thomas Elze

We consider discrete and integer-valued cellular automata (CA). A particular class of which comprises "Hamiltonian CA" with equations of motion that bear similarities to Hamilton's equations, while they present discrete updating rules. The dynamics is linear , quite similar to unitary evolution described by the Schrödinger equation. This has been essential in our construction of an invertible map between such CA and continuous quantum mechanical models, which incorporate a fundamental discreteness scale. Based on Shannon's sampling theory, it leads, for example, to a one-to-one relation between quantum mechanical and CA conservation laws. The important issue of linearity of the theory is examined here by incorporating higher-order nonlinearities into the underlying action. These produce inconsistent nonlocal (in time) effects when trying to describe continuously such nonlinear CA. Therefore, in the present framework, only linear CA and local quantum mechanical dynamics are compatible.

arXiv:1505.03764•Journal of Physics Conference Series•Jul 30, 2015•13 citations

Quantization of Cellular Automata

Pablo J. Arrighi, Vincent Nesme

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 translatio n and locality. We prove that this locality condition is so restrictive in the q uantum case that every quantum cellular automaton constructed in this way - i. e., by linearization of a classical one - must be reversible. We also discuss some subtleties about the extent of nonlocality that can be encountered in the o ne-dimensional case; we show that, even when the quantized version is non local, still, under some conditions, we may be unable to use this nonlocality to trans mit information nonlocally.

arXiv:0903.0258•Mar 2, 2009•1 citation

Definition and evolution of quantum cellular automata with two qubits per cell

Ioannis G. Karafyllidis

Studies of quantum computer implementations suggest cellular quantum computer architectures. These architectures can simulate the evolution of quantum cellular automata, which can possibly simulate both quantum and classical physical systems and processes. It is however known that except for the trivial case, unitary evolution of one-dimensional homogeneous quantum cellular automata with one qubit per cell is not possible. Quantum cellular automata that comprise two qubits per cell are defined and their evolution is studied using a quantum computer simulator. The evolution is unitary and its linearity manifests itself as a periodic structure in the probability distribution patterns.

arXiv:0811.0085•Physical Review A•Oct 5, 2004•33 citations
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+11+11+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.
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.
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 consider discrete and integer-valued cellular automata (CA). A particular class of which comprises "Hamiltonian CA" with equations of motion that bear similarities to Hamilton's equations, while they present discrete updating rules. The dynamics is linear , quite similar to unitary evolution described by the Schrödinger equation. This has been essential in our construction of an invertible map between such CA and continuous quantum mechanical models, which incorporate a fundamental discreteness scale. Based on Shannon's sampling theory, it leads, for example, to a one-to-one relation between quantum mechanical and CA conservation laws. The important issue of linearity of the theory is examined here by incorporating higher-order nonlinearities into the underlying action. These produce inconsistent nonlocal (in time) effects when trying to describe continuously such nonlinear CA. Therefore, in the present framework, only linear CA and local quantum mechanical dynamics are compatible.
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 translatio n and locality. We prove that this locality condition is so restrictive in the q uantum case that every quantum cellular automaton constructed in this way - i. e., by linearization of a classical one - must be reversible. We also discuss some subtleties about the extent of nonlocality that can be encountered in the o ne-dimensional case; we show that, even when the quantized version is non local, still, under some conditions, we may be unable to use this nonlocality to trans mit information nonlocally.
Studies of quantum computer implementations suggest cellular quantum computer architectures. These architectures can simulate the evolution of quantum cellular automata, which can possibly simulate both quantum and classical physical systems and processes. It is however known that except for the trivial case, unitary evolution of one-dimensional homogeneous quantum cellular automata with one qubit per cell is not possible. Quantum cellular automata that comprise two qubits per cell are defined and their evolution is studied using a quantum computer simulator. The evolution is unitary and its linearity manifests itself as a periodic structure in the probability distribution patterns.