Quantum Speedup by Quantum Annealing

Abstract

We study the glued-trees problem of Childs et. al. in the adiabatic model of quantum computing and provide an annealing schedule to solve an oracular problem exponentially faster than classically possible. The Hamiltonians involved in the quantum annealing do not suffer from the so-called sign problem. Unlike the typical scenario, our schedule is efficient even though the minimum energy gap of the Hamiltonians is exponentially small in the problem size. We discuss generalizations based on initial-state randomization to avoid some slowdowns in adiabatic quantum computing due to small gaps.

7 pages

References in corpus (3)

• Bounds for the adiabatic approximation with applications to quantum computation
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• A Quantum Approach to Classical Statistical Mechanics

Cited by in corpus (88)

• Adiabatic Quantum Computing
• Quantum Chemistry in the Age of Quantum Computing
• Defining and detecting quantum speedup
• Perspectives of quantum annealing: Methods and implementations
• Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
• Error corrected quantum annealing with hundreds of qubits
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Quantum annealing correction for random Ising problems
• Quantum Annealing Correction with Minor Embedding
• Bayesian Network Structure Learning Using Quantum Annealing
• SU(2) lattice gauge theory on a quantum annealer
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• Dynamics of reverse annealing for the fully-connected $p$-spin model
• Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
• Different Strategies for Optimization Using the Quantum Adiabatic Algorithm
• Nested Quantum Annealing Correction
• Quantum Walks
• Non-Stoquastic Interactions in Quantum Annealing via the Aharonov-Anandan Phase
• Benchmark test of Black-box optimization using D-Wave quantum annealer
• Chaos in spin glasses revealed through thermal boundary conditions
• The Power of Adiabatic Quantum Computation with No Sign Problem
• Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
• The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning
• Analog Nature of Quantum Adiabatic Unstructured Search
• Universal measurement-based quantum computation in two-dimensional SPT phases
• Variationally Scheduled Quantum Simulation
• Optimally Stopped Optimization
• Blueprint for all-to-all connected superconducting spin qubits
• Fast Quantum Methods for Optimization
• On The Power Of Coherently Controlled Quantum Adiabatic Evolutions
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Continuous-Time Quantum Algorithms for Unstructured Problems
• Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
• A double-slit proposal for quantum annealing
• Complexity of quantum state verification in the quantum linear systems problem
• Diabatic Quantum Annealing for the Frustrated Ring Model
• Quantum Annealing with Trigger Hamiltonians: Application to 2-SAT and Nonstoquastic Problems
• Theorem on the existence of a nonzero energy gap in adiabatic quantum computation
• Parity Quantum Optimization: Encoding Constraints
• Statistical-mechanical analysis of compressed sensing for Hamiltonian estimation of Ising spin glass
• Customized quantum annealing schedules
• Monte Carlo simulation of stoquastic Hamiltonians
• Diagonal Catalysts in Quantum Adiabatic Optimization
• Deep learning optimal quantum annealing schedules for random Ising models
• Quantum adiabatic optimization with Rydberg arrays: localization phenomena and encoding strategies
• Quantum annealing for hard 2-SAT problems : Distribution and scaling of minimum energy gap and success probability
• Quantum annealing with twisted fields
• Sensitivity of quantum speedup by quantum annealing to a noisy oracle
• Quantum optimization within lattice gauge theory model on a quantum simulator
• Theoretical survey of unconventional quantum annealing methods applied to adifficult trial problem
• Locally Suppressed Transverse-Field Protocol for Diabatic Quantum Annealing
• Construction of non-convex polynomial loss functions for training a binary classifier with quantum annealing
• Demonstration of long-range correlations via susceptibility measurements in a one-dimensional superconducting Josephson spin chain
• Message-passing algorithm of quantum annealing with nonstoquastic Hamiltonian
• Rapid quantum approaches for combinatorial optimisation inspired by optimal state-transfer
• A necessary condition for quantum adiabaticity applied to the adiabatic Grover search
• Adiabatic approximation for the imaginary-time Schroedinger equation and its application to simulated annealing
• Robust Diabatic Quantum Search by Landau-Zener-Stückelberg Oscillations
• Topologically protected Grover's oracle for the partition problem
• Excited state search using quantum annealing
• How to experimentally evaluate the adiabatic condition for quantum annealing
• Quantum annealing of Cayley-tree Ising spins at small scales
• Improving the efficiency of quantum annealing with controlled diagonal catalysts
• Quadratic constrained mixed discrete optimization with an adiabatic quantum optimizer
• Validating a Two Qubit Non-Stoquastic Hamiltonian in Quantum Annealing
• Approximating maximum independent set on Rydberg atom arrays using local detunings
• Cost of Emulating a Small Quantum Annealing Problem in the Circuit-Model
• Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
• Limits of Short-Time Evolution of Local Hamiltonians
• Development of research network on Quantum Annealing Computation and Information using Google Scholar data
• Formulation of the Electric Vehicle Charging and Routing Problem for a Hybrid Quantum-Classical Search Space Reduction Heuristic
• Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
• Validity condition for high-fidelity Digitized Quantum Annealing
• Excited-State Adiabatic Quantum Computation Started with Vacuum States
• Hardware-efficient quantum annealing with error mitigation via classical shadow
• Optimization of neural networks via finite-value quantum fluctuations
• The Perturbed Ferromagnetic Chain: A Tuneable Test of Quantum Hardness in the Transverse-Field Ising Model
• Frustration-enhanced quantum annealing correction models with additional inter-replica interactions
• Assessment of image generation by quantum annealer
• A Quantum Annealing Approach to Reduce Covid-19 Spread on College Campuses
• Essentiality of the Non-stoquastic Hamiltonians and Driver Graph Design in Quantum Optimization Annealing
• Curve fitting on a quantum annealer for an advanced navigation method
• Leveraging Analog Neutral Atom Quantum Computers for Diversified Pricing in Hybrid Column Generation Frameworks
• Quantum speed-up for solving the one-dimensional Hubbard model using quantum annealing
• A Quantum Genetic Algorithm with application to Cosmological Parameters Estimation
• Improving adiabatic quantum factorization via chopped random-basis optimization