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• 47 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•27 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•7 citations

An overview of quantum cellular automata

Pablo J. Arrighi

Natural Computing•Sep 20, 2019•133 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•164 citations

Classification of Quantum Cellular Automata

Michael Freedman, Matthew B. Hastings

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

Quantum walks via quantum cellular automata

Pedro C. S. Costa, Renato Portugal, Fernando de Melo

arXiv:1803.02176•Quantum Information Processing•Jul 26, 2018•18 citations
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.