Quantum Computation by Adiabatic Evolution

Abstract

We give a quantum algorithm for solving instances of the satisfiability problem, based on adiabatic evolution. The evolution of the quantum state is governed by a time-dependent Hamiltonian that interpolates between an initial Hamiltonian, whose ground state is easy to construct, and a final Hamiltonian, whose ground state encodes the satisfying assignment. To ensure that the system evolves to the desired final ground state, the evolution time must be big enough. The time required depends on the minimum energy difference between the two lowest states of the interpolating Hamiltonian. We are unable to estimate this gap in general. We give some special symmetric cases of the satisfiability problem where the symmetry allows us to estimate the gap and we show that, in these cases, our algorithm runs in polynomial time.

24 pages, 12 figures, LaTeX, amssymb,amsmath, BoxedEPS packages; email to [email protected]

References in corpus (1)

• Strengths and Weaknesses of Quantum Computing

Cited by in corpus (223)

• Quantum Computing
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Simulated Quantum Computation of Molecular Energies
• Quantum algorithms: an overview
• The Variational Quantum Eigensolver: a review of methods and best practices
• Programmable Quantum Simulations of Spin Systems with Trapped Ions
• Quantum Computational Supremacy
• Towards Quantum Chemistry on a Quantum Computer
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
• Quantum computing for finance: overview and prospects
• The quest for a Quantum Neural Network
• Quantum Search by Local Adiabatic Evolution
• Qudits and high-dimensional quantum computing
• Digitized adiabatic quantum computing with a superconducting circuit
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Simulating chemistry using quantum computers
• The Future of Quantum Computing with Superconducting Qubits
• Experimental signature of programmable quantum annealing
• Quantum computing for finance
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Bifurcation-based adiabatic quantum computation with a nonlinear oscillator network: Toward quantum soft computing
• A case study in programming a quantum annealer for hard operational planning problems
• Adiabatic Quantum Simulation of Quantum Chemistry
• Quantum simulation of the wavefunction to probe frustrated Heisenberg spin systems
• Emerging quantum computing algorithms for quantum chemistry
• The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Computational complexity of the landscape I
• Efficient variational simulation of non-trivial quantum states
• Qibo: a framework for quantum simulation with hardware acceleration
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Dynamic Portfolio Optimization with Real Datasets Using Quantum Processors and Quantum-Inspired Tensor Networks
• Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
• Hamiltonian Simulation Using Linear Combinations of Unitary Operations
• Algorithms for quantum simulation at finite energies
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• Quantum Simulation of Quantum Field Theory in the Light-Front Formulation
• A NASA Perspective on Quantum Computing: Opportunities and Challenges
• Quantum Machine Learning for Particle Physics using a Variational Quantum Classifier
• Adiabatic Quantum Computing for Random Satisfiability Problems
• Hamiltonian simulation in the low-energy subspace
• The quantum Ising chain for beginners
• On the representation of Boolean and real functions as Hamiltonians for quantum computing
• SU(2) lattice gauge theory on a quantum annealer
• The relativistic quantum channel of communication through field quanta
• A 16-bit Coherent Ising Machine for One-Dimensional Ring and Cubic Graph Problems
• Hamiltonian Simulation with Optimal Sample Complexity
• Quantum walks can find a marked element on any graph
• A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
• Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
• Exact and efficient Lanczos method on a quantum computer
• NISQ Computers: A Path to Quantum Supremacy
• Variational approaches to constructing the many-body nuclear ground state for quantum computing
• Landau-Zener transitions in qubits controlled by electromagnetic fields
• Temperature scaling law for quantum annealing optimizers
• Time-dependent unbounded Hamiltonian simulation with vector norm scaling
• QuASeR -- Quantum Accelerated De Novo DNA Sequence Reconstruction
• A new construction for a QMA complete 3-local Hamiltonian
• Adiabatic quantum state transfer in a semiconductor quantum-dot spin chain
• Shortcuts to adiabaticity for quantum annealing
• Adiabatic quantum optimization with the wrong Hamiltonian
• Local gap threshold for frustration-free spin systems
• Quantum annealing: the fastest route to quantum computation?
• Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
• Skyrmion Qubits: Challenges For Future Quantum Computing Applications
• Training and Classification using a Restricted Boltzmann Machine on the D-Wave 2000Q
• Finite temperature quantum annealing solving exponentially small gap problem with non-monotonic success probability
• Introduction to Quantum Algorithms for Physics and Chemistry
• Quantum Walks
• An introduction to quantum annealing
• Non-Stoquastic Interactions in Quantum Annealing via the Aharonov-Anandan Phase
• Quantum Computing for Quantum Tunnelling
• Uncertain fate of fair sampling in quantum annealing
• Quantum Machine Learning for Finance
• Low depth mechanisms for quantum optimization
• Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
• Error suppression and error correction in adiabatic quantum computation II: non-equilibrium dynamics
• Image Acquisition Planning for Earth Observation Satellites with a Quantum Annealer
• A new perturbative approach to the adiabatic approximation
• Quantum Analogue Computing
• Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
• Improved machine learning algorithm for predicting ground state properties
• On the stability of topological phases on a lattice
• Variational Quantum Anomaly Detection: Unsupervised mapping of phase diagrams on a physical quantum computer
• Implementation of a Hybrid Classical-Quantum Annealing Algorithm for Logistic Network Design
• GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm
• Quantum Algorithms for Solving Ordinary Differential Equations via Classical Integration Methods
• An energetic perspective on rapid quenches in quantum annealing
• Analysis of The Vehicle Routing Problem Solved via Hybrid Quantum Algorithms in Presence of Noisy Channels
• From quantum circuits to adiabatic algorithms
• Performance of a Quantum Annealer for Ising Ground State Computations on Chimera Graphs
• Quantum Monte Carlo tunneling from quantum chemistry to quantum annealing
• Ultrafast Variational Simulation of Non-trivial Quantum States with Long Range Interactions
• HOQST: Hamiltonian Open Quantum System Toolkit
• Quantum neural networks to simulate many-body quantum systems
• Charged particle tracking with quantum annealing-inspired optimization
• Breaking the quantum adiabatic speed limit by jumping along geodesics
• Optimal Control for Quantum Metrology via Pontryagin's principle
• An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
• Two quantum Ising algorithms for the Shortest Vector Problem: one for now and one for later
• Quantum adiabatic algorithm for Hilbert's tenth problem: I. The algorithm
• Application of Pontryagin's Minimum Principle to Grover's Quantum Search Problem
• Resource estimate for quantum many-body ground-state preparation on a quantum computer
• Evaluating Ising Processing Units with Integer Programming
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Effects of dissipation in an adiabatic quantum search algorithm
• Projected Cooling Algorithm for Quantum Computation
• Quantum adiabatic machine learning with zooming
• Preparing quantum many-body scar states on quantum computers
• Nested Quantum Annealing Correction at Finite Temperature: $p$-spin models
• Diagrammatic Approach to Quantum Search
• Product Formulas for Exponentials of Commutators
• A family of [[6k, 2k, 2]] codes for practical, scalable adiabatic quantum computation
• Adiabatic Quantum Optimization for Associative Memory Recall
• On The Power Of Coherently Controlled Quantum Adiabatic Evolutions
• Testing a quantum annealer as a quantum thermal sampler
• Measurement-Based Quantum Computing with Valence-Bond-Solids
• Encoding-Independent Optimization Problem Formulation for Quantum Computing
• HamLib: A library of Hamiltonians for benchmarking quantum algorithms and hardware
• Practical designs for permutation symmetric problem Hamiltonians on hypercubes
• Adiabatic quantum computation with flux qubits, first experimental results
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Qibolab: an open-source hybrid quantum operating system
• Can quantum computing solve classically unsolvable problems?
• Quantum spectral clustering algorithm for unsupervised learning
• Complexity of quantum state verification in the quantum linear systems problem
• Hybrid actor-critic algorithm for quantum reinforcement learning at CERN beam lines
• Analysis of quantum Krylov algorithms with errors
• Quantum Adiabatic Algorithm and Large Spin Tunnelling
• Quantum Computing by Cooling
• Mitigating noise in digital and digital-analog quantum computation
• Measurement of the ground-state flux diagram of three coupled qubits as a first step towards the demonstration of adiabatic quantum computation
• Analogue Quantum Simulation: A New Instrument for Scientific Understanding
• Counterdiabatic optimized driving in quantum phase sensitive models
• Fair Sampling Error Analysis on NISQ Devices
• The prospects of Monte Carlo antibody loop modelling on a fault-tolerant quantum computer
• Exponentially faster implementations of Select(H) for fermionic Hamiltonians
• Quantum computing through the lens of control: A tutorial introduction
• On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma
• Irreconcilable Difference Between Quantum Walks and Adiabatic Quantum Computing
• Binary Control Pulse Optimization for Quantum Systems
• Customized quantum annealing schedules
• Making Classical Ground State Spin Computing Fault-Tolerant
• Annealing Optimisation of Mixed ZX Phase Circuits
• Deep recurrent networks predicting the gap evolution in adiabatic quantum computing
• Deep learning optimal quantum annealing schedules for random Ising models
• Exploiting In-Constraint Energy in Constrained Variational Quantum Optimization
• Elementary Proof of QAOA Convergence
• Initial State Encoding via Reverse Quantum Annealing and h-gain Features
• Multi-qubit quantum computing using discrete-time quantum walks on closed graphs
• Anneal-path correction in flux qubits
• Hamiltonian simulation for low-energy states with optimal time dependence
• Fast quantum algorithms for traversing paths of eigenstates
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• Disorder-assisted graph coloring on quantum annealers
• Preparing ground states of the XXZ model using the quantum annealing with inductively coupled superconducting flux qubits
• A Boltzmann Machine Implementation for the D-Wave
• Quantum information processing: The case of vanishing interaction energy
• Quantum annealing with twisted fields
• Quantum search using non-Hermitian adiabatic evolution
• Hückel Molecular Orbital Theory on a Quantum Computer: A Scalable System-Agnostic Variational Implementation with Compact Encoding
• Tunneling in projective quantum Monte Carlo simulations with guiding wave functions
• Simulating Majorana zero modes on a noisy quantum processor
• Limitations on the simulation of non-sparse Hamiltonians
• Finding cliques by quantum adiabatic evolution
• Solving systems of Boolean multivariate equations with quantum annealing
• A Quantum Algorithm for Model-Independent Searches for New Physics
• A Hybrid Quantum-Classical Approach to the Electric Mobility Problem
• Scaling of errors in digitized counterdiabatic driving
• FragQC: An Efficient Quantum Error Reduction Technique using Quantum Circuit Fragmentation
• Tangle Machines
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Optimizing adiabaticity in quantum mechanics
• Post-processing variationally scheduled quantum algorithm for constrained combinatorial optimization problems
• Diagnosing First and Second Order Phase Transitions with Probes of Quantum Chaos
• Quantum walk on a graph of spins: magnetism and entanglement
• Quantum Machine Learning and its Supremacy in High Energy Physics
• Why adiabatic quantum annealing is unlikely to yield speed-up
• Quantum annealing-based computed tomography using variational approach for a real-number image reconstruction
• A quantum algorithm for solving 0-1 Knapsack problems
• A numerical approach for calculating exact non-adiabatic terms in quantum dynamics
• Mixed-Integer Programming Using a Bosonic Quantum Computer
• Polynomial Time Algorithms for Estimating Spectra of Adiabatic Hamiltonians
• Quantum and quantum-inspired optimization for solving the minimum bin packing problem
• Bifurcation-based quantum annealing with nested spins
• On Strong Bounds for Trotter and Zeno Product Formulas with Bosonic Applications
• Improving nonstoquastic quantum annealing with spin-reversal transformations
• Near-Landauer-Bound Quantum Computing Using Single Spins
• Counterdiabatic driving for long-lived singlet state preparation
• Generalized Ramsey numbers through adiabatic quantum optimization
• Quantum Zeno approach for molecular energies with maximum commuting initialHamiltonians
• Efficient Quantum Cooling Algorithm for Fermionic Systems
• Hierarchical Multigrid Ansatz for Variational Quantum Algorithms
• Phase transitions and gaps in quantum random energy models
• Experimental Demonstration of Fermionic QAOA with One-Dimensional Cyclic Driver Hamiltonian
• Mapping constrained optimization problems to quantum annealing with application to fault diagnosis
• Quantum Annealing with chaotic driver Hamiltonians
• Ising Hamiltonians for Constrained Combinatorial Optimization Problems and the Metropolis-Hastings Warm-Starting Algorithm
• A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing---Abridged Version
• Using copies to improve precision in continuous-time quantum computing
• Quantum Adiabatic Theorem Revisited
• Limits of Short-Time Evolution of Local Hamiltonians
• Passive verification protocol for thermal graph states
• Mathematical computability questions for some classes of linear and non-linear differential equations originated from Hilbert's tenth problem
• Quantum Software Ecosystem Design
• Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
• Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
• Absence of small-world effects at the quantum level and stability of the quantum critical point
• Duality approach to quantum annealing of the 3-XORSAT problem
• Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem
• Adiabatic theorem for classical stochastic processes
• Enhancing Scalability of Quantum Eigenvalue Transformation of Unitary Matrices for Ground State Preparation through Adaptive Finer Filtering
• Quantum algorithmic differentiation
• Control limit for the quantum state preparation under stochastic control errors
• Efficient inference in the transverse field Ising model
• Lattice Holography on a Quantum Computer
• Towards algorithm-free physical equilibrium model of computing
• Building a fusion-based quantum computer using teleported gates
• Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA
• Quantum adiabaticity in many-body systems and almost-orthogonality in complementary subspace