Threshold for Fault-tolerant Quantum Advantage with the Quantum Approximate Optimization Algorithm
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912305968578560 |
|---|---|
| author | Omanakuttan, Sivaprasad He, Zichang Zhang, Zhiwei Hao, Tianyi Babakhani, Arman Boulebnane, Sami Chakrabarti, Shouvanik Herman, Dylan Sullivan, Joseph Perlin, Michael A. Shaydulin, Ruslan Pistoia, Marco |
| author_facet | Omanakuttan, Sivaprasad He, Zichang Zhang, Zhiwei Hao, Tianyi Babakhani, Arman Boulebnane, Sami Chakrabarti, Shouvanik Herman, Dylan Sullivan, Joseph Perlin, Michael A. Shaydulin, Ruslan Pistoia, Marco |
| contents | Optimization is often cited as a promising application of quantum computers. However, the low degree of provable quantum speedups has led prior rigorous end-to-end resource analyses to conclude that a quantum computer is unlikely to surpass classical state-of-the-art on optimization problems under realistic assumptions. In this work, we compile and analyze the Quantum Approximate Optimization Algorithm (QAOA) combined with Amplitude Amplification (AA) applied to random 8-SAT at the satisfiability threshold. Our compilation involves careful optimization of circuits for Hamiltonian simulation, which may be of independent interest. We use the analytical scaling of the time-to-solution for QAOA identified by PRX Quantum 5, 030348 (2024) and find that with QAOA depth $p=623$, QAOA+AA achieves a crossover with state-of-the-art classical heuristics at 179 variables and 14.99 hours of runtime when executed on a surface-code-based fault-tolerant quantum computer with 73.91 million physical qubits, a physical error rate of $10^{-3}$, and a $1~μ$s code cycle time. Notably, we allow the classical solver to be parallelized as long as its total energy consumption is equal to that required for decoding in the surface code. We further show that this restriction on classical solver energy consumption can be relaxed given optimistic but plausible reductions in physical error rates and fault-tolerance overheads, enabling a crossover of 2.94 hours using 8.88 million physical qubits against a classical solver running on a supercomputer with $725,760$ CPU cores. These findings support the hypothesis that large-scale fault-tolerant quantum computers will be useful for optimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_01897 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Threshold for Fault-tolerant Quantum Advantage with the Quantum Approximate Optimization Algorithm Omanakuttan, Sivaprasad He, Zichang Zhang, Zhiwei Hao, Tianyi Babakhani, Arman Boulebnane, Sami Chakrabarti, Shouvanik Herman, Dylan Sullivan, Joseph Perlin, Michael A. Shaydulin, Ruslan Pistoia, Marco Quantum Physics Optimization is often cited as a promising application of quantum computers. However, the low degree of provable quantum speedups has led prior rigorous end-to-end resource analyses to conclude that a quantum computer is unlikely to surpass classical state-of-the-art on optimization problems under realistic assumptions. In this work, we compile and analyze the Quantum Approximate Optimization Algorithm (QAOA) combined with Amplitude Amplification (AA) applied to random 8-SAT at the satisfiability threshold. Our compilation involves careful optimization of circuits for Hamiltonian simulation, which may be of independent interest. We use the analytical scaling of the time-to-solution for QAOA identified by PRX Quantum 5, 030348 (2024) and find that with QAOA depth $p=623$, QAOA+AA achieves a crossover with state-of-the-art classical heuristics at 179 variables and 14.99 hours of runtime when executed on a surface-code-based fault-tolerant quantum computer with 73.91 million physical qubits, a physical error rate of $10^{-3}$, and a $1~μ$s code cycle time. Notably, we allow the classical solver to be parallelized as long as its total energy consumption is equal to that required for decoding in the surface code. We further show that this restriction on classical solver energy consumption can be relaxed given optimistic but plausible reductions in physical error rates and fault-tolerance overheads, enabling a crossover of 2.94 hours using 8.88 million physical qubits against a classical solver running on a supercomputer with $725,760$ CPU cores. These findings support the hypothesis that large-scale fault-tolerant quantum computers will be useful for optimization. |
| title | Threshold for Fault-tolerant Quantum Advantage with the Quantum Approximate Optimization Algorithm |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2504.01897 |