Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem
Science Advances · 31.05.2024 · 10 (22)
DOI: 10.1126/sciadv.adm6761 ↗Kurz gefasst
Fachartikel in der Zeitschrift Science Advances, erschienen am 31.05.2024. Verfasst von Ruslan Shaydulin und 28 weiteren Autor:innen. Beteiligte Einrichtung: Global Technology Applied Research, JPMorgan Chase, New York, NY 10017, USA. Die Arbeit wurde bisher 134-mal zitiert (Crossref) und nennt 90 Literaturangaben. Der Volltext ist frei in PubMed Central verfügbar.
Abstract (Originalsprache)
The quantum approximate optimization algorithm (QAOA) is a leading candidate algorithm for solving optimization problems on quantum computers. However, the potential of QAOA to tackle classically intractable problems remains unclear. Here, we perform an extensive numerical investigation of QAOA on the low autocorrelation binary sequences (LABS) problem, which is classically intractable even for moderately sized instances. We perform noiseless simulations with up to 40 qubits and observe that the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers, which are the state-of-the-art exact solvers for LABS. The combination of QAOA with quantum minimum finding gives the best empirical scaling of any algorithm for the LABS problem. We demonstrate experimental progress in executing QAOA for the LABS problem using an algorithm-specific error detection scheme on Quantinuum trapped-ion processors. Our results provide evidence for the utility of QAOA as an algorithmic component that enables quantum speedups.
Autor:innen und Institutionen
- Global Technology Applied Research, JPMorgan Chase, New York, NY 10017, USA.
- Quantinuum, Broomfield, CO 80021, USA.
- Mathematics and Computer Science Division, Argonne National Laboratory, Lemont, IL 60439, USA.
- Computational Science Division, Argonne National Laboratory, Lemont, IL 60439, USA.
ORCID-Profile: Ruslan Shaydulin, Changhao Li, Matthew DeCross, Dylan Herman, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun, Yuri Alexeev, Joan M Dreiling, John P Gaebler, Thomas M Gatterman, Justin A Gerber, Kevin Gilmore, Nathan Hewitt, Chandler V Horst, Shaohan Hu, Mitchell Matheny, Michael Mills, Steven A Moses, Peter Siegfried, Romina Yalovetzky, Marco Pistoia
Zitieren
APA
Shaydulin, R., Li, C., Chakrabarti, S., DeCross, M., Herman, D., Kumar, N., Larson, J., Lykov, D., Minssen, P., Sun, Y., Alexeev, Y., Dreiling, J. M., Gaebler, J. P., Gatterman, T. M., Gerber, J. A., Gilmore, K., Gresh, D., Hewitt, N., Horst, C. V., …, & Pistoia, M. (2024). Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem. Science Advances, 10(22). https://doi.org/10.1126/sciadv.adm6761
Vancouver
Shaydulin R, Li C, Chakrabarti S, DeCross M, Herman D, Kumar N, et al. Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem. Science Advances. 2024;10(22). doi:10.1126/sciadv.adm6761
BibTeX
@article{Shaydulin2024,
author = {Shaydulin, Ruslan and Li, Changhao and Chakrabarti, Shouvanik and DeCross, Matthew and Herman, Dylan and Kumar, Niraj and Larson, Jeffrey and Lykov, Danylo and Minssen, Pierre and Sun, Yue and Alexeev, Yuri and Dreiling, Joan M and Gaebler, John P and Gatterman, Thomas M and Gerber, Justin A and Gilmore, Kevin and Gresh, Dan and Hewitt, Nathan and Horst, Chandler V and Hu, Shaohan and Johansen, Jacob and Matheny, Mitchell and Mengle, Tanner and Mills, Michael and Moses, Steven A and Neyenhuis, Brian and Siegfried, Peter and Yalovetzky, Romina and Pistoia, Marco},
title = {Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem},
journal = {Science Advances},
year = {2024},
volume = {10},
number = {22},
doi = {10.1126/sciadv.adm6761}
}
EUVIMED