QAOA is a variational algorithm for solving combinatorial optimization problems. Given a cost function $C(z)$ (where $z$ is a binary string), QAOA constructs a quantum ansatz that preferentially amplifies high-scoring solutions, then measures to sample solutions.

QAOA is a general-purpose algorithm: schedule problems (minimize makepsan), MaxCut (maximum graph cut), satisfiability (SAT), and many others can be formulated as QAOA instances.

A QAOA circuit with depth $p$ has $2p$ parameterized layers:

1. Cost Hamiltonian layer: apply $e^{-i\gamma H_C}$ where $H_C$ encodes the cost function
2. Mixer Hamiltonian layer: apply $e^{-i\beta H_M}$ (usually $H_M = \sum X_i$)

Repeat $p$ times, then measure. Parameters $\gamma = [\gamma_1, \ldots, \gamma_p]$ and $\beta = [\beta_1, \ldots, \beta_p]$ are trained to maximize the expected cost (or minimize, depending on the problem).

from qiskit import QuantumCircuit
from qiskit.circuit import Parameter
import numpy as np
 
# Example: MaxCut on a 3-node graph
p = 2  # QAOA depth
gamma = [Parameter(f'γ_{i}') for i in range(p)]
beta = [Parameter(f'β_{i}') for i in range(p)]
 
qc = QuantumCircuit(3)
 
# Initial superposition
qc.h([0, 1, 2])
 
# QAOA layers
for i in range(p):
    # Cost: phase based on edge weights
    qc.rzz(2 * gamma[i], 0, 1)
    qc.rzz(2 * gamma[i], 1, 2)
 
    # Mixer
    qc.rx(2 * beta[i], 0)
    qc.rx(2 * beta[i], 1)
    qc.rx(2 * beta[i], 2)
 
qc.measure_all()
print(qc.draw())

Optimize $\gamma$ and $\beta$ using a classical optimizer. QAOA samples bitstrings after each evaluation; higher depths and better parameters yield better solutions.

from qiskit_aer import AerSimulator
from qiskit.optimizers import COBYLA
 
def evaluate_cost(params):
    # params = [γ_1, ..., γ_p, β_1, ..., β_p]
    result = sim.run(qc_bound, shots=1000).result()
    counts = result.get_counts()
 
    # Compute expected cost
    cost = sum(
        C(bitstring) * count / 1000
        for bitstring, count in counts.items()
    )
    return -cost  # Minimize negative cost
 
optimizer = COBYLA()
x0 = np.random.rand(2 * p)
result = optimizer.minimize(evaluate_cost, x0=x0)

QAOA depth $p$ affects approximation quality; larger $p$ generally gives better solutions but requires more quantum gates and classical optimization effort.