Quantum approximate optimization of non-planar graph problems on a planar superconducting processor
Harrigan et al. — Nature Physics 17, 332-336 (2021)
In Plain Language
What this paper does: This Google paper tests QAOA (Quantum Approximate Optimization Algorithm) on a real problem: MaxCut, where the goal is to divide a network into two groups to maximize the connections between them. It ran on Google's Sycamore processor with 23 qubits.
Why it matters: Optimization is one of the most promising near-term applications of quantum computing. This paper tested whether QAOA can actually beat random guessing on real hardware — a prerequisite for any practical quantum advantage in optimization.
Our scope: Small-scale reproduction. The original ran 3-23 qubit instances on 53-qubit Sycamore. We ran 3-6 qubit instances on Tuna-9 (9 qubits), mostly on emulator. The algorithm works, but we didn't test the larger instances that were the paper's main result.
What we found: All 4 claims reproduced at our scale. Tuna-9 achieved a 74.1% approximation ratio on the 9-node problem — matching the qualitative behavior of the original Google results. The algorithm finds better-than-random solutions on real hardware.
Key Terms
QAOA—Quantum Approximate Optimization Algorithm — a hybrid algorithm that alternates quantum and classical steps to find approximate solutions to optimization problems
MaxCut—A graph problem: divide nodes into two groups to maximize edges between groups. Used as a standard benchmark for optimization algorithms
Approximation ratio—How close the quantum solution is to the best possible solution. 100% = optimal. Random guessing on MaxCut gives ~50%
Backends Tested
Failure Modes
Claim-by-Claim Comparison
Each claim from the paper is tested on multiple quantum backends. Published values are compared against our measurements.
QAOA MaxCut at p=1 achieves approximation ratio > 0.5 (random)
| Backend | Measured | Discrepancy | Status |
|---|---|---|---|
| QI Emulator | Yes | match | PASS |
QAOA performance improves from p=1 to p=2
| Backend | Measured | Discrepancy | Status |
|---|---|---|---|
| QI Emulator | Yes | match | PASS |
SWAP compilation overhead degrades QAOA performance for non-native graphs
| Backend | Measured | Discrepancy | Status |
|---|---|---|---|
| QI Emulator | Yes | match | PASS |
Cross-Backend Summary
| Backend | Claims Tested | Passed | Pass Rate | Primary Issue |
|---|---|---|---|---|
| QI Emulator | 3 | 3 | 100% | -- |
Key Findings
QI Emulator: 3/3 claims matched. The simulation pipeline correctly reproduces the published physics.