Reinforcement Learning Assisted Recursive QAOA

Abstract

Variational quantum algorithms such as the Quantum Approximation Optimization Algorithm (QAOA) in recent years have gained popularity as they provide the hope of using NISQ devices to tackle hard combinatorial optimization problems. It is, however, known that at low depth, certain locality constraints of QAOA limit its performance. To go beyond these limitations, a non-local variant of QAOA, namely recursive QAOA (RQAOA), was proposed to improve the quality of approximate solutions. The RQAOA has been studied comparatively less than QAOA, and it is less understood, for instance, for what family of instances it may fail to provide high quality solutions. However, as we are tackling $\mathsf{NP}$-hard problems (specifically, the Ising spin model), it is expected that RQAOA does fail, raising the question of designing even better quantum algorithms for combinatorial optimization. In this spirit, we identify and analyze cases where RQAOA fails and, based on this, propose a reinforcement learning enhanced RQAOA variant (RL-RQAOA) that improves upon RQAOA. We show that the performance of RL-RQAOA improves over RQAOA: RL-RQAOA is strictly better on these identified instances where RQAOA underperforms, and is similarly performing on instances where RQAOA is near-optimal. Our work exemplifies the potentially beneficial synergy between reinforcement learning and quantum (inspired) optimization in the design of new, even better heuristics for hard problems.

17 pages, 6 figures. EPJ Quantum Technology journal version

References in corpus (18)

• Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
• Hartree-Fock on a superconducting qubit quantum computer
• Training variational quantum algorithms is NP-hard
• Quantum walks on a programmable two-dimensional 62-qubit superconducting processor
• Hybrid quantum-classical algorithms for approximate graph coloring
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Reinforcement Learning for Many-Body Ground-State Preparation Inspired by Counterdiabatic Driving
• Reinforcement Learning assisted Quantum Optimization
• Using models to improve optimizers for variational quantum algorithms
• Empirical performance bounds for quantum approximate optimization
• Low depth mechanisms for quantum optimization
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems
• Quantum-Informed Recursive Optimization Algorithms
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• Classical algorithms and quantum limitations for maximum cut on high-girth graphs
• Iterative Quantum Algorithms for Maximum Independent Set: A Tale of Low-Depth Quantum Algorithms
• Unsupervised strategies for identifying optimal parameters in Quantum Approximate Optimization Algorithm

Cited by in corpus (7)

• KANQAS: Kolmogorov-Arnold Network for Quantum Architecture Search
• Quantum Computing and Tensor Networks for Laminate Design: A Novel Approach to Stacking Sequence Retrieval
• Application of quantum-inspired generative models to small molecular datasets
• Reinforcement learning with learned gadgets to tackle hard quantum problems on real hardware
• Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem