Quantum-Informed Recursive Optimization Algorithms

Abstract

We propose and implement a family of quantum-informed recursive optimization (QIRO) algorithms for combinatorial optimization problems. Our approach leverages quantum resources to obtain information that is used in problem-specific classical reduction steps that recursively simplify the problem. These reduction steps address the limitations of the quantum component and ensure solution feasibility in constrained optimization problems. Additionally, we use backtracking techniques to further improve the performance of the algorithm without increasing the requirements on the quantum hardware. We demonstrate the capabilities of our approach by informing QIRO with correlations from classical simulations of shallow (depth $p=1$) circuits of the quantum approximate optimization algorithm (QAOA), solving instances of maximum independent set and maximum satisfiability problems with hundreds of variables. We also demonstrate how QIRO can be deployed on a neutral atom quantum processor available online on Amazon Braket to find large independent sets of graphs. In summary, our scheme achieves results comparable to classical heuristics, such as simulated annealing and greedy algorithms, even with relatively weak quantum resources. Furthermore, enhancing the quality of these quantum resources improves the performance of the algorithms, highlighting the potential of QIRO. Notably, the modular nature of QIRO offers various avenues for modifications, positioning our work as a blueprint for designing a broader class of hybrid quantum-classical algorithms for combinatorial optimization.

17 pages, 10 figures. Revised Figs. 1 and 2. Accepted version

References in corpus (1)

• Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods

Cited by in corpus (13)

• Challenges and Opportunities in Quantum Optimization
• Quantum Computing Dataset of Maximum Independent Set Problem on King's Lattice of over Hundred Rydberg Atoms
• Transfer learning of optimal QAOA parameters in combinatorial optimization
• MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA
• Mantra: Rewriting Quantum Programs to Minimize Trap-Movements for Zoned Rydberg Atom Arrays
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Hardness-dependent quantum adiabatic schedules for the maximum-independent-set problem
• Generation of quantum phases of matter and finding a maximum-weight independent set of unit-disk graphs using Rydberg atoms
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem
• Qubit-efficient quantum combinatorial optimization solver
• A Quantum Constraint Generation Framework for Binary Linear Programs
• Multiclass Portfolio Optimization via Variational Quantum Eigensolver with Dicke State Ansatz