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.

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

References in corpus (22)

• Ising formulations of many NP problems
• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• Quantum Annealing in the Transverse Ising Model
• Parallel Tempering: Theory, Applications, and New Perspectives
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Perspectives of quantum annealing: Methods and implementations
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Training variational quantum algorithms is NP-hard
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Coherent quantum annealing in a programmable 2000-qubit Ising chain
• Hyper-optimized tensor network contraction
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Hybrid quantum-classical algorithms for approximate graph coloring
• Tropical Tensor Network for Ground States of Spin Glasses
• Low depth mechanisms for quantum optimization
• Progress toward favorable landscapes in quantum combinatorial optimization
• Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
• Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• Computing solution space properties of combinatorial optimization problems via generic tensor networks
• Schedule path optimization for quantum annealing and adiabatic quantum computing
• The ground state energy of the Edwards-Anderson spin glass model with a parallel tempering Monte Carlo algorithm

Cited by in corpus (15)

• Challenges and Opportunities in Quantum Optimization
• Reinforcement Learning Assisted Recursive QAOA
• 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
• Generation of quantum phases of matter and finding a maximum-weight independent set of unit-disk graphs using Rydberg atoms
• Hardness-dependent quantum adiabatic schedules for the maximum-independent-set problem
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
• 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