Table of Contents
QAOA (quantum approximate optimization algorithm)
QAOA is a variational algorithm for solving combinatorial optimization problems. Given a cost function (where 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.
QAOA circuit
A QAOA circuit with depth has parameterized layers:
- Cost Hamiltonian layer: apply where encodes the cost function
- Mixer Hamiltonian layer: apply (usually )
Repeat times, then measure. Parameters and 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())
Training and results
Optimize and 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 affects approximation quality; larger generally gives better solutions but requires more quantum gates and classical optimization effort.
