QAOA Tutorial: Build and Evaluate a Quantum Optimization Circuit Step by Step
QAOAquantum algorithmsquantum optimizationvariational algorithmsquantum circuitsMaxCut

QAOA Tutorial: Build and Evaluate a Quantum Optimization Circuit Step by Step

CCoqBit Labs
2026-11-03
7 min read

Build a QAOA circuit for MaxCut, estimate solution quality and sampling cost, and evaluate simulator or hardware results step by step.

This QAOA tutorial shows software engineers how to turn a small combinatorial optimization problem into a quantum circuit, estimate its cost and quality, optimize its parameters, and evaluate measured results. The workflow is deliberately framework-neutral so you can adapt it to Qiskit, Cirq, PennyLane, or a cloud execution service as APIs and hardware options change.

Overview

The Quantum Approximate Optimization Algorithm, or QAOA, is a variational quantum algorithm for discrete optimization. It combines a parameterized quantum circuit with a classical optimizer. The quantum circuit produces candidate solutions, while the classical loop adjusts circuit parameters to increase the expected value of a chosen objective.

For a developer, the important mental model is an ordinary optimization loop with a quantum subroutine:

  1. Encode the problem as a cost Hamiltonian.
  2. Create a parameterized QAOA circuit.
  3. Execute the circuit on a simulator or quantum device.
  4. Convert measurement results into objective values.
  5. Return the measured objective to a classical optimizer.
  6. Repeat until the budget, iteration limit, or convergence condition is reached.

QAOA does not automatically solve every optimization problem faster than a classical method. Its practical value is as a structured experiment: it lets you compare circuit depth, sampling cost, optimizer behavior, and solution quality for a problem small enough to inspect. That makes it a useful first variational quantum algorithm project.

At depth p, QAOA alternates a cost unitary and a mixer unitary p times. A common starting state is the equal superposition of all computational-basis states. The cost unitary applies phase according to the objective, and the mixer moves amplitude between candidate bit strings. The parameters are commonly written as gamma and beta, with one pair per layer.

How to estimate

Before running code, define three measurable quantities:

  • Best-known objective: the target value from brute force, an exact solver, or a trusted classical heuristic.
  • Observed objective: the value of the best bit string actually measured by QAOA.
  • Sampling probability: the fraction of shots that produce an acceptable or optimal bit string.

For a maximization problem, a simple solution-quality estimate is:

quality = observed objective / best-known objective

For a minimization problem, use a ratio that preserves the interpretation that values closer to one are better, such as best-known objective / observed objective, provided the objective is positive. If the objective can be zero or negative, report the raw objective and the absolute gap instead of forcing a ratio.

Estimate the sampling requirement separately from the circuit quality. If an acceptable solution appears with probability q in one shot, the probability of seeing it at least once after S shots is approximately:

1 - (1 - q)^S

This estimate assumes independent samples and a stable circuit. Solving it for a desired confidence level helps you choose a shot count before execution. It also makes an important distinction: a circuit can have a good expected objective but still require many shots to observe the best bit string reliably.

A rough execution budget can be represented as:

total evaluations = optimizer iterations × parameter evaluations per iteration × circuit repetitions

On a shot-based backend, multiply the number of circuit evaluations by the shots per evaluation. On an ideal statevector simulator, you may calculate exact expectation values for small circuits, but memory and runtime still grow rapidly with the number of qubits. Treat this formula as a planning model rather than a provider-specific price estimate.

Inputs and assumptions

Choose a small problem first

MaxCut is a clear QAOA example because each graph vertex maps naturally to a qubit. Assign each vertex a binary value. An edge contributes one to the cut when its endpoints receive different values. For a graph with edge set E, the classical objective is:

C(z) = sum over (i,j) in E of [z_i != z_j]

For a two-qubit edge, the corresponding cost term is commonly written as:

(I - Z_i Z_j) / 2

Summing those terms produces a cost Hamiltonian whose measured eigenvalues match the cut value. Sign conventions vary across SDKs, so test the mapping on a few basis states before optimizing.

Set the QAOA depth

The depth p controls how many cost-and-mixer layers are applied. Start with p = 1 to validate the encoding and data pipeline. Increase depth only after the lower-depth experiment works. More layers introduce more parameters, gates, and opportunities for noise, so a deeper circuit is not automatically a better experiment.

Choose an evaluation method

There are two common approaches. With exact simulation, calculate the expectation value directly from the state or simulator-supported observable evaluation. With sampling, measure the qubits repeatedly, decode each bit string, calculate its classical objective, and average the results. Sampling is closer to hardware behavior but adds statistical variation.

Keep the code portable

Separate the implementation into four functions: build_circuit(parameters, problem), execute(circuit, shots), decode(result), and objective(solution). This separation makes it easier to move between Qiskit, Cirq, PennyLane, or a cloud backend without rewriting the problem logic. SDK method names and primitive interfaces change, so pin and record the versions used for a reproducible experiment.

Worked examples

Example: a three-vertex triangle

Consider a triangle with vertices 0, 1, and 2, and edges (0,1), (1,2), and (0,2). The circuit uses three qubits. Its classical objective is the number of edges crossing the two partitions.

By enumerating the eight bit strings, you can establish a reference before running QAOA. Strings with all bits equal produce a cut of zero. Strings with one bit separated from the other two produce a cut of two, which is the best possible value for this graph. This brute-force reference is small enough to verify by hand and should be part of the test suite.

The implementation plan is:

  1. Prepare three qubits in the |+> state with a Hadamard gate on each qubit.
  2. For each edge, apply the cost interaction associated with Z_i Z_j, using the SDK's supported parameterized rotation and entangling-gate pattern.
  3. Apply a mixer rotation around the X axis to every qubit.
  4. Repeat the cost and mixer layers according to p.
  5. Measure all qubits and decode each bit string as a partition.
  6. Calculate the cut value for every sample and return both the mean value and the best observed value.

For a parameter vector at depth one, such as (gamma_1, beta_1), do not assume that the first parameter choice is useful. Evaluate several initial points or use a classical optimizer. A practical objective for the optimizer is the negative expected cut if the optimizer minimizes by default. The sign conversion is a frequent source of apparently reversed results.

Suppose a run returns 1,000 samples and 420 decode to one of the six optimal triangle partitions. The observed probability of an optimal string is 0.42. If the best observed cut is two and the reference optimum is two, the observed quality is 2 / 2 = 1. That does not mean every sample was optimal: the mean cut might be lower, and repeated runs with different random seeds may produce different distributions. Report all three values when comparing experiments: best value, mean value, and optimal-solution frequency.

Simulator versus hardware planning

Use an ideal simulator to validate the Hamiltonian, objective signs, bit ordering, and optimizer loop. Use a shot-based simulator to study sampling variance. Move to hardware only after those checks pass, because device noise can obscure a software bug. On a real device, compare the noisy result with an ideal baseline using the same circuit structure and shot count where practical.

For a reusable experiment record the problem instance, qubit layout, QAOA depth, parameter initialization, optimizer settings, shots, backend, transpilation or compilation choices, random seed, and software versions. These fields explain differences that a final objective value alone cannot.

When to recalculate

Recalculate the result whenever an input that affects quality, runtime, or reproducibility changes. That includes the graph or objective function, QAOA depth, shot count, optimizer settings, parameter initialization strategy, simulator mode, backend, qubit mapping, compilation settings, and noise model.

Revisit the baseline whenever you change the problem size. A brute-force optimum is useful for tiny examples but becomes impractical as the number of variables grows. Replace it with a clearly identified classical reference method and report whether the comparison is exact, heuristic, or simply a sanity check.

Update the implementation after SDK or backend changes as well. Re-run a fixed regression case: verify the cost of every computational-basis state, confirm that a known optimal bit string is decoded correctly, and compare a short ideal-simulator run with a stored expectation. Avoid comparing results across versions unless the circuit construction and execution settings are equivalent.

Use this checklist before adapting the tutorial to a new optimization problem:

  • Can you calculate the classical objective for any candidate bit string?
  • Does the cost Hamiltonian reproduce that objective on test states?
  • Are maximization and minimization signs handled consistently?
  • Have you separated circuit construction, execution, decoding, and scoring?
  • Is the chosen depth justified by the problem size and execution budget?
  • Are you reporting mean objective, best observed objective, and solution frequency?
  • Have you recorded shots, seeds, backend details, and software versions?

Once these checks pass, increase the problem size or depth one variable at a time. That produces a more useful QAOA benchmark than changing the graph, optimizer, backend, and circuit simultaneously.

Related Topics

#QAOA#quantum algorithms#quantum optimization#variational algorithms#quantum circuits#MaxCut
C

CoqBit Labs

Quantum Computing Editor

Senior editor and content strategist. Writing about technology, design, and the future of digital media. Follow along for deep dives into the industry's moving parts.