Quantum-informed recursive optimization algorithms

Finžgar JR, Kerschbaumer A, Schuetz MJA, Mendl CB, Katzgraber HG. 2024. Quantum-informed recursive optimization algorithms. PRX Quantum. 5(2), 020327.

Download
OA 2024_PRXQuantum_Finzgar.pdf 2.02 MB [Published Version]

Journal Article | Published | English

Scopus indexed
Author
Finžgar, Jernej Rudi; Kerschbaumer, AronISTA; Schuetz, Martin J.A.; Mendl, Christian B.; Katzgraber, Helmut G.

Corresponding author has ISTA affiliation

Department
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 (e.g., locality) 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 showcase the capabilities of our approach by informing QIRO with correlations from classical simulations of shallow circuits of the quantum approximate optimization algorithm, 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 to find large independent sets of graphs. In summary, our scheme achieves results comparable to classical heuristics even with relatively weak quantum resources. Furthermore, enhancing the quality of these quantum resources improves the performance of the algorithms. Notably, the modular nature of QIRO offers various avenues for modifications, positioning our work as a template for a broader class of hybrid quantum-classical algorithms for combinatorial optimization.
Publishing Year
Date Published
2024-05-01
Journal Title
PRX Quantum
Publisher
American Physical Society
Acknowledgement
J.R.F. and A.K. thank Libor Caha and Alexander Kliesch for insightful discussions. The authors thank Lilly Palackal, Maximilian Passek, Carlos Riofrío, and Gili Rosenberg for thorough reviews of the manuscript, and the Amazon Braket, BMW, and QuEra teams for their support. C.M. thanks the Munich Quantum Valley initiative, which is supported by the Bavarian State Government with funds from the Hightech Agenda Bayern Plus. H.G.K. would like to thank Am Platzl 1A for providing the necessary environment for creative thinking. An open-source implementation of QIRO is available online [60].
Volume
5
Issue
2
Article Number
020327
eISSN
IST-REx-ID

Cite this

Finžgar JR, Kerschbaumer A, Schuetz MJA, Mendl CB, Katzgraber HG. Quantum-informed recursive optimization algorithms. PRX Quantum. 2024;5(2). doi:10.1103/PRXQuantum.5.020327
Finžgar, J. R., Kerschbaumer, A., Schuetz, M. J. A., Mendl, C. B., & Katzgraber, H. G. (2024). Quantum-informed recursive optimization algorithms. PRX Quantum. American Physical Society. https://doi.org/10.1103/PRXQuantum.5.020327
Finžgar, Jernej Rudi, Aron Kerschbaumer, Martin J.A. Schuetz, Christian B. Mendl, and Helmut G. Katzgraber. “Quantum-Informed Recursive Optimization Algorithms.” PRX Quantum. American Physical Society, 2024. https://doi.org/10.1103/PRXQuantum.5.020327.
J. R. Finžgar, A. Kerschbaumer, M. J. A. Schuetz, C. B. Mendl, and H. G. Katzgraber, “Quantum-informed recursive optimization algorithms,” PRX Quantum, vol. 5, no. 2. American Physical Society, 2024.
Finžgar JR, Kerschbaumer A, Schuetz MJA, Mendl CB, Katzgraber HG. 2024. Quantum-informed recursive optimization algorithms. PRX Quantum. 5(2), 020327.
Finžgar, Jernej Rudi, et al. “Quantum-Informed Recursive Optimization Algorithms.” PRX Quantum, vol. 5, no. 2, 020327, American Physical Society, 2024, doi:10.1103/PRXQuantum.5.020327.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
Access Level
OA Open Access
Date Uploaded
2024-05-21
MD5 Checksum
76bdf0b4dc06d59d073a57bd6957a96c


Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2308.13607

Search this title in

Google Scholar