Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm

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 & LE; 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.

Automated summary

We compared the performance of QAOA with Gurobi and MQLib solvers on solving the MaxCut problem. We found that a quantum device with a minimum noiseless sampling frequency and depth p can outperform classical algorithms. However, classical heuristic solvers can produce high-quality approximate solutions in linear time complexity, while a quantum device needs a depth p > 11 to match this quality for large graph sizes. Multi-shot QAOA is not efficient on large graphs, limiting the quantum advantage of QAOA on 3-regular graphs. Other problems may be more suitable for achieving quantum advantage on near-term quantum devices.