Source-linked AI summary
Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
Gavin E. Crooks
TL;DR
The paper examines QAOA for MaxCut amid limited understanding of its performance, resource requirements, and parameter-optimization difficulty. Using classical simulation with automatic differentiation and stochastic gradient descent, it finds that batch training, modest-depth circuits, and swap networks support effective implementations, while evaluation remains limited to small graphs.
Problem
QAOA’s performance, implementation cost, and parameter-optimization difficulty lack general guarantees, while effective algorithms for noisy near-term quantum architectures remain limited.
Method
The paper uses classical simulation with automatic differentiation and stochastic gradient descent to optimize QAOA circuits for MaxCut, including batch training and limited-connectivity implementations.
Results
QAOA’s approximation ratio increases with circuit depth and significantly exceeds Goemans–Williamson by P = 8, while P ≥8 maintains its relative advantage without strong graph-size dependence for Erdős–Rényi graphs.
Takeaways & Limitations
The authors expect QAOA MaxCut to require O(N 2P) gates and O(NP) runtime, with efficient execution despite limited qubit connectivity.
Takeaways & Limitations
Definitive evaluation against state-of-the-art classical heuristics requires graphs with hundreds or thousands of nodes and must await sufficiently capable quantum hardware.
Abstract
from arXiv · showhide
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.