Intrinsically universal \(n\)-dimensional quantum cellular automata

DOI10.1016/J.JCSS.2011.12.008zbMath1250.68203DBLPjournals/jcss/ArrighiG12arXiv0907.3827OpenAlexW1974849073WikidataQ62037054 ScholiaQ62037054MaRDI QIDQ1757844

Pablo Arrighi, Jonathan Grattage

Publication date: 6 November 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Abstract: There have been several non-axiomatic approaches taken to define Quantum Cellular Automata (QCA). Partitioned QCA (PQCA) are the most canonical of these non-axiomatic definitions. In this work we first show that any QCA can be put into the form of a PQCA. Our construction reconciles all the non-axiomatic definitions of QCA, showing that they can all simulate one another, and hence that they are all equivalent to the axiomatic definition. Next, we describe a simple n-dimensional QCA capable of simulating all others, in that the initial configuration and the forward evolution of any n-dimensional QCA can be encoded within the initial configuration of the intrinsically universal QCA, and that several steps of the intrinsically universal QCA then correspond to one step of the simulated QCA. Both results are made formal by defining generalised n-dimensional intrinsic simulation, i.e. a notion of simulation which 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. We argue that this notion brings the computer science based concepts of simulation and universality one step closer to theoretical physics.

Full work available at URL: https://arxiv.org/abs/0907.3827

zbMATH Keywords

cellular automatauniversalityquantum computationquantum circuits

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Quantum algorithms and complexity in the theory of computing (68Q12)

Cites Work

• Unitarity plus causality implies localizability
• Reversible simulation of one-dimensional irreversible cellular automata
• A six-state minimal time solution to the Firing squad synchronization problem
• Computation and construction universality of reversible cellular automata
• From quantum cellular automata to quantum lattice gases
• Partitioned quantum cellular automata are intrinsically universal
• From Dirac to diffusion: decoherence in quantum lattice gases
• One-Dimensional Quantum Cellular Automata over Finite, Unbounded Configurations
• A Simple n-Dimensional Intrinsically Universal Quantum Cellular Automaton
• Intrinsically Universal One-dimensional Quantum Cellular Automata in Two Flavours
• Intrinsic universality of a 1-dimensional reversible Cellular Automaton
• Reversible cellular automaton able to simulate any other reversible one using partitioning automata
• Mathematical Foundations of Computer Science 2004
• Endomorphisms and automorphisms of the shift dynamical system
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

Related Items (4)

The Simulation Powers and Limitations of Hierarchical Self-Assembly Systems ⋮ An overview of quantum cellular automata ⋮ A novel design of 8-bit adder/subtractor by quantum-dot cellular automata ⋮ Symmetries of the Dirac quantum walk and emergence of the de Sitter group

This page was built for publication: Intrinsically universal \(n\)-dimensional quantum cellular automata