This QAOA tutorial presents a repeatable workflow for turning a combinatorial optimization problem into a quantum circuit, tuning its parameters, interpreting sampled solutions, and benchmarking the result against a classical baseline. The same process can be reused as graph instances, circuit depth, shot counts, simulators, and hardware backends change.
Overview
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical method for searching for good solutions to discrete optimization problems. A classical optimizer proposes circuit parameters, a quantum processor or quantum simulator estimates the objective value, and the optimizer uses that value to propose the next parameters.
QAOA does not automatically make every optimization problem faster. Its practical value is that it gives developers a structured way to test quantum optimization circuits under controlled conditions. A useful experiment therefore measures more than the best bit string returned by a run. It records objective quality, approximation ratio, circuit depth, number of shots, optimizer evaluations, and elapsed runtime, then compares those measurements with a classical method solving the same instance.
The standard QAOA workflow has six stages:
- Define the optimization problem and its objective function.
- Encode the objective as a cost Hamiltonian.
- Choose a mixer Hamiltonian, usually a sum of single-qubit X operators.
- Build alternating cost and mixer layers with depth p.
- Optimize the variational angles using measured expectation values.
- Sample the final circuit and compare candidate solutions with a classical baseline.
For a first QAOA experiment, MaxCut is a practical example because a graph maps directly to pairwise terms. For an edge (i, j), a cut contribution can be represented as (1 - ZiZj)/2. Summing this expression over all edges gives a cost Hamiltonian whose measured value is the cut size.
How to estimate QAOA performance and cost
Estimate a QAOA experiment by separating algorithm quality from execution cost. For an instance with known optimum Copt, let Cbest be the best sampled objective value. For a maximization problem, a simple approximation ratio is:
approximation ratio = Cbest / Copt
If the optimum is unknown, report the best classical value available and label it as a reference rather than a proven optimum. For minimization problems, use a directionally consistent metric such as Copt / Cbest, or clearly state the transformation used to convert the problem into a maximization form.
A basic execution estimate starts with the number of objective evaluations:
total evaluations = optimizer iterations × evaluations per iteration × parameter restarts
Then estimate measurement work:
measurement shots = total evaluations × shots per evaluation × measurement groups
For a simple MaxCut circuit measured in the computational basis, all edge contributions can often be evaluated from the same bit-string samples. More complicated Hamiltonians may require separate measurement settings or grouped terms. Include those groups in the estimate instead of assuming that one circuit execution covers every term.
Runtime is not determined by shots alone. Track circuit construction, transpilation or compilation, queue or submission delay where applicable, execution time, result retrieval, and classical optimizer overhead. On a simulator, memory and simulation method can dominate. On hardware, circuit depth, two-qubit gates, connectivity, calibration, and repeated submissions can affect the practical result.
Inputs and assumptions
Before writing code, create an experiment specification. Record the following inputs:
- Problem instance: graph edges, weights, constraints, and the number of variables.
- Objective convention: whether larger or smaller values are better, and how bit strings map to decisions.
- QAOA depth: the number of alternating cost and mixer layers, denoted by
p. - Initialization: the starting values for gamma and beta, including whether parameters are randomized, zero-initialized, or transferred from a nearby experiment.
- Optimizer settings: optimizer name, step or trust-region settings, stopping tolerance, maximum iterations, and restart count.
- Sampling settings: shots per objective evaluation and final sampling run.
- Execution target: statevector or shot-based simulator, noisy simulator, or hardware backend.
- Classical baseline: brute force for small instances, a heuristic, an integer-programming solver, or another documented method.
Keep the cost function used during optimization separate from the final decision rule. The optimizer usually minimizes or maximizes an expectation value, while the application may care about the most frequent valid bit string, the best observed bit string, or the probability of sampling a solution above a quality threshold.
| Choice | Useful starting point | What to record |
|---|---|---|
| Parameter initialization | Small random values, structured values, or parameters transferred from a lower-depth run | Seed, ranges, and restart count |
| Optimizer | A derivative-free optimizer for noisy objectives; a gradient-based method when reliable gradients are available | Iterations, evaluations, and termination reason |
| Depth | Begin with p = 1, then increase gradually | Logical and transpiled depth |
| Shots | Use a fixed pilot count, then test sensitivity to higher counts | Shots per evaluation and final sampling shots |
| Execution target | Start with an ideal simulator, then add noise or hardware | Backend, noise model, compilation settings, and date |
Worked examples
Triangle MaxCut
Consider a triangle with vertices 0, 1, and 2. Its cost Hamiltonian is:
C = (1 - Z0Z1)/2 + (1 - Z1Z2)/2 + (1 - Z0Z2)/2
Each qubit represents one side of a partition. The all-zero and all-one strings produce a cut value of zero. Any string with one vertex separated from the other two cuts two edges, so the optimum cut value is two for this instance.
A p = 1 circuit begins in the equal superposition state, applies a cost unitary controlled by gamma, and then applies the mixer unitary controlled by beta. In framework code, the implementation should make the following pieces explicit:
prepare_plus_state()
apply_cost_layer(gamma, edges)
apply_mixer_layer(beta, number_of_qubits)
measure_all_qubits()
For each candidate pair of angles, estimate the expected cut value from sampled bit strings. After optimization, run a separate final sampling job and calculate the frequency of strings with cut value two. Report both the best observed cut and its probability; a high expectation value does not by itself describe how concentrated the output distribution is.
For a small graph, compare the result with exhaustive enumeration. Then repeat the experiment with the same graph at several shot counts and parameter restarts. This reveals whether a change in the reported result comes from the QAOA circuit, optimizer behavior, or measurement noise.
Experiment template
Use one row per run in a CSV or experiment tracker:
instance_id, qubits, edges, p, seed, optimizer,
max_iterations, restarts, shots_per_eval, final_shots,
logical_depth, transpiled_depth, backend, best_value,
expected_value, approximation_ratio, success_probability,
evaluations, runtime_seconds, notes
For example, if an experiment uses 40 optimizer iterations, one objective evaluation per iteration, two parameter restarts, and 1,000 shots per evaluation, the planned objective-measurement budget is 80,000 shots before the separate final sampling run. If the optimizer evaluates multiple trial points per iteration, replace “one” with the measured evaluations-per-iteration value.
When to recalculate
Recalculate the estimate whenever an input that affects quality, execution, or comparison changes. This includes a new graph instance, a different QAOA depth, a changed shot budget, another initialization strategy, an optimizer setting change, a new simulator configuration, or a different hardware backend.
Revisit the benchmark after framework releases that change primitives, optimizer interfaces, transpilation behavior, measurement handling, or backend execution. Keep the environment details with each run so that a later result can be attributed to the algorithm rather than an undocumented software change.
A practical update cycle is:
- Run an ideal or controlled simulator baseline.
- Repeat with fixed seeds and several parameter restarts.
- Increase shots to test sampling sensitivity.
- Increase
pone layer at a time and record circuit depth. - Compare against the same classical baseline and objective convention.
- Only then test noise models or hardware, recording mitigation methods separately.
Use the resulting table to decide whether an apparent improvement is meaningful: better approximation ratio, higher success probability, lower measurement budget, or a more realistic execution profile. That discipline makes a QAOA tutorial reproducible and turns each new graph, software version, or backend into a comparable experiment rather than an isolated demo.