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:0704.3961

Intrinsically universal one-dimensional quantum cellular automata in two flavours

Pablo J. Arrighi, Renan Fargetton, Zizhu Wang

Published Apr 30, 2007• 1 citation
arXivHTMLPDF

Abstract

We give a one-dimensional quantum cellular automaton (QCA) capable of simulating all others. By this we mean that the initial configuration and the local transition rule of any one-dimensional QCA can be encoded within the initial configuration of the universal QCA. Several steps of the universal QCA will 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 of adjacent cells in the universal QCA. The encoding is linear and hence does not carry any of the cost of the computation. We do this in two flavours: a weak one which requires an infinite but periodic initial configuration and a strong one which needs only a finite initial configuration. KEYWORDS: Quantum cellular automata, Intrinsic universality, Quantum computation.

DOI
10.48550/arxiv.0704.3961

Related papers

Intrinsically Universal One-dimensional Quantum Cellular Automata in Two Flavours

Pablo J. Arrighi, Renan Fargetton, Zizhu Wang

We give a one-dimensional quantum cellular automaton (QCA) capable of simulating all others. By this we mean that the initial configuration and the local transition rule of any onedimensional QCA can be encoded within the initial configuration of the universal QCA. Several steps of the universal QCA will 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 of adjacent cells in the universal QCA. The encoding is linear and hence does not carry any of the cost of the computation. We do this in two flavours: a weak one which requires an infinite but periodic initial configuration and a strong one which needs only a finite initial configuration.

Fundamenta Informaticae•Jan 1, 2009•17 citations

Quantum Walks via Quantum Cellular Automata for Simulating Quantum Computation

Tanish Singh

The quantum walk is a subset of classical random walks.Considerable research has lately been conducted on quantum walks in relation to quantum computing.The walk may be thought of as a type of quantum cellular automata.In a broader sense, there is a one-to-one link between them.Furthermore, we look at another type of quantum cellular automata that may be thought of as a quantum version of stochastic cellular automata.The quantum walk formalism is a widely used and quite practical paradigm for modelling quantum systems such as Dirac equation simulations, discrete dynamics in both the low and high energy regimes, and the development of a multitude of quantum algorithms.The walker in a QW moves in a quantum superposition of pathways, and the ensuing interference serves as the foundation for a broad range of quantum algorithms, including quantum search, graph isomorphism issues, and rating nodes in a network.To generate a block representation of n-dimensional quantum cellular automata, we apply the following general result to them.As a result, we have demonstrated that their generic, axiomatic formulation nevertheless produces a unifying, operational representation of them.Some non-trivial ramifications are investigated, such as the fact that bijective non-reversible CA are not physical as closed systems, or that quantum information can move faster than classical informationwithin some specified dynamics.Finally, we present n-dimensional quantum cellular automata that can simulate anything else.This means that the initial configuration and local transition rule of any one-dimensional QCA may be stored within the universal QCA's initial configuration.The simulated QCA will then correspond to many phases of the universal QCA.In the sense that each cell in the simulated QCA is represented as a group of nearby cells in the universal QCA, the simulation preserves the topology.Because the encoding is linear, it bears no cost of the calculation.

IARJSET•Nov 30, 2021•0 citations

Universally Programmable Quantum Cellular Automaton

Dan J. Shepherd, Titus Franz, Reinhard F. Werner

We discuss the role of classical control in the context of reversible quantum cellular automata. Employing the structure theorem for quantum cellular automata, we give a general construction scheme to turn an arbitrary cellular automaton with external classical control into an autonomous one, thereby proving the computational equivalence of these two models. We use this technique to construct a universally programmable cellular automaton on a one-dimensional lattice with single cell dimension 12.

arXiv:quant-ph/0512058•Physical Review Letters•Jul 13, 2006•49 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

One-Dimensional Quantum Cellular Automata

Pablo J. Arrighi, Vincent Nesme, Reinhard F. Werner

We define and study quantum cellular automata (QCA). We show that they are reversible and that the neighborhood of the inverse is the opposite of the neighborhood. We also show that QCA always admit, modulo shifts, a two-layered block representation. Note that the same two-layered block representation result applies also over infinite configurations, as was previously shown for one-dimensional systems in the more elaborate formalism of operators algebras [18]. Here the proof is simpler and self-contained, moreover we discuss a counterexample QCA in higher dimensions.

•Jan 1, 2011•5 citations

Quantum cellular automaton for universal quantum computation

Robert Raussendorf

This paper describes a quantum cellular automaton capable of performing universal quantum computation. The automaton has an elementary transition function that acts on Margolus cells of $2\ifmmode\times\else\texttimes\fi{}2$ qubits, and both the ``quantum input'' and the program are encoded in the initial state of the system.

arXiv:quant-ph/0412048•Physical Review A•Aug 1, 2005•54 citations
We give a one-dimensional quantum cellular automaton (QCA) capable of simulating all others. By this we mean that the initial configuration and the local transition rule of any one-dimensional QCA can be encoded within the initial configuration of the universal QCA. Several steps of the universal QCA will 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 of adjacent cells in the universal QCA. The encoding is linear and hence does not carry any of the cost of the computation. We do this in two flavours: a weak one which requires an infinite but periodic initial configuration and a strong one which needs only a finite initial configuration. KEYWORDS: Quantum cellular automata, Intrinsic universality, Quantum computation.
We give a one-dimensional quantum cellular automaton (QCA) capable of simulating all others. By this we mean that the initial configuration and the local transition rule of any onedimensional QCA can be encoded within the initial configuration of the universal QCA. Several steps of the universal QCA will 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 of adjacent cells in the universal QCA. The encoding is linear and hence does not carry any of the cost of the computation. We do this in two flavours: a weak one which requires an infinite but periodic initial configuration and a strong one which needs only a finite initial configuration.
The quantum walk is a subset of classical random walks.Considerable research has lately been conducted on quantum walks in relation to quantum computing.The walk may be thought of as a type of quantum cellular automata.In a broader sense, there is a one-to-one link between them.Furthermore, we look at another type of quantum cellular automata that may be thought of as a quantum version of stochastic cellular automata.The quantum walk formalism is a widely used and quite practical paradigm for modelling quantum systems such as Dirac equation simulations, discrete dynamics in both the low and high energy regimes, and the development of a multitude of quantum algorithms.The walker in a QW moves in a quantum superposition of pathways, and the ensuing interference serves as the foundation for a broad range of quantum algorithms, including quantum search, graph isomorphism issues, and rating nodes in a network.To generate a block representation of n-dimensional quantum cellular automata, we apply the following general result to them.As a result, we have demonstrated that their generic, axiomatic formulation nevertheless produces a unifying, operational representation of them.Some non-trivial ramifications are investigated, such as the fact that bijective non-reversible CA are not physical as closed systems, or that quantum information can move faster than classical informationwithin some specified dynamics.Finally, we present n-dimensional quantum cellular automata that can simulate anything else.This means that the initial configuration and local transition rule of any one-dimensional QCA may be stored within the universal QCA's initial configuration.The simulated QCA will then correspond to many phases of the universal QCA.In the sense that each cell in the simulated QCA is represented as a group of nearby cells in the universal QCA, the simulation preserves the topology.Because the encoding is linear, it bears no cost of the calculation.
We discuss the role of classical control in the context of reversible quantum cellular automata. Employing the structure theorem for quantum cellular automata, we give a general construction scheme to turn an arbitrary cellular automaton with external classical control into an autonomous one, thereby proving the computational equivalence of these two models. We use this technique to construct a universally programmable cellular automaton on a one-dimensional lattice with single cell dimension 12.
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 define and study quantum cellular automata (QCA). We show that they are reversible and that the neighborhood of the inverse is the opposite of the neighborhood. We also show that QCA always admit, modulo shifts, a two-layered block representation. Note that the same two-layered block representation result applies also over infinite configurations, as was previously shown for one-dimensional systems in the more elaborate formalism of operators algebras [18]. Here the proof is simpler and self-contained, moreover we discuss a counterexample QCA in higher dimensions.