QAOA erklärt: Max-Cut Schritt für Schritt lösen

QAOA (Quantum Approximate Optimization Algorithm) ist einer der am meisten gehypten Quantenalgorithmen der nahen Zukunft — und das aus gutem Grund. Er ist ein ernsthafter Kandidat für einen Quantenvorteil bei kombinatorischen Optimierungsproblemen, er läuft auf heutiger NISQ-Hardware, und er ist zugänglich genug, um ihn an einem Nachmittag zu implementieren.

Diese Anleitung baut die vollständige QAOA-Pipeline von Grund auf, mit Max-Cut als Beispielproblem. Am Ende wirst du verstehen, was QAOA tatsächlich tut, wie man es implementiert und wann es sich lohnt, es einzusetzen.

Was ist Max-Cut?

Max-Cut ist ein Graphenpartitionierungsproblem: Gegeben ist ein Graph, und die Knoten sollen in zwei Gruppen (0 und 1) aufgeteilt werden, um die Anzahl der Kanten zu maximieren, die zwischen den Gruppen verlaufen. Es ist im Allgemeinen NP-schwer, tritt im VLSI-Chipdesign, beim Clustering und in der Netzwerkanalyse auf und lässt sich sauber auf Quantenhardware abbilden.

Hier ist ein einfacher Graph mit 4 Knoten:

0 --- 1
|   \ |
3 --- 2

Der maximale Schnitt dieses Graphen ist 4 (die Kanten 0-1, 1-2, 2-3, 3-0 verlaufen alle über die Grenze). Unser Ziel: die Bitfolge 0101 oder 1010 finden, die dies erreicht.

Die Idee hinter QAOA

QAOA ist ein variationeller Hybridalgorithmus. Er wechselt zwischen zwei parametrisierten Operationen ab:

1. Problem-Unitary U_C(γ) — kodiert die Kostenfunktion (Kantenübergänge) als Phasen-Kickback
2. Mischer-Unitary U_B(β) — mischt zwischen Lösungen (X-Rotationen)

Mit p Schichten dieser abwechselnden Unitaries bereitet QAOA einen Quantenzustand vor, dessen Messung wahrscheinlich eine gute Lösung liefert. Ein klassischer Optimierer stimmt die 2p Winkel (γ, β) so ab, dass der erwartete Schnittwert maximiert wird.

QAOA mit PennyLane aufbauen

import pennylane as qml
import numpy as np
from scipy.optimize import minimize

# Graph edges
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]
n_qubits = 4

dev = qml.device("default.qubit", wires=n_qubits)

def cost_unitary(gamma):
    """Encode the Max-Cut cost into phases."""
    for u, v in edges:
        qml.CNOT(wires=[u, v])
        qml.RZ(2 * gamma, wires=v)
        qml.CNOT(wires=[u, v])

def mixer_unitary(beta):
    """Apply X-rotation mixer to all qubits."""
    for i in range(n_qubits):
        qml.RX(2 * beta, wires=i)

@qml.qnode(dev)
def qaoa_circuit(params, p=1):
    gammas = params[:p]
    betas = params[p:]
    # Start in uniform superposition
    for i in range(n_qubits):
        qml.Hadamard(wires=i)
    # Alternate p layers
    for layer in range(p):
        cost_unitary(gammas[layer])
        mixer_unitary(betas[layer])
    return qml.probs(wires=range(n_qubits))

def expected_cut(params, p=1):
    """Classical cost function: expected number of cut edges."""
    probs = qaoa_circuit(params, p)
    total = 0.0
    for bitstring_idx, prob in enumerate(probs):
        bits = format(bitstring_idx, f'0{n_qubits}b')
        cut = sum(1 for u, v in edges if bits[u] != bits[v])
        total += prob * cut
    return -total  # Minimize negative cut

# Optimize p=1 QAOA
p = 1
init_params = np.random.uniform(0, np.pi, 2 * p)
result = minimize(expected_cut, init_params, method='COBYLA',
                  options={'maxiter': 200})

print(f"Optimized params: {result.x}")
print(f"Expected cut: {-result.fun:.3f} / 4.0 maximum")

Bei der Ausführung wird typischerweise expected_cut ≈ 3.5 mit p=1 erreicht — 87,5 % des maximalen Schnitts.

Die beste Lösung sampeln

Nach der Optimierung wird der Schaltkreis gesampelt, um die wahrscheinlichsten guten Lösungen zu finden:

@qml.qnode(dev)
def sample_circuit(params, p=1, shots=1000):
    gammas = params[:p]
    betas = params[p:]
    for i in range(n_qubits):
        qml.Hadamard(wires=i)
    for layer in range(p):
        cost_unitary(gammas[layer])
        mixer_unitary(betas[layer])
    return qml.sample(wires=range(n_qubits))

samples = sample_circuit(result.x, shots=1000)

# Count cut values for each bitstring
from collections import Counter
cut_counts = Counter()
for bits in samples:
    key = ''.join(str(b) for b in bits)
    cut = sum(1 for u, v in edges if bits[u] != bits[v])
    cut_counts[(key, cut)] += 1

# Show top 5 most frequent bitstrings
for (bits, cut), count in sorted(cut_counts.items(), key=lambda x: -x[1])[:5]:
    print(f"{bits}  cut={cut}  frequency={count/10:.1f}%")

Erwartete Ausgabe:

0101  cut=4  frequency=28.3%
1010  cut=4  frequency=27.1%
0110  cut=3  frequency=8.4%
...

Die optimalen Lösungen (0101 und 1010) dominieren — QAOA hat ihre Wahrscheinlichkeit verstärkt.

Dasselbe Problem mit HLQuantum

Das eingebaute QAOA von HLQuantum erlaubt es dir, den Aufbau des Schaltkreises vollständig zu überspringen:

import hlquantum as hlq

graph = [(0, 1), (1, 2), (2, 3), (3, 0)]

result = hlq.algorithms.qaoa(
    graph=graph,
    problem='max_cut',
    p=2,
    backend='pennylane',
    shots=2000,
)

print(result.best_solution)   # '0101' or '1010'
print(result.cut_value)       # 4
print(result.approximation_ratio)  # ~0.96 for p=2

Backends lassen sich mit einem einzigen Flag wechseln:

# Run on Qiskit Aer
result_qiskit = hlq.algorithms.qaoa(graph=graph, problem='max_cut', p=2, backend='qiskit')

# Run on real IonQ hardware (if you have credits)
result_ionq = hlq.algorithms.qaoa(graph=graph, problem='max_cut', p=2,
                                   backend='ionq', device='aria-1')

p erhöhen für bessere Ergebnisse

Das QAOA-Approximationsverhältnis verbessert sich mit der Tiefe p. Bei p→∞ löst QAOA das Problem exakt. In der Praxis:

Der Kompromiss: Tiefere Schaltkreise sammeln auf echter Hardware mehr Rauschen an. Auf Simulatoren nutze p=3 oder höher. Auf NISQ-QPUs ist p=1 oder p=2 üblicherweise die praktische Grenze.

Wann lohnt sich der Einsatz von QAOA?

Derzeit nützlich für:

• Benchmarking von NISQ-Geräten (QAOA ist ein Standard-Benchmark-Schaltkreis)
• Akademische Forschung zu variationellen Quantenalgorithmen
• Kleine Graphen (unter 20 Knoten) auf Simulatoren

Noch nicht nützlich für:

• Produktionsoptimierung auf echter Hardware im großen Maßstab — klassische Heuristiken (Simulated Annealing, Tabu-Suche) übertreffen QAOA bei praktischen Problemen nach wie vor
• Große Graphen — die Schaltkreistiefe skaliert mit der Graphendichte

Das Versprechen: Auf zukünftiger fehlertoleranter Hardware mit tiefen Schaltkreisen könnte QAOA bei großem p echte Beschleunigungen für dichte NP-schwere Optimierung liefern. Die theoretischen Grundlagen sind solide; die Hardware ist noch nicht so weit.

Nächste Schritte

• PennyLane SDK guide — richte PennyLane für weitere variationelle Algorithmen ein
• VQE guide — der Schwesteralgorithmus für die Quantenchemie
• HLQuantum — führe QAOA mit einer einzigen API auf jedem Backend aus