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:0907.3827 · Journal of Computer and System Sciences

Intrinsically universal n-dimensional quantum cellular automata

Pablo J. Arrighi, Jonathan Grattage

Published Jan 12, 2012• 19 citations
arXivHTMLPDF
DOI
10.1016/j.jcss.2011.12.008

Related papers

Partitioned quantum cellular automata are intrinsically universal

Pablo J. Arrighi, Jonathan Grattage

arXiv:1010.2335•Natural Computing•Aug 30, 2011•41 citations

One-Dimensional Quantum Cellular Automata over Finite, Unbounded Configurations

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

arXiv:0711.3517•Lecture notes in computer science•Sep 24, 2008•32 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

A Simple n-Dimensional Intrinsically Universal Quantum Cellular Automaton

Pablo J. Arrighi, Jonathan Grattage

arXiv:1002.1015•Lecture notes in computer science•Jan 1, 2010•12 citations

Nontrivial Quantum Cellular Automata in Higher Dimensions

Jeongwan Haah, Lukasz Fidkowski, Matthew B. Hastings

arXiv:1812.01625•Communications in Mathematical Physics•Nov 10, 2022•68 citations

Quantum Cellular Automata

Karoline Wiesner

Quantum cellular automata (QCA) are reviewed, including early and more recent proposals. QCA are a generalization of (classical) cellular automata (CA) and in particular of reversible CA. The latter are reviewed shortly. An overview is given over early attempts by various authors to define one-dimensional QCA. These turned out to have serious shortcomings which are discussed as well. Various proposals subsequently put forward by a number of authors for a general definition of one- and higher-dimensional QCA are reviewed and their properties such as universality and reversibility are discussed.

arXiv:0808.0679•Aug 5, 2008•1 citation
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.
Quantum cellular automata (QCA) are reviewed, including early and more recent proposals. QCA are a generalization of (classical) cellular automata (CA) and in particular of reversible CA. The latter are reviewed shortly. An overview is given over early attempts by various authors to define one-dimensional QCA. These turned out to have serious shortcomings which are discussed as well. Various proposals subsequently put forward by a number of authors for a general definition of one- and higher-dimensional QCA are reviewed and their properties such as universality and reversibility are discussed.