Different Strategies for Optimization Using the Quantum Adiabatic Algorithm

Abstract

We present the results of a numerical study, with 20 qubits, of the performance of the Quantum Adiabatic Algorithm on randomly generated instances of MAX 2-SAT with a unique assignment that maximizes the number of satisfied clauses. The probability of obtaining this assignment at the end of the quantum evolution measures the success of the algorithm. Here we report three strategies which consistently increase the success probability for the hardest instances in our ensemble: decreasing the overall evolution time, initializing the system in excited states, and adding a random local Hamiltonian to the middle of the evolution.

References in corpus (1)

• Quantum Adiabatic Evolution Algorithms with Different Paths

Cited by in corpus (45)

• Adiabatic Quantum Computing
• Digitized adiabatic quantum computing with a superconducting circuit
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Differentiable Quantum Architecture Search
• Decoherence in adiabatic quantum computation
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• Recent advances for quantum classifiers
• Training A Quantum Optimizer
• Shortcuts to adiabaticity for quantum annealing
• Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
• Non-Stoquastic Interactions in Quantum Annealing via the Aharonov-Anandan Phase
• Algorithm engineering for a quantum annealing platform
• An energetic perspective on rapid quenches in quantum annealing
• Adiabatic optimization versus diffusion Monte Carlo
• Combinatorial Optimization on Gate Model Quantum Computers: A Survey
• Advantages of Unfair Quantum Ground-State Sampling
• Application of Pontryagin's Minimum Principle to Grover's Quantum Search Problem
• Variationally Scheduled Quantum Simulation
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Fast Quantum Methods for Optimization
• Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
• Complexity of quantum state verification in the quantum linear systems problem
• Customized quantum annealing schedules
• Irreconcilable Difference Between Quantum Walks and Adiabatic Quantum Computing
• Deep learning optimal quantum annealing schedules for random Ising models
• Quantum annealing with twisted fields
• Quantum ground state isoperimetric inequalities for the energy spectrum of local Hamiltonians
• Theoretical survey of unconventional quantum annealing methods applied to adifficult trial problem
• Why adiabatic quantum annealing is unlikely to yield speed-up
• The quantum annealing gap and quench dynamics in the exact cover problem
• Tensor network method for reversible classical computation
• Anti-crossings and spectral gap during quantum adiabatic evolution
• Hamiltonian surgery: Cheeger-type gap inequalities for nonpositive (stoquastic), real, and Hermitian matrices
• Quantum annealing sampling with a bias field
• Bifurcation-based quantum annealing with nested spins
• Quantum adiabatic optimization without heuristics
• The performance of the quantum adiabatic algorithm on spike Hamiltonians
• Quantum Annealing with chaotic driver Hamiltonians
• Posiform Planting: Generating QUBO Instances for Benchmarking
• Quantum Adiabatic Evolution for Global Optimization in Big Data
• Ising formulations of routing optimization problems
• QPack: Quantum Approximate Optimization Algorithms as universal benchmark for quantum computers
• Maritime Just-in-time navigation with Quantum algorithms
• Excited-State Adiabatic Quantum Computation Started with Vacuum States
• Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem