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

Cellular Automata on Quantum Annealing Systems

Dunn, Robert A.

Published Jan 7, 2021• 0 citations
arXivHTMLPDF

Abstract

We present herein an introduction to implementing 2-color cellular automata on quantum annealing systems, such as the D-Wave quantum computer. We show that implementing nearest-neighbor cellular automata is possible. We present an implementation of Wolfram's cellular automata Rule 110, which has previously been shown to be a universal Turing machine, as a QUBO suitable for use on quantum annealing systems. We demonstrate back-propagation of cellular automata rule sets to determine initial cell states for a desired later system state. We show 2-D 2-color cellular automata, such as Conway's Game of Life, can be expressed for quantum annealing systems.

DOI
10.48550/arxiv.2101.02309

Related papers

Quantum Cellular Automata for Quantum Error Correction and Density Classification

Thiago L. M. Guedes, D. Winter, Markus Müller

Quantum cellular automata are alternative quantum-computing paradigms to quantum Turing machines and quantum circuits. Their working mechanisms are inherently automated, therefore measurement free, and they act in a translation invariant manner on all cells or qudits of a register, generating a global rule that updates cell states locally, i.e., based solely on the states of their neighbors. Although desirable features in many applications, it is generally not clear to which extent these fully automated discrete-time local updates can generate and sustain long-range order in the (noisy) systems they act upon. In particular, whether and how quantum cellular automata can perform quantum error correction remain open questions. We close this conceptual gap by proposing quantum cellular automata with quantum-error-correction capabilities. We design and investigate two (quasi)one dimensional quantum cellular automata based on known classical cellular-automata rules with density-classification capabilities, namely the local majority voting and the two-line voting. We investigate the performances of those quantum cellular automata as quantum-memory components by simulating the number of update steps required for the logical information they act upon to be afflicted by a logical bit flip. The proposed designs pave a way to further explore the potential of new types of quantum cellular automata with built-in quantum-error-correction capabilities.

Physical Review Letters•Oct 7, 2024•9 citations

Quantum cellular automata for quantum error correction and density classification

Thiago L. M. Guedes, Winter, Don, Markus Müller

Quantum cellular automata are alternative quantum-computing paradigms to quantum Turing machines and quantum circuits. Their working mechanisms are inherently automated, therefore measurement free, and they act in a translation invariant manner on all cells/qudits of a register, generating a global rule that updates cell states locally, i.e., based solely on the states of their neighbors. Although desirable features in many applications, it is generally not clear to which extent these fully automated discrete-time local updates can generate and sustain long-range order in the (noisy) systems they act upon. In special, whether and how quantum cellular automata can perform quantum error correction remain open questions. We close this conceptual gap by proposing quantum cellular automata with quantum-error-correction capabilities. We design and investigate two (quasi-)one dimensional quantum cellular automata based on known classical cellular-automata rules with density-classification capabilities, namely the local majority voting and the two-line voting. We investigate the performances of those quantum cellular automata as quantum-memory components by simulating the number of update steps required for the logical information they act upon to be afflicted by a logical bit flip. The proposed designs pave a way to further explore the potential of new types of quantum cellular automata with built-in quantum error correction capabilities.

arXiv:2309.03608•Jan 1, 2023•0 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

On one-dimensional quantum cellular automata

John Watrous

Since Richard Feynman introduced the notion of quantum computation in 1982, various models of "quantum computers" have been proposed (R. Feynman, 1992). These models include quantum Turing machines and quantum circuits. We define another quantum computational model, one dimensional quantum cellular automata, and demonstrate that any quantum Turing machine can be efficiently simulated by a one dimensional quantum cellular automaton with constant slowdown. This can be accomplished by consideration of a restricted class of one dimensional quantum cellular automata called one dimensional partitioned quantum cellular automata. We also show that any one dimensional partitioned quantum cellular automaton can be simulated by a quantum Turing machine with linear slowdown, but the problem of efficiently simulating an arbitrary one dimensional quantum cellular automaton with a quantum Turing machine is left open. From this discussion, some interesting facts concerning these models are easily deduced.

Annual Symposium on Foundations of Computer Science•Nov 19, 2002•156 citations

Quantum Algorithms of Solving the Backtracking of One-dimensional Cellular Automata

Weng-Long Chang, Mang Feng, Kawuu W. Lin +2 more

In [Wolfram 1982; Wolfram 1983; Wolfram 2002], the backtracking of one-dimensional cellular automata is to find out which of the 2n possible initial configurations of width n evolve to a specific configuration. In this paper, in one-dimensional cellular automata for a specific configuration of width n, its unique initial configuration can be found by mean of the proposed quantum algorithm with polynomial quantum gates, polynomial quantum bits and the successful probability that is the same as that of Shor's quantum order-finding algorithm in [Shor 1994].

arXiv:1109.2998•Sep 14, 2011•0 citations

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
We present herein an introduction to implementing 2-color cellular automata on quantum annealing systems, such as the D-Wave quantum computer. We show that implementing nearest-neighbor cellular automata is possible. We present an implementation of Wolfram's cellular automata Rule 110, which has previously been shown to be a universal Turing machine, as a QUBO suitable for use on quantum annealing systems. We demonstrate back-propagation of cellular automata rule sets to determine initial cell states for a desired later system state. We show 2-D 2-color cellular automata, such as Conway's Game of Life, can be expressed for quantum annealing systems.
Quantum cellular automata are alternative quantum-computing paradigms to quantum Turing machines and quantum circuits. Their working mechanisms are inherently automated, therefore measurement free, and they act in a translation invariant manner on all cells or qudits of a register, generating a global rule that updates cell states locally, i.e., based solely on the states of their neighbors. Although desirable features in many applications, it is generally not clear to which extent these fully automated discrete-time local updates can generate and sustain long-range order in the (noisy) systems they act upon. In particular, whether and how quantum cellular automata can perform quantum error correction remain open questions. We close this conceptual gap by proposing quantum cellular automata with quantum-error-correction capabilities. We design and investigate two (quasi)one dimensional quantum cellular automata based on known classical cellular-automata rules with density-classification capabilities, namely the local majority voting and the two-line voting. We investigate the performances of those quantum cellular automata as quantum-memory components by simulating the number of update steps required for the logical information they act upon to be afflicted by a logical bit flip. The proposed designs pave a way to further explore the potential of new types of quantum cellular automata with built-in quantum-error-correction capabilities.
Quantum cellular automata are alternative quantum-computing paradigms to quantum Turing machines and quantum circuits. Their working mechanisms are inherently automated, therefore measurement free, and they act in a translation invariant manner on all cells/qudits of a register, generating a global rule that updates cell states locally, i.e., based solely on the states of their neighbors. Although desirable features in many applications, it is generally not clear to which extent these fully automated discrete-time local updates can generate and sustain long-range order in the (noisy) systems they act upon. In special, whether and how quantum cellular automata can perform quantum error correction remain open questions. We close this conceptual gap by proposing quantum cellular automata with quantum-error-correction capabilities. We design and investigate two (quasi-)one dimensional quantum cellular automata based on known classical cellular-automata rules with density-classification capabilities, namely the local majority voting and the two-line voting. We investigate the performances of those quantum cellular automata as quantum-memory components by simulating the number of update steps required for the logical information they act upon to be afflicted by a logical bit flip. The proposed designs pave a way to further explore the potential of new types of quantum cellular automata with built-in quantum error correction capabilities.
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.
Since Richard Feynman introduced the notion of quantum computation in 1982, various models of "quantum computers" have been proposed (R. Feynman, 1992). These models include quantum Turing machines and quantum circuits. We define another quantum computational model, one dimensional quantum cellular automata, and demonstrate that any quantum Turing machine can be efficiently simulated by a one dimensional quantum cellular automaton with constant slowdown. This can be accomplished by consideration of a restricted class of one dimensional quantum cellular automata called one dimensional partitioned quantum cellular automata. We also show that any one dimensional partitioned quantum cellular automaton can be simulated by a quantum Turing machine with linear slowdown, but the problem of efficiently simulating an arbitrary one dimensional quantum cellular automaton with a quantum Turing machine is left open. From this discussion, some interesting facts concerning these models are easily deduced.
In [Wolfram 1982; Wolfram 1983; Wolfram 2002], the backtracking of one-dimensional cellular automata is to find out which of the 2n possible initial configurations of width n evolve to a specific configuration. In this paper, in one-dimensional cellular automata for a specific configuration of width n, its unique initial configuration can be found by mean of the proposed quantum algorithm with polynomial quantum gates, polynomial quantum bits and the successful probability that is the same as that of Shor's quantum order-finding algorithm in [Shor 1994].
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.