QAOA is a hybrid quantum-classical method for searching for good solutions to combinatorial problems. This QAOA Max-Cut tutorial builds the workflow in Python, explains how to compare its output with a classical baseline, and gives a repeatable way to evaluate circuit depth, optimization effort, sampling quality, and simulator or hardware behavior.
Overview
Max-Cut asks a simple question: given a graph, how can its vertices be divided into two groups so that as many edges as possible cross between the groups? A bit string represents a partition. For example, 0101 assigns vertices 0 and 2 to one group and vertices 1 and 3 to the other.
QAOA, or the Quantum Approximate Optimization Algorithm, encodes the graph as a cost Hamiltonian. A parameterized quantum circuit prepares candidate bit strings, while a classical optimizer adjusts the circuit parameters to increase the expected cut value. The workflow is therefore hybrid:
- Construct a graph and define its objective function.
- Prepare a parameterized QAOA circuit.
- Estimate the objective value from circuit measurements.
- Use a classical optimizer to update the parameters.
- Sample the optimized circuit and select the best feasible bit string.
QAOA does not automatically outperform a classical algorithm. For small graphs, exact enumeration, dynamic programming, local search, or an integer-programming solver may be faster and more reliable. The practical question is whether the quantum workflow produces a useful solution under the same resource and quality constraints. That requires a baseline and consistent measurements.
The examples below use PennyLane-style Python because its optimization loop is compact. The same logical stages map to Qiskit QAOA, Cirq-based circuits, or a managed quantum cloud platform. SDK names and interfaces can change, so pin the package versions used by a project and check the current documentation before adapting the snippets.
How to estimate QAOA performance
Start by separating four measurements that are often mixed together:
- Solution quality: the cut value of the best sampled bit string, divided by the known or computed optimum.
- Expectation value: the average cut value estimated from repeated circuit measurements.
- Optimization effort: the number of objective evaluations, optimizer iterations, and circuit executions.
- Execution cost: qubit count, circuit depth, two-qubit gate count, shots, queue or runtime behavior, and noise sensitivity.
For a graph with edge set E, define the cut value of a bit string x as:
C(x) = sum over (i,j) in E of [x_i != x_j]
When the edge list has unit weights, each crossing edge contributes one. For weighted Max-Cut, replace the contribution with the edge weight. The approximation ratio is:
approximation ratio = best sampled cut value / reference optimum
The reference optimum may come from exhaustive enumeration for a small graph or from a trusted classical solver for a larger one. If the optimum is unknown, report the result against the best classical solution found and label it accordingly.
A framework-neutral circuit model
At QAOA layer p, the circuit normally alternates a cost unitary and a mixer unitary. The initial state is commonly an equal superposition created with Hadamard gates. For every edge, the cost operation applies a parameterized interaction between the corresponding qubits. The mixer applies a parameterized rotation to each qubit.
A compact PennyLane-style skeleton looks like this:
import pennylane as qml
from pennylane import numpy as np
edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
n_qubits = 4
p = 2
dev = qml.device("default.qubit", wires=n_qubits, shots=None)
def qaoa_layer(gamma, beta):
for i, j in edges:
qml.IsingZZ(2 * gamma, wires=[i, j])
for wire in range(n_qubits):
qml.RX(2 * beta, wires=wire)
@qml.qnode(dev)
def expected_cost(params):
gammas = params[0]
betas = params[1]
for wire in range(n_qubits):
qml.Hadamard(wires=wire)
for layer in range(p):
qaoa_layer(gammas[layer], betas[layer])
return qml.expval(cost_observable)
The exact observable construction depends on the SDK and the sign convention used for the cost Hamiltonian. Validate it on one or two manually scored bit strings before running an optimizer. A sign error can cause the optimizer to minimize the cut when the intended objective is to maximize it.
Choosing and running the optimizer
QAOA uses a low-dimensional parameter vector containing p gamma values and p beta values. Gradient-based methods can work well on differentiable simulators, while derivative-free methods are useful when measurements are finite-shot, noisy, or supplied by hardware. No single optimizer is consistently best for every graph, depth, initialization, and noise model.
Keep the objective loop observable:
history = []
def objective(params):
value = expected_cost(params)
history.append(float(value))
return -value # negate when the optimizer minimizes
# Use the optimizer interface supplied by your selected SDK.
# Record parameters, objective value, iteration, and elapsed time.
Run several initializations rather than trusting one optimization trajectory. Compare the best result, median result, and variation between runs. A single unusually good run is not a reliable benchmark.
Inputs and assumptions
Before calculating a result, record the inputs that determine whether two QAOA experiments are comparable:
- Graph: number of vertices, number of edges, degree distribution, connectivity, and whether edges are weighted.
- Depth p: the number of cost-mixer pairs. Increasing p adds parameters and usually increases circuit depth.
- Initialization: random, fixed, heuristic, or parameters transferred from a lower-depth run.
- Optimizer: algorithm, learning rate or step settings, stopping tolerance, and maximum iterations.
- Shots: the number of samples used to estimate expectations and produce final counts.
- Backend: ideal statevector, shot-based simulator, noisy simulator, or hardware. Record transpilation and device settings where applicable.
- Baseline: the classical method, time limit, and whether the reported value is optimal or simply the best found.
For an ideal statevector simulation, expectation values can be smooth and reproducible. Shot-based simulation introduces sampling error. Hardware adds calibration drift, connectivity constraints, readout error, gate error, queue time, and possible transpilation overhead. A noiseless simulator result should therefore be treated as an algorithmic reference, not a prediction of hardware performance.
Estimate total quantum evaluations with a simple planning formula:
total evaluations = optimizer iterations × parameter evaluations per iteration × measurement settings
Multiply that estimate by the shots per evaluation to approximate the number of circuit shots. The actual execution count may be higher when gradients, grouped observables, retries, or backend-specific batching are used.
Worked examples
Example graph and classical reference
Use the four-vertex graph with edges (0,1), (0,2), (1,2), and (2,3). A small graph can be scored by direct enumeration:
from itertools import product
def cut_value(bits, edges):
return sum(bits[i] != bits[j] for i, j in edges)
best_value = -1
best_bits = None
for bits in product([0, 1], repeat=4):
value = cut_value(bits, edges)
if value > best_value:
best_value = value
best_bits = bits
print(best_value, best_bits)
This baseline gives you a reference for validating the Hamiltonian, the sampled bit-string interpretation, and the final approximation ratio. Because complementary assignments represent the same cut, a bit string and its inverted string should have equal scores.
Illustrative benchmark table
The following table is a measurement template, not a claim about universal QAOA performance. Fill it with results from your graph, SDK version, backend, and fixed experimental settings.
| Configuration | What to record | How to interpret it |
|---|---|---|
| p = 1, ideal simulator | Best cut, expectation, iterations, depth | Useful for validating the objective and circuit construction |
| p = 2, ideal simulator | Best cut, approximation ratio, parameter variance | Tests whether added expressivity improves results enough to justify extra optimization |
| p = 2, shot-based simulator | Best cut across repeated seeds, shots, evaluations | Shows sensitivity to measurement noise and initialization |
| p = 2, hardware or noisy backend | Sampled cut, two-qubit depth, readout behavior, runtime | Separates algorithm quality from execution noise and compilation effects |
For each row, run a classical baseline under a comparable wall-clock or evaluation budget. Report the best sampled solution and the expectation value separately: a high expectation does not guarantee that the optimum appears frequently in the samples, while a rare optimum sample may coexist with a modest expectation.
Tuning checklist
- Begin with p = 1 and verify every cut value manually.
- Increase p only when the lower-depth result and baseline are correctly measured.
- Try multiple parameter seeds and retain the full optimization history.
- Use more shots for final sampling than for early exploratory iterations when execution cost matters.
- Compare at least one gradient-based and one derivative-free optimizer when the backend permits it.
- Track two-qubit depth after compilation, not only the abstract circuit depth.
- Repeat noisy experiments and report dispersion, not only the best run.
- Test whether a simple classical local-search improvement beats the sampled quantum candidates.
When to recalculate
Recalculate the benchmark whenever any input that affects quality or cost changes. That includes the graph, edge weights, QAOA depth, optimizer settings, initialization strategy, shot count, SDK version, transpiler configuration, simulator method, noise model, or hardware backend. A result from one graph should not be generalized to another with a different density or structure.
Refresh the workflow after a major SDK release because observable definitions, optimizer interfaces, circuit compilation, measurement formats, and backend execution behavior may change. Re-run the classical reference whenever the graph changes, and regenerate the resource estimate before moving from simulation to hardware. For repeatable engineering work, store the graph, package versions, random seeds, parameters, backend settings, counts, expectation history, and compiled-circuit metrics alongside each result.
The practical decision rule is straightforward: keep QAOA when it produces a solution quality that matters for the application under a clearly defined resource budget. If a classical baseline reaches the same result with substantially less effort, document that outcome rather than forcing a quantum advantage claim. Use the experiment to identify the next useful change—different initialization, a smaller graph, a deeper circuit, more shots, a better compilation strategy, or a different backend—and then rerun the same measurement protocol.