A Unified Framework for Two Quantum Approaches to Combinatorial Optimization

A study conducted by Ruho Kondo et al. in collaboration with Keio University and the University of Tokyo, was published in Quantum.

Combinatorial optimization problems, such as transportation planning and scheduling, become increasingly difficult to solve as the number of variables grows, due to the so-called “combinatorial explosion.” Quantum algorithms offer a promising approach to tackling these problems by leveraging quantum properties such as superposition and interference. Among quantum optimization methods, the Recursive Quantum Approximate Optimization Algorithm (RQAOA), which reduces the problem size step-by-step, has shown strong performance. However, its theoretical foundation has remained incomplete. Another promising method, based on Quantum Random Access Codes (QRACs), enables large-scale problems to be addressed with fewer qubits, but the relationship between arbitrary quantum states and solutions had not been fully clarified.

In this study, we investigated both Recursive QAOA and QRAC-based optimization, shedding light on their unresolved theoretical aspects. We demonstrated that, despite differing in approximation level, both methods can be unified under the same mathematical formulation. We further introduced a novel heuristic tailored to this unified framework and confirmed through simulations that it can outperform existing quantum optimization methods and classical algorithms with approximation guarantees. This work contributes to the development of efficient quantum optimization techniques, with potential applications in transportation, finance, and machine learning.

Title: Recursive Quantum Relaxation for Combinatorial Optimization Problems
Authors: Kondo, R., Sato, Y., Raymond, R., Yamamoto, N.
Journal Name: Quantum
Published: January 15, 2025
https://doi.org/10.22331/q-2025-01-15-1594