Simple proof of equivalence between adiabatic quantum computation and the circuit model

Abstract

We prove the equivalence between adiabatic quantum computation and quantum computation in the circuit model. An explicit adiabatic computation procedure is given that generates a ground state from which the answer can be extracted. The amount of time needed is evaluated by computing the gap. We show that the procedure is computationally efficient.

5 pages, 2 figures. v2: improved gap estimates and added some more details

References in corpus (9)

• The Physical Implementation of Quantum Computation
• Internal Consistency of Fault-Tolerant Quantum Error Correction in Light of Rigorous Derivations of the Quantum Markovian Limit
• General error estimate for adiabatic quantum computing
• From quantum circuits to adiabatic algorithms
• Ground State Quantum Computation
• Mimicking Time Evolution within a Quantum Ground State: Ground-State Quantum Computation, Cloning, and Teleportation
• Quantum Algorithm to Solve Satisfiability Problems
• Solving Satisfiability Problems by the Ground-State Quantum Computer
• Efficiency of Ground State Quantum Computer

Cited by in corpus (103)

• Quantum Computing
• Adiabatic Quantum Computing
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Quantum Annealing and Analog Quantum Computation
• Digitized adiabatic quantum computing with a superconducting circuit
• Universal computation by multi-particle quantum walk
• Mathematical Foundation of Quantum Annealing
• Simulating chemistry using quantum computers
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Error corrected quantum annealing with hundreds of qubits
• Realizable Hamiltonians for Universal Adiabatic Quantum Computers
• A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation
• Quantum Adiabatic Brachistochrone
• Decoherence in adiabatic quantum computation
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• Towards Fault Tolerant Adiabatic Quantum Computation
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Quantum adiabatic machine learning
• Adiabatic state preparation study of methylene
• Accuracy vs run time in adiabatic quantum search
• MAX 2-SAT with up to 108 qubits
• Nested Quantum Annealing Correction
• Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction
• Spectral Gap Amplification
• Experimental Adiabatic Quantum Factorization under Ambient Conditions Based on a Solid-State Single Spin System
• Decoherence of adiabatically steered quantum systems
• Training a quantum annealing based restricted Boltzmann machine on cybersecurity data
• Algorithmic approach to adiabatic quantum optimization
• Improved machine learning algorithm for predicting ground state properties
• Non-Abelian holonomic transformation in the presence of classical noise
• Electronic structure with direct diagonalization on a D-Wave quantum annealer
• Calculation of molecular vibrational spectra on a quantum annealer
• Quantum Gates with Controlled Adiabatic Evolutions
• Mean Field Analysis of Quantum Annealing Correction
• Effect of Local Minima on Adiabatic Quantum Optimization
• Hamiltonian gadgets with reduced resource requirements
• High Fidelity Adiabatic Quantum Computation via Dynamical Decoupling
• Schedule path optimization for quantum annealing and adiabatic quantum computing
• Fast Universal Quantum Computation with Railroad-switch Local Hamiltonians
• Space-Time Circuit-to-Hamiltonian Construction and Its Applications
• An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
• Universal 2-local Hamiltonian Quantum Computing
• Complex instruction set computing architecture for performing accurate quantum $Z$ rotations with less magic
• Scalable effective temperature reduction for quantum annealers via nested quantum annealing correction
• Adiabatic Quantum Search in Open Systems
• Period Finding with Adiabatic Quantum Computation
• Quantum and Classical in Adiabatic Computation
• Optimal parametrizations of adiabatic paths
• Adiabatic and Hamiltonian computing on a 2D lattice with simple 2-qubit interactions
• A family of [[6k, 2k, 2]] codes for practical, scalable adiabatic quantum computation
• Adiabatic topological quantum computing
• Adiabatic Quantum Transistors
• The Bose-Hubbard model is QMA-complete
• Local Hamiltonians in Quantum Computation
• Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
• Error suppression in adiabatic quantum computing with qubit ensembles
• Continuous-Time Quantum Algorithms for Unstructured Problems
• Improved Bounds for Eigenpath Traversal
• Fault-tolerant Holonomic Quantum Computation in Surface Codes
• The Stability of Quantum Concatenated Code Hamiltonians
• Feedback-controlled adiabatic quantum computation
• Error Suppression for Hamiltonian Quantum Computing in Markovian Environments
• Decoherence induced deformation of the ground state in adiabatic quantum computation
• Theorem on the existence of a nonzero energy gap in adiabatic quantum computation
• Quantum search by partial adiabatic evolution
• A Fault-Tolerant Scheme of Holonomic Quantum Computation on Stabilizer Codes with Robustness to Low-weight Thermal Noise
• A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing
• Customized quantum annealing schedules
• Making Classical Ground State Spin Computing Fault-Tolerant
• Hamiltonian quantum computing with superconducting qubits
• How Fast Can Quantum Annealers Count?
• Quantum Atom Optics: Theory and Applications to Quantum Technology
• A Novel Algebraic Geometry Compiling Framework for Adiabatic Quantum Computations
• On models of nonlinear evolution paths in adiabatic quantum algorithms
• Phase transitions in the frustrated Ising ladder with stoquastic and nonstoquastic catalysts
• The relationship between minimum gap and success probability in adiabatic quantum computing
• Separability gap and large deviation entanglement criterion
• Probing nonlinear adiabatic paths with a universal integrator
• Noise-tolerant quantum speedups in quantum annealing without fine tuning
• Proof of efficient, parallelized, universal adiabatic quantum computation
• Incentivising Demand Side Response through Discount Scheduling using Hybrid Quantum Optimization
• Noise enhanced performance of adiabatic quantum computing by lifting degeneracies
• Avoid First Order Quantum Phase Transition by Changing Problem Hamiltonians
• Simulating quantum circuits by adiabatic computation: improved spectral gap bounds
• Efficient optimization of perturbative gadgets
• Complexity of the XY antiferromagnet at fixed magnetization
• Homological Description of the Quantum Adiabatic Evolution With a View Toward Quantum Computations
• Lower bounds for adiabatic quantum algorithms by quantum speed limits
• High-dimensional counterdiabatic quantum computing
• Cost of Emulating a Small Quantum Annealing Problem in the Circuit-Model
• Decoherence of a tunable capacitively shunted flux qubit
• Mapping NP-Hard Problems to Restricted Adiabatic Quantum Architectures
• Gates for Adiabatic Quantum Computing
• Threshold theorem in isolated quantum dynamics with stochastic control errors
• Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
• Development of research network on Quantum Annealing Computation and Information using Google Scholar data
• Sampling electronic structure QUBOs with Ocean and Mukai solvers
• On fixed-gap adiabatic quantum computation
• Quantum Walks on Necklaces and Mixing
• Control limit for the quantum state preparation under stochastic control errors
• Experimental implementation of leakage elimination operators
• Improving adiabatic quantum factorization via chopped random-basis optimization
• Renormalization method for proving frustration-free local spin chains are gapped