Run QAOA on a small graph with an exhaustive angle grid and compare the expected cut with the exact MaxCut optimum.
Officially provided by KetQat — method by Farhi et al. (2014), Karp (1972) and others. KetQat prepares, verifies and maintains this product; it does not claim to have invented the method. Read the origin statement.
Runs the Quantum Approximate Optimization Algorithm for MaxCut as a statevector simulation on your machine. The graph is a ring, a path, a complete graph or your own edge list; the product prepares the uniform superposition, applies the cost and mixer layers as operators for one or two layers, searches the angles on an exhaustive grid, and reports the best expected cut against the exact optimum found by enumerating every assignment. The final state is sampled with a seed so you also get an observed cut distribution.
On a triangle-free regular graph at one layer, the Farhi-Goldstone-Gutmann closed form for the expected cut is evaluated at the chosen angles and reported beside the simulation, so the two can be compared directly.
The optimiser is a grid rather than a gradient method on purpose: a grid is exhaustive at its resolution, so the reported expectation is a lower bound on what QAOA can reach at that depth, not where a local optimiser happened to stop.
Installs the KetQat SDK from commit 2cedabbd814f, the exact version whose product definition this page shows. The SDK is not on PyPI yet, so pip install ketqat alone will not work.
pip install "ketqat[algorithms] @ git+https://github.com/ketqat/ketqat-sdk@2cedabbd814fd199b1989c8ceb1e9efa1744c2c0#subdirectory=python"Save it as example.py and run python example.py. Or use the CLI: ketqat catalog run [email protected].
import json
from ketqat_runner import catalog
record = catalog.run("[email protected]", seed=7, graph="ring", n_vertices=6, layers=1, shots=1000)
result = record.result
print(json.dumps({
"status": record.status,
"max_cut": result["max_cut"],
"best_expectation": round(result["best_expectation"], 9),
"approximation_ratio": round(result["approximation_ratio"], 9),
"analytic_p1_expectation": round(result["analytic_p1_expectation"], 9),
}))
{
"status": "succeeded",
"max_cut": 6,
"best_expectation": 4.5,
"approximation_ratio": 0.75,
"analytic_p1_expectation": 4.5
}Verified with
ketqat report RUN_ID sends an opt-in usage report: product, version, succeeded/failed, time and SDK version only. It shows you the exact payload first and needs an API token from Settings. Nothing is sent unless you run it.
| Name | Type | Default | Allowed values | Description |
|---|---|---|---|---|
| graph | string | ring | enum: ring, path, complete, custom | ring (cycle on n vertices), path, complete, or custom (give edges). |
| n_vertices | integer | 6 | maximum: 12; minimum: 2 | Number of vertices n, one qubit each; the state vector has 2^n amplitudes. |
| edges | string[] | null | minItems: 1; uniqueItems: true | For graph=custom: edges as 'u-v' strings with vertices in 0..n-1, no self-loops, no repeats. null otherwise. |
| layers | integer | 1 | maximum: 2; minimum: 1 | QAOA depth p: 1 or 2. Each layer adds one beta and one gamma to the grid search. |
| grid | integer | 24 | maximum: 64; minimum: 4 | Grid points per angle: beta in [0, pi) and gamma in [0, 2 pi), so grid^(2p) expectation evaluations. Requests estimated above ~24 s are refused with the estimate. |
| shots | integer | 1000 | maximum: 1000000; minimum: 1 | Measurement samples drawn from the optimised QAOA state. |
| Name | Type | Description |
|---|---|---|
| best_expectation | number | Largest expected cut <C> found on the grid, from the simulated state. |
| max_cut | integer | Exact MaxCut value from enumerating all 2^n assignments, with the optimal assignments listed. |
| approximation_ratio | number | best_expectation / max_cut. |
| best_beta | number[] | Mixer angles of the best grid point (one per layer); best_gamma holds the cost angles. |
| analytic_p1_expectation | number | Farhi-Goldstone-Gutmann closed form at the chosen angles when layers=1 and the graph is triangle-free and regular; null otherwise. |
| probability_of_optimal_cut | number | Exact probability that measuring the optimised state yields an optimal assignment. |
| counts | object | Seeded measurement counts by assignment string (vertex 0 is the rightmost character), with the sampled mean cut and the best sampled cut. |
Ring of 6 vertices, one layer, 24x24 grid: best expected cut 4.5 of the exact maximum 6 (ratio 0.75, the known p=1 ceiling), equal to the Farhi-Goldstone-Gutmann closed form at the chosen angles; an optimal assignment has probability 0.285 and 276 of 1000 seeded shots hit one.
Generated with
{"grid":24,"edges":null,"graph":"ring","shots":1000,"layers":1,"n_vertices":6}{
"grid": 24,
"note": "Ratio is against the exact optimum from enumerating all 64 assignments, not a bound. Angles come from an exhaustive 24x24 grid per layer; a finer grid can only improve the expectation, so this is a lower bound on QAOA's best.",
"graph": {
"kind": "ring",
"edges": [
[
0,
1
],
[
1,
2
],
[
2,
3
],
[
3,
4
],
[
4,
5
],
[
5,
0
]
],
"n_vertices": 6,
"triangle_free": true,
"regular_degree": 2
},
"shots": 1000,
"counts": {
"100010": 12,
"100011": 2,
"100100": 31,
"100101": 35,
"100110": 32,
"101000": 6,
"101001": 38,
"101010": 138,
"101011": 7,
"101100": 43,
"101101": 21,
"101110": 9,
"101111": 3,
"110001": 1,
"110010": 31,
"110100": 36,
"110101": 9,
"110110": 31,
"111010": 8,
"111011": 2,
"111101": 2,
"111110": 1,
"000010": 2,
"000100": 4,
"000101": 4,
"000111": 5,
"001001": 36,
"001010": 6,
"001011": 36,
"001101": 26,
"001110": 5,
"010000": 2,
"010001": 12,
"010010": 36,
"010011": 38,
"010100": 11,
"010101": 138,
"010110": 33,
"010111": 6,
"011001": 30,
"011010": 35,
"011011": 30,
"011100": 1,
"011101": 6
},
"layers": 1,
"max_cut": 6,
"best_beta": [
2.748893571891
],
"bit_order": "vertex 0 is the rightmost character of each assignment string",
"execution": "statevector simulation of the QAOA layers; angles from an exhaustive grid; optimum by enumeration",
"best_gamma": [
2.356194490192
],
"analytic_p1_note": "Farhi-Goldstone-Gutmann p=1 closed form |E| (1/2 + 1/2 sin(4 beta) sin(gamma) cos(gamma)^(d-1)) evaluated at the chosen angles; it holds for triangle-free d-regular graphs.",
"best_expectation": 4.5,
"best_sampled_cut": 6,
"sampled_cut_mean": 4.492,
"analytic_p1_applies": true,
"approximation_ratio": 0.75,
"optimal_assignments": [
"010101",
"101010"
],
"beats_random_guessing": true,
"analytic_p1_expectation": 4.5,
"random_guess_expectation": 3,
"observed_optimal_fraction": 0.276,
"probability_of_optimal_cut": 0.28515625
}analytic agreement
On rings of 4, 6 and 8 vertices and on the 2-vertex edge, the simulated p=1 expectation equals the Farhi-Goldstone-Gutmann closed form |E|(1/2 + 1/2 sin(4 beta) sin(gamma) cos(gamma)^(d-1)) to 1e-12 at 16 angle pairs, and the product's grid optimum reaches the known ceiling of 3/4 of the ring's edges.
python/tests/test_catalog_products.py::test_qaoa_p1_expectation_matches_the_farhi_closed_form
exact optimum bound
The expected cut, the analytic value and every sampled cut never exceed the enumerated optimum; the optimum itself equals |E| on even rings (bipartite), 2 on a triangle and floor(n/2) ceil(n/2) on complete graphs.
python/tests/test_catalog_products.py::test_qaoa_cuts_never_exceed_the_brute_force_maximum
sampling consistency
The fraction of sampled assignments that are optimal lies within five binomial standard deviations of the exact probability of an optimal cut read off the state vector, and the sampled mean cut within five standard deviations of the exact expectation.
python/tests/test_catalog_products.py::test_qaoa_samples_follow_the_state_vector
resource guard
Requests whose grid search is estimated above the time ceiling, graphs with self-loops or repeated edges, and more than 12 vertices are refused before anything runs.
python/tests/test_catalog_products.py::test_qaoa_refuses_oversized_searches_and_bad_graphs
example execution
The example code is executed verbatim in a clean virtual environment with only the algorithms extra installed.
1.0.01 Nov 2026currentShown on this page
Needs SDK 0.3.0 or later with extras: algorithms.
KetQat implementation of published methods
The Quantum Approximate Optimization Algorithm and the p=1 closed form for triangle-free regular graphs are due to Farhi, Goldstone and Gutmann (2014); MaxCut is the classical NP-hard problem of Karp (1972). KetQat wrote this pure-Python statevector implementation (qaoa.py), the grid search, the brute-force reference, the seeded sampling, the validation tests and this catalog entry. KetQat did not invent the method.
Apache-2.0 — see Licensing.
People credited for this product. KetQat publishes and maintains it; contributors are credited for their work and are not sellers.
No usage reports yet
Distinct signed-in accounts that chose to send at least one usage report (ketqat report) for this product in the last 90 days. KetQat staff, test and bot accounts are excluded. Reports are opt-in, so this is not a count of all users.
Computed 10 Nov 2026, 17:10 UTC.
Not yet rated
Be the first to rate this product after you run it.
Mean of visible reviews. Hidden reviews and reviews by KetQat staff, test and bot accounts are excluded. Pro status gives no extra weight.
Sign in to review this product. One review per person; you can edit it later.
No reviews yet.