Universal 2-local Hamiltonian Quantum Computing

Abstract

We present a Hamiltonian quantum computation scheme universal for quantum computation (BQP). Our Hamiltonian is a sum of a polynomial number (in the number of gates L in the quantum circuit) of time-independent, constant-norm, 2-local qubit-qubit interaction terms. Furthermore, each qubit in the system interacts only with a constant number of other qubits. The computer runs in three steps - starts in a simple initial product-state, evolves it for time of order L^2 (up to logarithmic factors) and wraps up with a two-qubit measurement. Our model differs from the previous universal 2-local Hamiltonian constructions in that it does not use perturbation gadgets, does not need large energy penalties in the Hamiltonian and does not need to run slowly to ensure adiabatic evolution.

recomputed the necessary number of interactions, new geometric layout, added references

References in corpus (14)

• Universal computation by quantum walk
• The power of quantum systems on a line
• Simple proof of equivalence between adiabatic quantum computation and the circuit model
• Realizable Hamiltonians for Universal Adiabatic Quantum Computers
• Scalable quantum computation via local control of only two qubits
• Collective processes of an ensemble of spin-1/2 particles
• Adiabatic Gate Teleportation
• A new construction for a QMA complete 3-local Hamiltonian
• Quantum simulators, continuous-time automata, and translationally invariant systems
• Hamiltonian Quantum Cellular Automata in 1D
• Possible implementation of adiabatic quantum algorithm with superconducting flux qubits
• Computation on Spin Chains with Limited Access
• Fast Universal Quantum Computation with Railroad-switch Local Hamiltonians
• Grover's algorithm on a Feynman computer

Cited by in corpus (16)

• Computational advantage of quantum random sampling
• Universal Quantum Hamiltonians
• Quantum gate learning in engineered qubit networks: Toffoli gate with always-on interactions
• Quantum Walks
• Fast quantum computation at arbitrarily low energy
• Adiabatic and Hamiltonian computing on a 2D lattice with simple 2-qubit interactions
• The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension
• A comparative study of universal quantum computing models: towards a physical unification
• Quadratization in discrete optimization and quantum mechanics
• Hamiltonian quantum computing with superconducting qubits
• Universal resources for quantum computing
• Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction
• Efficiently verifiable quantum advantage on near-term analog quantum simulators
• Pinned QMA: The power of fixing a few qubits in proofs
• Efficient Classical Simulation of the DQC1 Circuit with Zero Discord
• Quantum Walks on Necklaces and Mixing