Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
read the original abstract
The Quantum Approximate Optimization Algorithm (QAOA) is a promising approach for programming a near-term gate-based hybrid quantum computer to find good approximate solutions of hard combinatorial problems. However, little is currently know about the capabilities of QAOA, or of the difficulty of the requisite parameters optimization. Here, we study the performance of QAOA on the MaxCut combinatorial optimization problem, optimizing the quantum circuits on a classical computer using automatic differentiation and stochastic gradient descent, using QuantumFlow, a quantum circuit simulator implemented with TensorFlow. We find that we can amortize the training cost by optimizing on batches of problems instances; that QAOA can exceed the performance of the classical polynomial time Goemans-Williamson algorithm with modest circuit depth, and that performance with fixed circuit depth is insensitive to problem size. Moreover, MaxCut QAOA can be efficiently implemented on a gate-based quantum computer with limited qubit connectivity, using a qubit swap network. These observations support the prospects that QAOA will be an effective method for solving interesting problems on near-term quantum computers.
This paper has not been read by Pith yet.
Forward citations
Cited by 13 Pith papers
-
SAFE ma-QAOA: Surrogate-Assisted and Fine-Tuning Enhanced Multi-Angle QAOA with Parameter Distillation
SAFE ma-QAOA achieves 64.3% fewer active parameters and 94.5% lower estimated QPU workload via surrogate pre-training and parameter distillation on Sherrington-Kirkpatrick, 2D spin glass, and Max-Cut instances.
-
Beyond Single Trajectories: Optimal Control and Jordan-Lie Algebra in Hybrid Quantum Walks for Combinatorial Optimization
Hybrid quantum walks with optimal dynamical coin operators outperform QAOA on Max-Cut and MIS by accessing a strictly larger Jordan-Lie algebra that enables faster convergence and higher accuracy.
-
Nonvariational quantum optimisation approaches to pangenome-guided sequence assembly
Iterative-QAOA solves pangenome assembly instances on current quantum hardware by using a fixed-ramp QAOA schedule with warm-start updates and a new HUBO encoding that cuts variables from O(N^{2}) to O(N log N).
-
RFOX (Rotated-Field Oscillatory eXchange) quantum algorithm: Towards Parameter-Free Quantum Optimizers
RFOX keeps the instantaneous spectral gap flat across interpolation and disorder by using a constant XX catalyst plus derived ZX counter-diabatic drive, yielding faster ground-state convergence on small RFIM instances.
-
The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
The paper decomposes dynamical Lie algebras of XY-mixer topologies and demonstrates warm-starting QAOA via pre-training on restricted generators to improve convergence on constrained optimization problems.
-
Quantum Hypergraph Partitioning
Balanced k-way hypergraph partitioning is cast as QUBO and higher-order binary problems for quantum optimization, with small-instance tests confirming effectiveness for the all-or-nothing cut on 3-uniform hypergraphs.
-
Demonstrating Record Fidelity for the Quantum Fourier Transform
Parity Architecture delivers record ~0.01 fidelity for 50-qubit QFT on IBM hardware with super-exponential scaling improvement.
-
RFOX (Rotated-Field Oscillatory eXchange) quantum algorithm: Towards Parameter-Free Quantum Optimizers
RFOX maintains a flat spectral gap via non-stoquastic XX catalyst plus analytic counter-diabatic ZX driving, yielding near-optimal solutions on random-field Ising models with up to 10x fewer Trotter steps.
-
Per-Shot Evaluation of QAOA on Max-Cut: A Black-Box Implementation Comparison with Goemans-Williamson
QAOA with default parameters is compared per-shot to Goemans-Williamson on realistic Max-Cut instances, highlighting practical limitations under black-box use.
-
Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
Systematic numerical study of QAOA parameter transfer on heavy-hex Ising models with local cubic terms shows transferred angles from small instances yield improving expectation values up to 49 layers on instances up t...
-
Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits
Noise characteristics of superconducting qubits bound the optimal QAOA depth, contrary to the expectation that higher depth always improves performance.
-
Gate Freezing Method for Gradient-Free Variational Quantum Algorithms in Circuit Optimization
A gate freezing method improves convergence of gradient-free optimizers Rotosolve, Fraxis, and FQS for parameterized quantum circuits by reallocating resources to poorly optimized gates using previous iteration information.
-
The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
A synthesis of expert insights from the ADAC Quantum Computing Working Group and member survey on the complementary roles of quantum and classical high-performance computing in future hybrid infrastructures.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.