EUVIMEDEUVIMED entdecken
Crossref

Iterative quantum algorithms for maximum independent set

Lucas T. Brady, Stuart Hadfield

Physical Review A · 25.11.2024 · 110 (5)

DOI: 10.1103/physreva.110.052435 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Physical Review A, online erschienen am 25.11.2024. Verfasst von Lucas T. Brady und 1 weiteren Autor:innen. Die Arbeit wurde bisher 18-mal zitiert (Crossref) und nennt 44 Literaturangaben. Gefördert von: National Aeronautics and Space Administration, Defense Advanced Research Projects Agency, Ames Research Center.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Quantum algorithms have been widely studied in the context of combinatorial optimization problems. While this endeavor can often analytically and practically achieve quadratic speedups, theoretical and numeric studies remain limited, especially compared to the study of classical algorithms. We propose and study a new class of hybrid approaches to quantum optimization, termed Iterative Quantum Algorithms, which in particular generalizes the Recursive Quantum Approximate Optimization Algorithm. This paradigm can incorporate hard problem constraints, which we demonstrate by considering the Maximum Independent Set (MIS) problem. We show that, for QAOA with depth $p=1$, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS. We then turn to deeper $p>1$ circuits and other ways to modify the quantum algorithm that can no longer be easily mimicked by classical algorithms, and empirically confirm improved performance. Our work demonstrates the practical importance of incorporating proven classical techniques into more effective hybrid quantum-classical algorithms.

Förderung

  • National Aeronautics and Space Administration
  • Defense Advanced Research Projects Agency
  • Ames Research Center

Zitieren

APA

Brady, L. T., & Hadfield, S. (2024). Iterative quantum algorithms for maximum independent set. Physical Review A, 110(5). https://doi.org/10.1103/physreva.110.052435

Vancouver

Brady LT, Hadfield S. Iterative quantum algorithms for maximum independent set. Physical Review A. 2024;110(5). doi:10.1103/physreva.110.052435

BibTeX
@article{Brady2024,
  author = {Brady, Lucas T. and Hadfield, Stuart},
  title = {Iterative quantum algorithms for maximum independent set},
  journal = {Physical Review A},
  year = {2024},
  volume = {110},
  number = {5},
  doi = {10.1103/physreva.110.052435}
}
Kostenlos starten →