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:1010.2335 · Natural Computing

Partitioned quantum cellular automata are intrinsically universal

Pablo J. Arrighi, Jonathan Grattage

Published Aug 30, 2011• 41 citations
arXivHTMLPDF
DOI
10.1007/s11047-011-9277-6

Related papers

Intrinsically universal n-dimensional quantum cellular automata

Pablo J. Arrighi, Jonathan Grattage

arXiv:0907.3827•Journal of Computer and System Sciences•Jan 12, 2012•19 citations

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

arXiv:0704.3961•Apr 30, 2007•1 citation

An overview of quantum cellular automata

Pablo J. Arrighi

Natural Computing•Sep 20, 2019•117 citations

Classification of Quantum Cellular Automata

Michael Freedman, Matthew B. Hastings

arXiv:1902.10285•Communications in Mathematical Physics•Apr 6, 2020•60 citations

On Quantum Cellular Automata

Alexander Yu. Vlasov

In recent work [quant-ph/0405174] by Schumacher and Werner was discussed an abstract algebraic approach to a model of reversible quantum cellular automata (CA) on a lattice. It was used special model of CA based on partitioning scheme and so there is a question about quantum CA derived from more general, standard model of classical CA. In present work is considered an approach to definition of a scheme with "history", valid for quantization both irreversible and reversible classical CA directly using local transition rules. It is used language of vectors in Hilbert spaces instead of C*-algebras, but results may be compared in some cases. Finally, the quantum lattice gases, quantum walk and "bots" are also discussed briefly.

arXiv:quant-ph/0406119•Jun 17, 2004•6 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
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.
In recent work [quant-ph/0405174] by Schumacher and Werner was discussed an abstract algebraic approach to a model of reversible quantum cellular automata (CA) on a lattice. It was used special model of CA based on partitioning scheme and so there is a question about quantum CA derived from more general, standard model of classical CA. In present work is considered an approach to definition of a scheme with "history", valid for quantization both irreversible and reversible classical CA directly using local transition rules. It is used language of vectors in Hilbert spaces instead of C*-algebras, but results may be compared in some cases. Finally, the quantum lattice gases, quantum walk and "bots" are also discussed briefly.
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.