Hamiltonian Quantum Cellular Automata in 1D

Abstract

We construct a simple translationally invariant, nearest-neighbor Hamiltonian on a chain of 10-dimensional qudits that makes it possible to realize universal quantum computing without any external control during the computational process. We only require the ability to prepare an initial computational basis state which encodes both the quantum circuit and its input. The computational process is then carried out by the autonomous Hamiltonian time evolution. After a time polynomially long in the size of the quantum circuit has passed, the result of the computation is obtained with high probability by measuring a few qudits in the computational basis. This result also implies that there cannot exist efficient classical simulation methods for generic translationally invariant nearest-neighbor Hamiltonians on qudit chains, unless quantum computers can be efficiently simulated by classical computers (or, put in complexity theoretic terms, unless BPP=BQP).

explanation in Section II largely rewritten, 2 new figures, accepted for publication in PRA

References in corpus (16)

• Fault-tolerant quantum computation by anyons
• Elementary gates for quantum computation
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• The power of quantum systems on a line
• Universal quantum computation using only projective measurement, quantum memory, and preparation of the 0 state
• Unified derivations of measurement-based schemes for quantum computation
• Both Toffoli and Controlled-NOT need little help to do universal quantum computation
• Quantum simulators, continuous-time automata, and translationally invariant systems
• A quantum cellular automaton for universal quantum computation
• A universally programmable Quantum Cellular Automaton
• A 2 rebit gate universal for quantum computing
• Spin-1/2 particles moving on a 2D lattice with nearest-neighbor interactions can realize an autonomous quantum computer
• The Computational Power of Symmetric Hamiltonians
• Universal quantum walks and adiabatic algorithms by 1D Hamiltonians
• A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation
• Models of Quantum Cellular Automata

Cited by in corpus (35)

• Adiabatic Quantum Computing
• Universal computation by quantum walk
• Quantum algorithms for quantum chemistry and quantum materials science
• The Future of Quantum Computing with Superconducting Qubits
• The power of quantum systems on a line
• Computational advantage of quantum random sampling
• A review of Quantum Cellular Automata
• Universal Quantum Hamiltonians
• Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
• Ground State Entanglement in One Dimensional Translationally Invariant Quantum Systems
• Fast Universal Quantum Computation with Railroad-switch Local Hamiltonians
• Universal 2-local Hamiltonian Quantum Computing
• The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
• The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension
• Interfacing with Hamiltonian Dynamics
• A comparative study of universal quantum computing models: towards a physical unification
• Local Hamiltonians in Quantum Computation
• Universal quantum walks and adiabatic algorithms by 1D Hamiltonians
• The Complexity of Translationally-Invariant Low-Dimensional Spin Lattices in 3D
• Superconducting qubit circuit emulation of a vector spin-1/2
• Universal resources for quantum computing
• Quantum Complexity: restrictions on algorithms and architectures
• Hamiltonian quantum computer in one dimension
• A Simple n-Dimensional Intrinsically Universal Quantum Cellular Automaton
• The Role of Rotational Invariance in the Properties of Hamiltonians
• Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction
• Intrinsically universal n-dimensional quantum cellular automata
• Universal Hamiltonians for Exponentially Long Simulation
• An overview of Quantum Cellular Automata
• Pinned QMA: The power of fixing a few qubits in proofs
• Waveguide QED toolboxes for universal quantum matter
• Quantum Coherence in Noisy Cellular Automata
• Partitioned quantum cellular automata are intrinsically universal
• Reversibility in one-dimensional quantum cellular automata in the presence of noise
• Quantum Walks on Necklaces and Mixing