ArXiv.org · 2008 · 16 citations · 36 references
ComputingComputer SciencePhysicsAlgorithmsQuantum ComputingQuantum MechanicsAdiabatic Quantum ComputingQuantum AlgorithmsQuantum BitsQuantum CircuitsQuantum ComputationQuantum SimulationAdiabatic Algorithm DesignAdiabatic Quantum ComputationAdiabatic Quantum SimulationDecision ProblemsHamiltonian SimulationQuantum Hamiltonian SimulationQuantum Walk AlgorithmsUniversal Quantum Computation
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.
36
<i>Quantum Computation and Quantum Information</i>
Michael A. Nielsen, Isaac L. Chuang, Lov K. Grover · American Journal of Physics · 2002 · 22.7K citations
Fault-tolerant quantum computation by anyons
Alexei Kitaev · Annals of Physics · 2003 · 7.3K citations · Full text
Computing, Computer Science, Physics +12
Richard P. Feynman · Foundations of Physics · 1986 · 1.7K citations
Quantum computations: algorithms and error correction
Alexei Kitaev · Russian Mathematical Surveys · 1997 · 1.5K citations