EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Quantum-Informed Recursive Optimization Algorithms

Jernej Rudi Finžgar, Aron Kerschbaumer, Martin J.A. Schuetz, Christian B. Mendl, Helmut G. Katzgraber

PRX Quantum · 03.05.2024 · 5 (2)

DOI: 10.1103/prxquantum.5.020327 ↗

Kurz gefasst

Fachartikel in der Zeitschrift PRX Quantum, online erschienen am 03.05.2024. Verfasst von Jernej Rudi Finžgar und 4 weiteren Autor:innen. Die Arbeit wurde bisher 42-mal zitiert (Crossref) und nennt 41 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Hightech Agenda Bayern Plus.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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. Published by the American Physical Society 2024

Förderung

  • Hightech Agenda Bayern Plus

Zitieren

APA

Finžgar, J. R., Kerschbaumer, A., Schuetz, M. J., Mendl, C. B., & Katzgraber, H. G. (2024). Quantum-Informed Recursive Optimization Algorithms. PRX Quantum, 5(2). https://doi.org/10.1103/prxquantum.5.020327

Vancouver

Finžgar JR, Kerschbaumer A, Schuetz MJ, Mendl CB, Katzgraber HG. Quantum-Informed Recursive Optimization Algorithms. PRX Quantum. 2024;5(2). doi:10.1103/prxquantum.5.020327

BibTeX
@article{Fingar2024,
  author = {Finžgar, Jernej Rudi and Kerschbaumer, Aron and Schuetz, Martin J.A. and Mendl, Christian B. and Katzgraber, Helmut G.},
  title = {Quantum-Informed Recursive Optimization Algorithms},
  journal = {PRX Quantum},
  year = {2024},
  volume = {5},
  number = {2},
  doi = {10.1103/prxquantum.5.020327}
}
Kostenlos starten →