When is a Quantum Cellular Automaton (QCA) a Quantum Lattice Gas Automaton (QLGA)?
arXiv:1209.5367 · doi:10.1063/1.4821640
Abstract
Quantum cellular automata (QCA) are models of quantum computation of particular interest from the point of view of quantum simulation. Quantum lattice gas automata (QLGA - equivalently partitioned quantum cellular automata) represent an interesting subclass of QCA. QLGA have been more deeply analyzed than QCA, whereas general QCA are likely to capture a wider range of quantum behavior. Discriminating between QLGA and QCA is therefore an important question. In spite of much prior work, classifying which QCA are QLGA has remained an open problem. In the present paper we establish necessary and sufficient conditions for unbounded, finite Quantum Cellular Automata (QCA) (finitely many active cells in a quiescent background) to be Quantum Lattice Gas Automata (QLGA). We define a local condition that classifies those QCA that are QLGA, and we show that there are QCA that are not QLGA. We use a number of tools from functional analysis of separable Hilbert spaces and representation theory of associative algebras that enable us to treat QCA on finite but unbounded configurations in full detail.
37 pages, 7 figures, with changes to explanatory text and updated figures, J. Math. Phys. version
References in corpus (8)
- Simulated Quantum Computation of Molecular Energies
- The Bravyi-Kitaev transformation for quantum computation of electronic structure
- Polynomial-time quantum algorithm for the simulation of chemical dynamics
- From transistor to trapped-ion computers for quantum chemistry
- Reversible quantum cellular automata
- Local Unitary Quantum Cellular Automata
- Matrix Algebras and Semidefinite Programming Techniques for Codes
- Back to the Future: A roadmap for quantum simulation from vintage quantum chemistry
Cited by in corpus (11)
- A review of Quantum Cellular Automata
- Efficient and scalable quantum walk algorithms via the quantum Fourier transform
- Causal and compositional structure of unitary transformations
- Quantum field theory from a quantum cellular automaton in one spatial dimension and a no-go theorem in higher dimensions
- Quantum cellular automata without particles
- Multiparticle quantum walk with a gas-like interaction
- History Dependent Quantum Random Walks as Quantum Lattice Gas Automata
- An overview of Quantum Cellular Automata
- The Equivalence of Schrödinger and Heisenberg Pictures in Quantum Cellular Automata
- Neighborhood-History Quantum Walk
- Fully Quantum Lattice Gas Automata Building Blocks for Computational Basis State Encodings