Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm

Abstract

In this work, we compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers such as Gurobi and MQLib to solve the combinatorial optimization problem MaxCut on 3-regular graphs. The goal is to identify under which conditions QAOA can achieve "quantum advantage" over classical algorithms, in terms of both solution quality and time to solution. One might be able to achieve quantum advantage on hundreds of qubits and moderate depth $p$ by sampling the QAOA state at a frequency of order 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 $\text{large}$ graph sizes $N$, a quantum device must support depth $p>11$. Otherwise, we demonstrate that the number of required samples grows exponentially with $N$, hindering the scalability of QAOA with $p\le 11$. These results put challenging bounds on achieving quantum advantage for QAOA MaxCut on 3-regular graphs. Other problems, such as different graphs, weighted MaxCut, maximum independent set, and 3-SAT, may be better suited for achieving quantum advantage on near-term quantum devices.

References in corpus (26)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Simulating quantum computation by contracting tensor networks
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Warm-starting quantum optimization
• Quantum Computer Systems for Scientific Discovery
• Hyper-optimized tensor network contraction
• 0.5 Petabyte Simulation of a 45-Qubit Quantum Circuit
• Full-State Quantum Circuit Simulation by Using Data Compression
• Counterdiabaticity and the quantum approximate optimization algorithm
• MAXCUT QAOA performance guarantees for p >1
• Multistart Methods for Quantum Approximate Optimization
• Progress toward favorable landscapes in quantum combinatorial optimization
• Exploiting Symmetry Reduces the Cost of Training QAOA
• Evaluation of QAOA based on the approximation ratio of individual samples
• Solving optimization problems with Rydberg analog quantum computers: Realistic requirements for quantum advantage using noisy simulation and classical benchmarks
• QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
• An adaptive algorithm for quantum circuit simulation
• Performance Evaluation and Acceleration of the QTensor Quantum Circuit Simulator on GPUs
• Embedding Learning in Hybrid Quantum-Classical Neural Networks
• Classical algorithms and quantum limitations for maximum cut on high-girth graphs
• Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization

Cited by in corpus (18)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Early Fault-Tolerant Quantum Computing
• Fast Simulation of High-Depth QAOA Circuits
• Demonstration of weighted graph optimization on a Rydberg atom array using local light-shifts
• Stochastic noise can be helpful for variational quantum algorithms
• Performance Analysis of Multi-Angle QAOA for p > 1
• Symmetry-informed transferability of optimal parameters in the Quantum Approximate Optimization Algorithm
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
• Optimized Noise Suppression for Quantum Circuits
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Deep-Circuit QAOA
• Optimization via Quantum Preconditioning
• Generation of quantum phases of matter and finding a maximum-weight independent set of unit-disk graphs using Rydberg atoms
• Approximate Quadratization of High-Order Hamiltonians for Combinatorial Quantum Optimization
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Investigating layer-selective transfer learning of QAOA parameters for Max-Cut problem
• Quantum imaginary time evolution and UD-MIS problem