QAOA Max-Cut Tutorial: Build, Tune, and Validate a Quantum Optimization Circuit
QAOAMax-Cutquantum optimizationquantum algorithmsbenchmarking

QAOA Max-Cut Tutorial: Build, Tune, and Validate a Quantum Optimization Circuit

QQubit365 Editorial Team
2026-11-08
7 min read

Learn how to implement QAOA for Max-Cut, tune its parameters, budget shots, and validate results against classical and hardware baselines.

This QAOA Max-Cut tutorial presents a repeatable workflow for encoding a graph, building and tuning a Quantum Approximate Optimization Algorithm circuit, and deciding whether its output is meaningful. It covers cost-Hamiltonian construction, circuit depth, initialization, optimizers, shot allocation, classical baselines, and validation on simulators or quantum hardware.

Overview

Max-Cut is a useful starting point for quantum optimization because its objective is easy to define: divide the vertices of a graph into two groups so that as many edges as possible cross between them. A bitstring represents a partition. For example, 0101 assigns vertices 0 and 2 to one group and vertices 1 and 3 to the other.

For an edge connecting vertices i and j, the edge contributes one to the cut when the corresponding bits differ. In binary notation, that contribution is often written as (1 - z_i z_j) / 2, where each z value is either +1 or -1. The total objective is therefore:

C(x) = Σ_(i,j)∈E (1 - z_i z_j) / 2

QAOA uses two alternating operators. The cost unitary applies phases based on the graph objective, while the mixer unitary changes the computational basis states so the optimizer can explore different partitions. At depth p, the circuit has parameter vectors γ = (γ₁, ..., γₚ) and β = (β₁, ..., βₚ). A classical optimizer adjusts those parameters to maximize the measured expected cut value.

QAOA does not automatically establish a quantum advantage. A meaningful experiment must compare its results with a transparent classical method and separate optimization quality from sampling noise, compilation effects, and hardware errors.

How to estimate

Use the following workflow for a QAOA implementation:

  1. Define the graph. Record the number of vertices, edge list, weights if present, and whether duplicate edges or self-loops are allowed.
  2. Build the objective. Convert every edge into a two-qubit interaction. For an unweighted graph, each edge has coefficient one. For a weighted graph, multiply its contribution by the edge weight.
  3. Choose the initial state. A uniform superposition created with a Hadamard gate on every qubit is a common baseline. It gives the initial circuit access to all bitstrings.
  4. Apply the alternating layers. Each layer applies a cost unitary parameterized by γ followed by a mixer parameterized by β. The exact gate decomposition depends on the SDK and backend.
  5. Measure the objective, not just the most frequent string. From measured bitstrings, calculate each cut value and estimate the mean objective. The most common bitstring and the best observed bitstring answer different questions.
  6. Optimize the parameters. Run a classical optimizer against the estimated objective. Keep the parameter history, stopping rule, random seed where supported, and number of shots per evaluation.
  7. Validate the result. Re-evaluate the final parameters with fresh shots, calculate the best and mean cut values, and compare them with a classical baseline.

A useful quality measure is the approximation ratio:

approximation ratio = QAOA cut value / classical optimum

If the optimum is unavailable for a larger graph, use the strongest reproducible baseline available and label the result as a baseline ratio rather than an exact approximation ratio. For a maximization problem, a ratio closer to one indicates a better result, but it should always be reported with the graph, depth, shots, and evaluation method.

Framework primitives change over time, but the experiment design is portable. Qiskit, Cirq, PennyLane, and other quantum SDKs generally provide circuit objects, parameterized gates, simulators, measurement tools, and optimizer interfaces. Consult the current documentation for syntax and backend-specific constraints. A broader gate and syntax reference is available in the Quantum Gates Reference.

Inputs and assumptions

Before running the experiment, write down these inputs:

  • Graph: vertex count, edge list, weights, and the graph-generation method.
  • QAOA depth: test a small sequence such as p = 1, 2, 3 rather than selecting one depth without comparison.
  • Parameter initialization: choose random, fixed heuristic, interpolated, or warm-start values and record the choice.
  • Optimizer: specify the algorithm, maximum evaluations, tolerance, and whether it handles noisy function values.
  • Shots: record shots per objective evaluation and the separate number used for final validation.
  • Execution mode: distinguish an ideal statevector calculation, a finite-shot simulator, a noisy simulator, and hardware execution.
  • Classical baseline: use exact enumeration for small graphs when practical; otherwise use a clearly documented heuristic or solver configuration.

Parameter count grows with QAOA depth: the standard formulation has two trainable parameters per layer. Circuit depth also depends on how the graph edges are scheduled into executable two-qubit operations. Dense graphs may require more sequential operations than sparse graphs, even when they use the same number of qubits.

Shot allocation is part of the estimate. If one optimization run evaluates the objective N times with S shots per evaluation, the basic measurement budget is approximately N × S shots, before repeats, calibration overhead, or validation runs. This is not a hardware price estimate; it is an experiment-planning estimate. Cloud or vendor costs, if relevant, must be calculated separately from the provider's current terms.

Worked examples

Example 1: triangle graph

Consider a three-vertex cycle with edges (0,1), (1,2), and (0,2). The graph requires three qubits. Any partition that places one vertex on one side and two on the other cuts two edges, which is optimal for this graph. The bitstrings 001, 010, and 100, along with their complements, represent optimal partitions under a consistent bit-ordering convention.

For a first experiment, run depths p = 1 and p = 2 using the same optimizer budget and shot count. For each depth, report the best sampled cut, the mean cut over all samples, the probability of sampling an optimal bitstring, and the final parameter values. A simulator may show a clean pattern, while finite shots can make two otherwise similar parameter settings appear different. Repeating the final evaluation helps distinguish a real improvement from sampling variation.

Example 2: comparing execution modes

RunPurposeReportInterpretation
Exact classicalFind the reference optimumOptimal cut and runtimeReference for a small graph
Ideal simulatorTest the QAOA model without sampling or device noiseExpected cut, parameters, depthChecks encoding and optimizer behavior
Shot-based simulatorModel finite measurement dataMean cut, best cut, shots, repeatsShows statistical stability
Noisy simulator or hardwareMeasure execution effectsCompiled depth, two-qubit operations, calibration context, resultsTests practical robustness

Suppose the classical optimum for a small test graph is 5. An ideal simulator returns an expected cut of 4.7, while a hardware run returns a mean cut of 3.9 and occasionally samples 5. The hardware result is not automatically useless: it may still demonstrate that high-quality solutions are sampled. However, the gap should be investigated through repeated runs, circuit-resource data, and noise-aware controls. Do not compare only the single best bitstring; include distributions and uncertainty indicators.

For larger graphs, create a benchmark set rather than relying on one favorable instance. Keep graph size, density, weight distribution, depth, optimizer budget, and shot budget visible. The quantum circuit resource estimation guide can help organize qubit, gate, depth, and shot accounting.

When to recalculate

Revisit the experiment whenever the graph, QAOA depth, optimizer, shot allocation, SDK, compiler, simulator, or backend changes. A new backend can alter connectivity, supported gates, transpiled depth, measurement behavior, and error exposure. Likewise, changing from an ideal simulator to hardware changes the question from “can this ansatz represent a good solution?” to “can this execution stack preserve enough of that solution to measure it?”

Use this compact worksheet for every run:

  • Graph ID, vertex count, edge count, and weight convention
  • SDK and version, backend or simulator, and compilation settings
  • QAOA depth, parameter initialization, optimizer, and evaluation limit
  • Shots per evaluation, final validation shots, and number of repeats
  • Classical baseline method and result
  • Best cut, mean cut, optimal-solution probability if known, and approximation ratio
  • Seed, parameter history, circuit depth, two-qubit operation count, and timestamp

For reproducibility, store the graph, source code, environment, raw counts, optimized parameters, and final circuit together. The reproducible quantum computing workflow provides a useful structure for that record. If the result is being evaluated as a potential use case rather than a learning exercise, also apply a broader quantum algorithm project evaluation.

The practical decision rule is simple: increase depth or move to hardware only after the encoding, baseline, optimizer budget, and measurement procedure are stable. Recalculate after each material change, and treat an improvement as credible only when it survives fresh shots, repeated runs, and comparison with the same classical reference.

Related Topics

#QAOA#Max-Cut#quantum optimization#quantum algorithms#benchmarking
Q

Qubit365 Editorial Team

Quantum Computing Editors

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.