Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , , , , , , , , , , , , , , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909214227562496 |
|---|---|
| author | Shaydulin, Ruslan Li, Changhao Chakrabarti, Shouvanik DeCross, Matthew Herman, Dylan Kumar, Niraj Larson, Jeffrey Lykov, Danylo Minssen, Pierre Sun, Yue Alexeev, Yuri Dreiling, Joan M. Gaebler, John P. Gatterman, Thomas M. Gerber, Justin A. Gilmore, Kevin Gresh, Dan Hewitt, Nathan Horst, Chandler V. Hu, Shaohan Johansen, Jacob Matheny, Mitchell Mengle, Tanner Mills, Michael Moses, Steven A. Neyenhuis, Brian Siegfried, Peter Yalovetzky, Romina Pistoia, Marco |
| author_facet | Shaydulin, Ruslan Li, Changhao Chakrabarti, Shouvanik DeCross, Matthew Herman, Dylan Kumar, Niraj Larson, Jeffrey Lykov, Danylo Minssen, Pierre Sun, Yue Alexeev, Yuri Dreiling, Joan M. Gaebler, John P. Gatterman, Thomas M. Gerber, Justin A. Gilmore, Kevin Gresh, Dan Hewitt, Nathan Horst, Chandler V. Hu, Shaohan Johansen, Jacob Matheny, Mitchell Mengle, Tanner Mills, Michael Moses, Steven A. Neyenhuis, Brian Siegfried, Peter Yalovetzky, Romina Pistoia, Marco |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_02342 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem Shaydulin, Ruslan Li, Changhao Chakrabarti, Shouvanik DeCross, Matthew Herman, Dylan Kumar, Niraj Larson, Jeffrey Lykov, Danylo Minssen, Pierre Sun, Yue Alexeev, Yuri Dreiling, Joan M. Gaebler, John P. Gatterman, Thomas M. Gerber, Justin A. Gilmore, Kevin Gresh, Dan Hewitt, Nathan Horst, Chandler V. Hu, Shaohan Johansen, Jacob Matheny, Mitchell Mengle, Tanner Mills, Michael Moses, Steven A. Neyenhuis, Brian Siegfried, Peter Yalovetzky, Romina Pistoia, Marco Quantum Physics Statistical Mechanics Emerging Technologies 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. |
| title | Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem |
| topic | Quantum Physics Statistical Mechanics Emerging Technologies |
| url | https://arxiv.org/abs/2308.02342 |