QAOA Explained with a Practical Max-Cut Example in Qiskit
QAOAMax-Cutquantum algorithmsQiskitquantum optimizationNISQ

QAOA Explained with a Practical Max-Cut Example in Qiskit

CCoqBit Labs
2026-11-12
6 min read

Learn how QAOA encodes Max-Cut, optimizes parameters, and runs as a practical Qiskit-style hybrid circuit.

QAOA turns a discrete optimization problem into a parameterized quantum circuit whose parameters are improved by a classical optimizer. In this tutorial, you will translate a small Max-Cut graph into a cost Hamiltonian, build a QAOA circuit in Qiskit-style Python, interpret measured bitstrings, and decide when increasing circuit depth or changing the execution method is worthwhile.

Overview

Max-Cut asks you to divide the vertices of a graph into two groups so that as many edges as possible cross between the groups. A bitstring provides a natural encoding: bit 0 can represent one group and bit 1 the other. For an edge connecting vertices i and j, the edge contributes one to the cut when the two bits differ.

QAOA, or the Quantum Approximate Optimization Algorithm, alternates two parameterized operations:

  • Cost operation: assigns phase according to the quality of each candidate solution.
  • Mixer operation: moves probability amplitude among candidate bitstrings.

A classical optimizer repeatedly changes the parameters and evaluates the circuit's expected cost. The quantum circuit supplies the expectation value; the classical routine chooses the next parameters. This hybrid loop is the central pattern behind many variational quantum algorithms.

For a graph G=(V,E), the Max-Cut cost operator is commonly written as:

C = Σ(i,j)∈E (1 - ZᵢZⱼ) / 2

Here, ZᵢZⱼ has eigenvalue +1 when the two corresponding bits agree and −1 when they differ. Consequently, each edge term evaluates to 0 for an uncut edge and 1 for a cut edge.

For a depth-one circuit, the state is typically prepared as:

|ψ(γ,β)⟩ = U₍B₎(β) U₍C₎(γ) |+⟩ⁿ

Higher-depth QAOA repeats the cost and mixer layers with separate parameter pairs: (γ₁,β₁), (γ₂,β₂), ....

How to estimate the Max-Cut result

The quantity to optimize is the expected cut value:

F(γ,β) = ⟨ψ(γ,β)| C |ψ(γ,β)⟩

On an ideal simulator, this expectation can be calculated from the full statevector. On a shot-based simulator or quantum processor, it is estimated from repeated measurements. The optimizer attempts to maximize F.

Graph-to-Hamiltonian translation

Graph elementCost contributionInterpretation
Edge (0, 1)(1 − Z₀Z₁) / 2Rewards different assignments for vertices 0 and 1
Edge (1, 2)(1 − Z₁Z₂) / 2Rewards different assignments for vertices 1 and 2
Edge (0, 2)(1 − Z₀Z₂) / 2Rewards different assignments for vertices 0 and 2
Triangle totalSum of the three termsThe maximum cut value is 2

The following circuit sketch shows one QAOA layer for a graph with three vertices. Each edge receives a cost interaction, and each qubit receives a mixer rotation:

q0: ──H──RZZ(-γ)────────────RX(2β)──
           │
q1: ──H──RZZ(-γ)──RZZ(-γ)──RX(2β)──
           │       │
q2: ──H────┴───────RZZ(-γ)──RX(2β)──

The exact sign convention depends on how the cost unitary is defined. The important requirement is consistency between the Hamiltonian, circuit gates, and objective function. The code below uses a convention in which RZZ(-γ) implements the relevant two-qubit phase up to a global phase.

Inputs and assumptions

Before running an experiment, record the inputs that affect the result:

  • Graph: vertices and edges, including whether the graph is weighted.
  • Depth: the number of alternating cost and mixer layers, usually called p.
  • Initial parameters: starting values for each gamma and beta.
  • Objective estimator: exact statevector expectation, sampled expectation, or hardware measurements.
  • Optimizer: a derivative-free method is often a practical starting point when measurements are noisy.
  • Evaluation budget: the number of objective evaluations and measurement shots per evaluation.

For a first experiment, use a small unweighted graph and compare the best measured bitstring with a classical Max-Cut solution. This comparison is more informative than looking only at the optimizer's final objective value.

Worked example: a triangle in Qiskit-style Python

The example uses Qiskit's circuit and statevector abstractions together with SciPy's classical optimizer. Qiskit execution APIs change over time, so treat this as a clear implementation template and verify imports against the versions in your environment.

import numpy as np
from scipy.optimize import minimize
from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector, SparsePauliOp

n = 3
edges = [(0, 1), (1, 2), (0, 2)]

def make_qaoa_circuit(gammas, betas):
    p = len(gammas)
    qc = QuantumCircuit(n)
    qc.h(range(n))

    for layer in range(p):
        # Cost unitary for each Max-Cut edge.
        for i, j in edges:
            qc.rzz(-gammas[layer], i, j)
        # X mixer on every qubit.
        for q in range(n):
            qc.rx(2 * betas[layer], q)
    return qc

def zz_label(i, j):
    # Qiskit Pauli labels are written with the highest-index qubit first.
    label = ['I'] * n
    label[n - 1 - i] = 'Z'
    label[n - 1 - j] = 'Z'
    return ''.join(label)

def expected_cut(x, p=1):
    gammas = x[:p]
    betas = x[p:]
    state = Statevector.from_instruction(make_qaoa_circuit(gammas, betas))

    value = 0.0
    for i, j in edges:
        zz = SparsePauliOp.from_list([(zz_label(i, j), 1.0)])
        zz_expectation = np.real(state.expectation_value(zz))
        value += (1.0 - zz_expectation) / 2.0
    return value

def objective(x):
    return -expected_cut(x)

initial = np.array([0.5, 0.8])  # [gamma, beta] for p=1
result = minimize(objective, initial, method='Nelder-Mead')

print('parameters:', result.x)
print('expected cut:', -result.fun)
print(make_qaoa_circuit(result.x[:1], result.x[1:]).draw())

For the triangle, every valid two-group assignment cuts two of the three edges at most. The optimizer should therefore seek an expected value approaching, but not necessarily equal to, 2. An expectation value is an average over all sampled solutions; it is not itself a bitstring. To obtain candidate solutions, add measurements and inspect the most frequent bitstrings.

Conceptually, the measurement workflow is:

1. Build the parameterized QAOA circuit.
2. Optimize parameters using an exact or sampled objective.
3. Bind the best parameters to a measurement-enabled circuit.
4. Run enough shots to obtain counts.
5. Compute the classical cut value for each returned bitstring.
6. Keep the highest-quality bitstring and compare its frequency.

When moving from a statevector to a sampler or real backend, replace exact expectation evaluation with counts or primitive-based expectation estimates. Keep the same cost function so that results remain comparable.

Limitations and a checklist for increasing depth

More QAOA layers add expressive power, but they also increase circuit size, parameter count, optimization effort, and exposure to noise. A deeper circuit is not automatically a better experiment, particularly when two-qubit gates dominate the error budget.

  1. Validate the cost function on a classically solvable graph.
  2. Run a noiseless statevector baseline before using a hardware backend.
  3. Record the best cut value, expected value, optimizer evaluations, and parameter vector.
  4. Increase p one layer at a time rather than changing depth and optimizer simultaneously.
  5. Compare several initial parameter settings because local optimization can be sensitive to initialization.
  6. Transpile for the target device and inspect added gates, especially routed two-qubit operations.
  7. Repeat with a fixed shot budget and report variability across runs.

For weighted Max-Cut, replace each edge term with wᵢⱼ(1 − ZᵢZⱼ)/2. For constrained scheduling or routing problems, the cost Hamiltonian may need penalty terms. Those penalties should be scaled deliberately: a penalty that is too small permits invalid solutions, while one that is too large can make the optimization landscape difficult to explore.

When to recalculate

Recalculate your QAOA baseline whenever the graph, edge weights, depth, optimizer, shot budget, or execution backend changes. A result from a noiseless simulator should not be treated as a hardware benchmark, and a result from one transpilation layout may not transfer to another device.

For a repeatable experiment, save the graph definition, QAOA convention, software versions, initial parameters, optimizer settings, transpiled circuit, shot count, and raw measurement counts. Revisit the experiment after a framework changes its primitives or execution model, and whenever you move from statevector simulation to sampled or hardware execution. This record lets you distinguish an algorithmic improvement from a change caused by noise, compilation, sampling, or an altered API.

Start with the triangle example, verify the classical optimum, then substitute your own graph and increase depth only after the baseline is understood. That incremental workflow makes QAOA useful as a controlled quantum optimization experiment rather than a black-box search.

Related Topics

#QAOA#Max-Cut#quantum algorithms#Qiskit#quantum optimization#NISQ
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.