Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm
Abstract
We compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers Gurobi and MQLib to solve the MaxCut problem on 3-regular graphs. We identify the minimum noiseless sampling frequency and depth p required for a quantum device to outperform classical algorithms. There is potential for quantum advantage on hundreds of qubits and moderate depth with a sampling frequency of 10 kHz. We observe, however, that classical heuristic solvers are capable of producing high-quality approximate solutions in linear time complexity. In order to match this quality for large graph sizes N, a quantum device must support depth p > 11. Additionally, multi-shot QAOA is not efficient on large graphs, indicating that QAOA p ≤ 11 does not scale with N. These results limit achieving quantum advantage for QAOA MaxCut on 3-regular graphs. Other problems, such as different graphs, weighted MaxCut, and 3-SAT, may be better suited for achieving quantum advantage on near-term quantum devices.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jul 25, 2023
- Source ID
- 10.1038/s41534-023-00718-4
Entities
People
- Cody Poole
- Danylo Lykov
- Jonathan Wurtz
- Mark Saffman
- Thomas Noël
- Yuri Alexeev
Organizations
- United States Department of Defense