Quantum-Informed Recursive Optimization: A Promising Hybrid Quantum-Classical Algorithm for Combinatorial Optimization

Quantum-Informed Recursive Optimization (QIRO) is a new family of hybrid quantum-classical algorithms developed by researchers from BMW AG Munich, Amazon Quantum Solutions Lab, and Technical University of Munich. QIRO is designed for combinatorial optimization problems, using quantum resources to simplify the problem recursively.

The team demonstrated QIRO’s capabilities by solving instances of maximum independent set and maximum satisfiability problems with hundreds of variables. The algorithm’s performance is comparable to classical heuristics and can be improved with enhanced quantum resources. The research represents a significant advancement in quantum optimization and provides a template for future hybrid quantum-classical algorithms.

What is Quantum-Informed Recursive Optimization (QIRO)?

Quantum-Informed Recursive Optimization (QIRO) is a family of hybrid quantum-classical algorithms proposed by a team of researchers from BMW AG Munich, Department of Computer Science Technical University Munich School of CIT Garching, Amazon Quantum Solutions Lab, AWS Center for Quantum Computing, and Technical University of Munich Institute for Advanced Study. The team includes Jernej Rudi Finžgar, Aron Kerschbaumer, Martin JA Schuetz, Christian B Mendl, and Helmut G Katzgraber. The research was received on 21 September 2023, accepted on 21 February 2024, and published on 3 May 2024.

QIRO algorithms are designed for combinatorial optimization problems. The approach uses quantum resources to obtain information that is then used in problem-specific classical reduction steps that recursively simplify the problem. These reduction steps address the limitations of the quantum component, such as locality, and ensure solution feasibility in constrained optimization problems. The team also uses backtracking techniques to further improve the performance of the algorithm without increasing the requirements on the quantum hardware.

The team showcased the capabilities of QIRO by informing it with correlations from classical simulations of shallow circuits of the quantum approximate optimization algorithm. They solved instances of maximum independent set and maximum satisfiability problems with hundreds of variables. They also demonstrated how QIRO can be deployed on a neutral atom quantum processor to find large independent sets of graphs.

How Does QIRO Compare to Classical Heuristics?

The team’s scheme achieves results comparable to classical heuristics, even with relatively weak quantum resources. Enhancing the quality of these quantum resources improves the performance of the algorithms. The modular nature of QIRO offers various avenues for modifications, positioning the team’s work as a template for a broader class of hybrid quantum-classical algorithms for combinatorial optimization.

Quantum optimization has been identified as a promising area of research towards practical quantum advantage. On noisy intermediate-scale quantum (NISQ) devices, much effort has been dedicated to studying hybrid quantum-classical algorithms such as the quantum approximate optimization algorithm (QAOA). QAOA is a local algorithm, meaning that at any constant circuit depth, only qubits that are separated by less than a certain distance in the interaction graph of the optimization problem are able to communicate.

What are the Limitations of QAOA and How Does QIRO Address Them?

Locality was shown to severely limit the performance of QAOA. Because introducing nonlocal updates in quantum algorithms comes with additional hardware requirements, applying nonlocal updates classically has been proposed as an alternative in recursive QAOA (RQAOA). Here, values of variables are iteratively frozen by rounding the correlations between variables as measured in the quantum state prepared by QAOA. As variables are removed from the optimization problem, the distances between nodes in the interaction graph are reduced iteratively. The nonlocal effects introduced via the new connections between previously unconnected nodes counterbalance the locality inherent to QAOA.

Building upon RQAOA, QIRO uses information generated by quantum resources to recursively reduce the size of the optimization problem by means of problem-specific classical optimization routines. This scheme allows the team to leverage decades of research in classical combinatorial optimization and tailor the classical subroutines to the particular optimization problem of interest, thereby enhancing the algorithm’s performance.

How Does QIRO Broaden the Scope of Quantum Algorithms?

The inclusion of problem-specific update rules in QIRO allows the team to broaden the scope of their algorithm beyond gate-based architectures to analog devices. This approach is reminiscent of previous approaches leveraging spin-freezing schemes on quantum annealers and in various Monte Carlo methods. For problems with hard constraints, the update rules can offer options to enforce feasibility by design, even in the presence of noise.

The team also proposes backtracking as a strategy to further improve the performance of QIRO by attempting to identify and correct nonideal decisions made at earlier stages of the algorithm. Backtracking provides a way to enhance algorithmic performance without necessitating an increase in circuit depth, as is commonplace in quantum optimization algorithms.

What is the Future of QIRO?

The robustness of QIRO, its ability to be deployed on a neutral atom quantum processor, and its potential for further modifications position it as a promising tool for a broader class of hybrid quantum-classical algorithms for combinatorial optimization. As quantum resources continue to improve, so too will the performance of QIRO and similar algorithms. This research represents a significant step forward in the field of quantum optimization, and the team’s work serves as a template for future developments in this area.