This QAOA tutorial shows how to model Max-Cut, build a parameterized circuit, tune its angles, and decide whether tuning produced a meaningful improvement. You will also get a repeatable evaluation workflow, simple approximation-ratio calculations, and a results log you can reuse when changing graphs, circuit depth, simulators, or hardware backends.
Overview
The Quantum Approximate Optimization Algorithm, or QAOA, is a hybrid method. A quantum circuit prepares and samples candidate solutions, while a classical optimizer changes the circuit parameters between runs. For Max-Cut, the goal is to divide the vertices of a graph into two groups so that as many edges as possible cross between groups.
Each computational-basis bit string represents a partition. A measured bit of 0 places a vertex in one group, and a bit of 1 places it in the other. The bit string 0101, for example, assigns four vertices to alternating groups. Because swapping every bit leaves the cut value unchanged, complementary strings such as 0101 and 1010 describe equivalent cuts.
QAOA does not guarantee that a shallow circuit will find the global optimum. Its practical value in an experiment is therefore not established by looking at one attractive bit string. You should compare the best sampled solution and the average sampled quality with an exact classical baseline, while recording the number of shots, circuit depth, optimizer behavior, and execution conditions.
For background on circuit depth, gate counts, and execution overhead, see Quantum Circuit Resource Estimation. If you are new to quantum states and measurement, What Is a Qubit? provides useful preparation.
How to estimate QAOA performance
Use the following workflow for each graph and each QAOA configuration:
- Define the graph. List the vertices and edges. Start with a small graph whose optimum can be checked exhaustively.
- Calculate the classical baseline. Evaluate every relevant bit string, or use a trusted exact solver, and record the optimal cut value, denoted by
C*. - Encode the objective. Construct a cost Hamiltonian whose expectation value corresponds to the cut objective. For an edge connecting vertices
iandj, a common Max-Cut contribution is based on the parity of their two bits. - Choose the QAOA depth. A depth of
papplies alternating cost and mixer layersptimes. Keep the initial comparison simple, such as one depth across several optimizer settings. - Prepare and sample. Initialize the qubits in an equal superposition, apply the parameterized layers, measure the circuit, and collect a fixed number of shots.
- Score every result. Convert each measured bit string into a cut value using the original graph, not only the Hamiltonian expectation returned by a framework.
- Compare configurations. Report the best observed cut, the mean cut value, the frequency of optimal strings, and the approximation ratio.
The approximation ratio provides a compact comparison:
approximation ratio = best observed cut value / exact optimal cut value
For example, if the exact optimum is 5 and the best sampled string has value 4, the best-sample ratio is 0.8. You may also calculate a sampled mean ratio by dividing the average cut value by the exact optimum. State which version you use; the two measurements answer different questions.
Do not treat a higher ratio from a single run as conclusive evidence that one configuration is better. Repeat the experiment with the same shot budget and, where possible, multiple optimizer initializations. A useful comparison keeps the graph, scoring function, shot count, stopping rule, and random-seed policy fixed while changing only the factor under study.
Inputs and assumptions
Graph and encoding
Represent the problem as an undirected graph G = (V, E). Use one qubit per vertex in a direct encoding. For each edge (i, j), the cut contributes one when the assigned bits differ and zero when they match. This makes the classical scoring function easy to test independently from the quantum circuit.
Before running QAOA, write a small classical scorer. Given a bit string, it should iterate over the edge list and count edges whose endpoint bits differ. Test it on a few hand-checked partitions. This catches bit-order mistakes, which are common when a framework displays the least-significant qubit first or reverses the order of measured bits.
Ansatz and parameters
A standard QAOA ansatz has two parameter arrays: gamma values for cost layers and beta values for mixer layers. At depth p, there are typically 2p parameters, although conventions and circuit implementations can vary. Document the parameter order and angle convention in your experiment log.
For a first test, compare depth one with a modest increase in depth rather than changing depth, optimizer, and noise model simultaneously. More layers increase expressive power but also add gates, parameters, and opportunities for sampling and hardware noise to affect the result.
Optimizer and stopping rule
QAOA optimization is a classical numerical search over noisy objective estimates. Choose an optimizer that matches your execution setting: gradient-free methods can be convenient when the objective is estimated from finite shots, while gradient-based methods may require additional circuit evaluations and careful gradient handling.
Define a maximum number of objective evaluations and a stopping tolerance before running the experiment. Otherwise, one configuration may receive substantially more opportunities to improve simply because its optimizer ran longer. Record the initial parameters, final parameters, objective history, and termination reason.
Shots, noise, and backend behavior
Shots are the number of measurements used to estimate the output distribution. A small shot count makes each objective evaluation cheaper or faster but increases statistical variation. Use the same shot count for comparable trials, and consider a separate final sampling budget after optimization so that parameter tuning and final evaluation are not confused.
Start with an ideal statevector or noiseless shot-based simulator to validate the encoding and optimization loop. Then test a noisy simulator or hardware backend if that is part of your goal. Transpilation can change gate counts, connectivity, and depth, so record the target backend, compilation settings, mapped qubits, and final circuit resources. The Quantum SDK Comparison can help you choose a framework for the experiment.
Worked examples
Example 1: a four-vertex cycle
Consider a cycle with edges (0,1), (1,2), (2,3), and (3,0). An alternating assignment such as 0101 cuts all four edges, so the exact optimum is C* = 4. The complementary assignment is equally good.
Suppose a depth-one QAOA run produces the following simplified measurement summary after scoring each string:
0101and its complement: cut value 4, observed 36% of shots combined;- strings with cut value 2: observed 52% of shots combined;
- strings with cut value 0: observed 12% of shots combined.
The best-sample approximation ratio is 4 / 4 = 1.0. The mean cut value is (0.36 × 4) + (0.52 × 2) + (0.12 × 0) = 2.48, giving a mean ratio of 2.48 / 4 = 0.62. Both figures matter: the first says an optimal assignment appeared, while the second describes the overall distribution.
Now suppose a tuned run increases the optimal-string frequency to 60%, reduces cut-value-2 outcomes to 34%, and leaves 6% at cut value 0. The best-sample ratio remains 1.0, so it has not improved on that metric. The mean value becomes (0.60 × 4) + (0.34 × 2) = 3.08, or a mean ratio of 0.77. In this case tuning improved the distribution even though the best observed answer was already optimal.
Example 2: comparing depth and optimizers
For a less symmetric graph, create a comparison table with one row per trial. Include graph identifier, number of vertices and edges, depth, optimizer, initial parameter seed, shot count during optimization, final evaluation shots, best cut, mean cut, optimal-string frequency, approximation ratios, objective evaluations, and backend details.
A reasonable interpretation might be: depth two produced a higher best cut than depth one, but only after many more evaluations; its mean ratio was similar, and its transpiled circuit was substantially deeper. That result does not establish a practical advantage for depth two. It identifies a tradeoff worth testing again with more repetitions, a controlled noise model, or a different parameter initialization.
Illustrative implementation structure
Whether you use Qiskit, Cirq, PennyLane, or another SDK, separate the experiment into four functions:
score(bitstring, edges)returns the classical cut value;build_qaoa(graph, p, parameters)returns the parameterized circuit;evaluate(parameters, shots, backend)executes and scores samples;optimize(initial_parameters)calls the classical optimizer and stores the history.
This separation makes it easier to update framework APIs, replace a sampler, test a new graph, or run the same scoring code against an exact classical distribution. For a related variational workflow, see the VQE Tutorial.
Reusable results log
Copy this template into a notebook or experiment-tracking system:
date_or_run_id:
graph_vertices:
graph_edges:
exact_optimum:
qaoa_depth_p:
optimizer_and_settings:
initial_parameters:
shots_during_optimization:
final_evaluation_shots:
backend_or_simulator:
transpilation_settings:
best_cut:
mean_cut:
optimal_string_frequency:
best_sample_ratio:
mean_ratio:
objective_evaluations:
termination_reason:
notes_and_next_test:When to recalculate
Recalculate whenever an input that affects the comparison changes. That includes the graph, edge weights, QAOA depth, optimizer or stopping rule, parameter initialization, shot allocation, backend, transpilation settings, noise model, and framework sampler behavior. A change in any of these can alter the measured distribution even when the mathematical problem is unchanged.
Refresh the experiment after major quantum SDK releases rather than assuming old examples behave identically. Sampler interfaces, default measurement behavior, optimizer names, parameter conventions, and transpilation controls can change. Run the workflow at least twice a year if it is used as a maintained tutorial, and rerun it immediately when a dependency update changes circuit construction or execution results.
For every refresh, first validate the classical scorer and exact baseline. Next run a noiseless small-graph test, then repeat the tuned experiment with the documented shot budget. Compare not only the best bit string but also the mean cut, optimal frequency, circuit resources, and evaluation count. If the result changes, record whether the cause was an API update, a different random initialization, a backend change, or ordinary sampling variation.
The most useful next step is to run one controlled comparison: keep the graph and execution budget fixed, change only QAOA depth or optimizer, and log the complete result. This turns a QAOA implementation into a reproducible experiment rather than a one-off demonstration. For deciding whether a larger optimization experiment is worthwhile, use the Classical-versus-Quantum Feasibility Checklist before increasing circuit size or hardware spend.