Q-CHOP: Quantum constrained Hamiltonian optimization

Abstract

Combinatorial optimization problems that arise in science and industry typically have constraints. Yet the presence of constraints makes them challenging to tackle using both classical and quantum optimization algorithms. We propose a new quantum algorithm for constrained optimization, which we call quantum constrained Hamiltonian optimization (Q-CHOP). Our algorithm leverages the observation that for many problems, while the best solution is difficult to find, the worst feasible (constraint-satisfying) solution is known. The basic idea of Q-CHOP is to enforce a Hamiltonian constraint at all times, thereby restricting evolution to the subspace of feasible states, and slowly ``rotate'' an objective Hamiltonian to trace an adiabatic path from the worst feasible state to the best feasible state. Q-CHOP thereby assigns qualitatively distinct roles to the constraint and objective functions of a constrained optimization problem. We additionally propose a version of Q-CHOP that can start in any feasible state. Finally, we benchmark Q-CHOP against the commonly-used adiabatic algorithm of quantum annealing with an objective function that penalizes constraint violation, and find that Q-CHOP consistently performs significantly better on a wide range of problems, including textbook graph problems, knapsack problems, combinatorial auctions, and a real-world financial use case of bond exchange-traded fund basket optimization.

uploading accepted version

References in corpus (28)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Encoding a qubit in an oscillator
• Shortcuts to adiabaticity: concepts, methods, and applications
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Mathematical Foundation of Quantum Annealing
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Quantum computing for finance
• Quantum critical dynamics in a 5000-qubit programmable spin glass
• Quantum Simulations of Classical Annealing Processes
• Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Hybrid quantum-classical algorithms for approximate graph coloring
• Encoding an oscillator into many oscillators
• Applying quantum algorithms to constraint satisfaction problems
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Quantum speedup of branch-and-bound algorithms
• A quantum walk assisted approximate algorithm for bounded NP optimisation problems
• Combinatorial optimisation via highly efficient quantum walks
• Constrained Optimization via Quantum Zeno Dynamics
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems
• Approaches to Constrained Quantum Approximate Optimization
• Fast Quantum Methods for Optimization
• Recursive QAOA outperforms the original QAOA for the MAX-CUT problem on complete graphs
• Exact Equivalence between Quantum Adiabatic Algorithm and Quantum Circuit Algorithm
• Quantum independent set problem and non-abelian adiabatic mixing
• Quantum Algorithm for Approximating Maximum Independent Sets
• Universal Quantum Speedup for Branch-and-Bound, Branch-and-Cut, and Tree-Search Algorithms
• Quantum counterdiabatic driving enhanced by two-stage local control