Research Replication
QAOA MaxCut: Distributions, Landscapes and Optimization
Compare analytical settings, a parameter landscape and a classical optimization loop on three small graphs, keeping cut fractions and approximation ratios distinct.
Historical local simulator results · Public package pending
What distribution of graph cuts does one-layer QAOA produce, and how does its mean compare with graph-specific predictions and the exact optimum?
Source paper: Farhi, Goldstone and Gutmann, A Quantum Approximate Optimization Algorithm (2014).
What this replication investigates
This reference explores p = 1 QAOA on the triangle, square and Petersen graphs, using fixed analytical settings, a two-parameter landscape and a classical optimization loop respectively.
These selected local simulator cases illustrate the method and its comparisons. They are not a proof of the general approximation theorem, a hardware study or evidence of an advantage over classical optimization.
Method and parameters
- Prepare candidate bit strings with one cost layer and one mixing layer, then score each sampled partition by its cut size.
- Use 2,048 shots per measured circuit, and exact brute-force optimum cut sizes for the small graph comparisons.
- Evaluate fixed triangle angles, sweep the square’s parameter grid, and optimize Petersen angles with COBYLA.
- Report mean cut, mean divided by edge count, and mean divided by the optimum separately. Account for parameter selection when constructing sampling intervals.
Results and comparison
Scroll the table horizontally to see every results column.
| Graph / mode | Mean cut | Mean / edges | Mean / optimum |
|---|---|---|---|
| Triangle / fixed | 2.0000 | 0.6667 | 1.0000 |
| Square / landscape | 3.0391 | 0.7598 | 0.7598 |
| Petersen / optimize | 10.3486 | 0.6899 | 0.8624 |
For the triangle, square and Petersen instances, the corresponding ideal p = 1 mean cuts are 2, 3 and approximately 10.3867513. All three predictions lie within the reference’s conservative 95% bounded-sampling intervals.
All three saved runs sampled an optimal partition, but that does not make their distribution means optimal. Petersen’s best observed cut is 12, while its mean is 10.3486.
On triangle-free 3-regular graphs, the optimized ideal p = 1 edge fraction is 1/2 + 1/(3√3). On Petersen it implies an approximation ratio of about 0.86556. The paper’s separate rounded 0.6924 worst-case guarantee is relative to the optimum; neither cubic statement applies to our triangle or square.
What the evidence establishes
The evidence is preserved historical local simulator output, not current hosted jobs. Report preparation reconstructs graph scores, histogram metrics, uncertainty bounds and optimizer counts from those inputs.
Square’s interval accounts for selection across 862 measured circuits. Petersen’s final interval assumes fresh independent shots after angle selection. These are sampling comparisons, not certificates of global optimization or hardware performance.
Limitations
- Saved results lack a recorded seed, authenticated job IDs and immutable execution provenance. Source-input hashes identify preparation inputs, not historical execution.
- The old Petersen ratio threshold of 0.69 was a weak sanity check, not validation of its graph-specific prediction.
- Zero empirical variance in the triangle sample does not prove zero uncertainty for future shots.
- Sampling bounds omit systematic backend error. Optimizer success indicates a stopping condition, not a guaranteed optimum.
Access and reproduction
The original algorithm paper and this scoped results overview are public. Current hosted execution, a sealed public Capsule and a receiving-team reproduction remain separate qualification steps.
The experiment's source package and runnable Capsule are not yet public. This page describes the scoped reference and its evidence; it does not provide a one-click reproduction.
Learning example or research replication?
There is currently no matching QAOA MaxCut snippet in the editor’s twelve-example catalog. Those learning circuits introduce state preparation and gates; this reference adds a graph objective, parameter search and a scientific comparison. Opening an unrelated editor example will not reproduce these results.
Explore the smaller learning circuits →
For a smaller local workflow with new teaching samples, follow the separate QAOA MaxCut: Tune a Four-Qubit Circuit learning tutorial. It does not reproduce the retained results above.
Explore the research collection →
References
- Farhi, Goldstone and Gutmann: A Quantum Approximate Optimization Algorithm (2014)
- Wang and colleagues: Quantum Approximate Optimization Algorithm for MaxCut — A Fermionic View
Scientific scope and retained results reviewed with the Marqov Replications project on October 16, 2026. Each reference is a separate experiment from the editor's learning examples.