Universal quantum walks and adiabatic algorithms by 1D Hamiltonians
arXiv:0802.1207
Abstract
We construct a family of time-independent nearest-neighbor Hamiltonians coupling eight-state systems on a 1D ring that enables universal quantum computation. Hamiltonians in this family can achieve universality either by driving a continuous-time quantum walk or by terminating an adiabatic algorithm. In either case, the universality property can be understood as arising from an efficient simulation of a programmable quantum circuit. Using gadget perturbation theory, one can demonstrate the same kind of universality for related Hamiltonian families acting on qubits in 2D. Our results demonstrate that simulating 1D chains of spin-7/2 particles is BQP-hard, and indeed BQP-complete because the outputs of decision problems can be encoded in the outputs of such simulations.
14 pages
References in corpus (16)
- Fault-tolerant quantum computation by anyons
- Quantum Computation and Decision Trees
- Perfect state transfer in quantum spin networks
- Two-Bit Gates are Universal for Quantum Computation
- Exponential algorithmic speedup by quantum walk
- Perfect Transfer of Arbitrary States in Quantum Spin Networks
- The Propagation of Quantum Information Through a Spin System
- A Universal Two--Bit Gate for Quantum Computation
- The power of quantum systems on a line
- The Dynamics of 1D Quantum Spin Systems Can Be Approximated Efficiently
- Towards Fault Tolerant Adiabatic Quantum Computation
- On Universal and Fault-Tolerant Quantum Computing
- Hamiltonian Quantum Cellular Automata in 1D
- Quantum simulators, continuous-time automata, and translationally invariant systems
- A universally programmable Quantum Cellular Automaton
- Spin-1/2 particles moving on a 2D lattice with nearest-neighbor interactions can realize an autonomous quantum computer
Cited by in corpus (9)
- Universal computation by quantum walk
- The Future of Quantum Computing with Superconducting Qubits
- Hamiltonian Quantum Cellular Automata in 1D
- Control by quantum dynamics on graphs
- Hamiltonian gadgets with reduced resource requirements
- Local Hamiltonians in Quantum Computation
- Quantum Walk-based Generation of Entanglement Between Two Walkers
- Parameter Estimation, Model Reduction and Quantum Filtering
- Quantum vs Classical Birth and Death Processes; Exactly Solvable Examples