Quantum speedup of branch-and-bound algorithms

Abstract

Branch-and-bound is a widely used technique for solving combinatorial optimisation problems where one has access to two procedures: a branching procedure that splits a set of potential solutions into subsets, and a cost procedure that determines a lower bound on the cost of any solution in a given subset. Here we describe a quantum algorithm that can accelerate classical branch-and-bound algorithms near-quadratically in a very general setting. We show that the quantum algorithm can find exact ground states for most instances of the Sherrington-Kirkpatrick model in time $O(2^{0.226n})$, which is substantially more efficient than Grover's algorithm.

11 pages, 5 figures

References in corpus (1)

• Finding spin-glass ground states using quantum walks

Cited by in corpus (34)

• Quantum computing for finance
• Challenges and Opportunities in Quantum Optimization
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Quantum Algorithms for Jet Clustering
• Low depth mechanisms for quantum optimization
• Challenges of variational quantum optimization with measurement shot noise
• Towards large-scale quantum optimization solvers with few qubits
• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• A "thoughtful" Local Friendliness no-go theorem: a prospective experiment with new assumptions to suit
• Two quantum Ising algorithms for the Shortest Vector Problem: one for now and one for later
• Explainable AI using expressive Boolean formulas
• Many-body localization enables iterative quantum optimization
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• Quantum-accelerated constraint programming
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
• A Quantum Search Decoder for Natural Language Processing
• A quantum algorithm for solving 0-1 Knapsack problems
• Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing
• Mixed-Integer Programming Using a Bosonic Quantum Computer
• Implementation of Quantum Fourier Transform and Quantum Hashing for a Quantum Device with Arbitrary Qubits Connection Graphs
• On the Baltimore Light RailLink into the quantum future
• Computational complexity of three-dimensional Ising spin glass: Lessons from D-Wave annealer
• Practical implementation of a quantum backtracking algorithm
• End-to-End Protocol for High-Quality QAOA Parameters with Few Shots
• Quantum-inspired dynamical models on quantum and classical annealers
• A Quantum Constraint Generation Framework for Binary Linear Programs
• Leveraging Analog Neutral Atom Quantum Computers for Diversified Pricing in Hybrid Column Generation Frameworks
• Multiclass Portfolio Optimization via Variational Quantum Eigensolver with Dicke State Ansatz
• Q-CHOP: Quantum constrained Hamiltonian optimization
• Quantum tree generator improves QAOA state-of-the-art for the knapsack problem
• A quantum search method for quadratic and multidimensional knapsack problems