Site Tools


qiskit-qaoa

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:

  1. Cost Hamiltonian layer: apply where encodes the cost function
  2. 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.

qiskit-qaoa.md · Last modified: