QuellengeprüftLevel 3

QAOA (Quantum Approximate Optimization Algorithm)

QAOA ist ein hybrider quanten-klassischer Algorithmus für kombinatorische Optimierung: Kosten- und Mixer-Schichten wechseln sich ab, ein klassischer Optimierer stimmt die Parameter ab.

Was es bedeutet

Ausgehend von |+>^n wechseln sich p Schichten aus Kosten-Hamiltonian-Evolution exp(-i*gamma*C) und Mixer-Evolution exp(-i*beta*B) ab.Ein klassischer Optimierer stellt die 2p Winkel ein, um den Erwartungswert von C zu maximieren.Mit wachsendem p sinkt die erreichbare Näherungsqualität nicht; im Grenzfall p gegen unendlich verbindet sich QAOA mit dem adiabatischen Algorithmus.

Alltagsvergleich

Wie Teig in Runden kneten: einmal in Richtung der gewünschten Form drücken (Kostenschicht), dann falten und mischen (Mixerschicht) -- nach einigen Runden ist der Teig der Form viel näher.
Der klassische Optimierer ist der Trainer, der Quantenschaltkreis der Athlet: der Trainer sieht die Punktzahl und passt die Einstellungen an.

Häufige Missverständnisse

  • Kein garantierter Vorteil gegenüber klassischen Optimierern -- ein allgemeiner bewiesener Speedup ist nicht bekannt.
  • Bei endlichem p ist QAOA approximativ -- kein zertifiziertes Optimum.
  • Nicht rein quantenmechanisch, sondern ein Hybrid mit klassischem Optimierer.

Das Wichtigste

  • Wechselt p-mal Kosten- und Mixer-Schichten ab, Start bei |+>^n.
  • Klassischer Optimierer stimmt 2p Winkel ab.
  • Näherungsqualität nicht-fallend in p; Verbindung zum adiabatischen Algorithmus.

Verständnis prüfen

Welche zwei Operationen wechseln sich in jeder QAOA-Schicht ab?

  1. A.Orakel und Diffusion
  2. B.Kosten-Hamiltonian- und Mixer-Hamiltonian-Evolution
  3. C.QFT und inverse QFT
  4. D.Kodierung und Fehlerkorrektur
Antwort anzeigen

Antwort: B. Kosten-Hamiltonian- und Mixer-Hamiltonian-Evolution

Warum: Kosten-Evolution unter C und Mixer-Evolution unter B, Winkel klassisch abgestimmt.

Baut auf

QubitSuperpositionQuantenmessungHybrides Quanten-Klassik-RechnenVariationeller Quanten-Eigenwertlöser (VQE)

Primärquelle: Farhi, Goldstone, Gutmann, A Quantum Approximate Optimization Algorithm, arXiv:1411.4028 (2014)

Graded 2026-07-10 (human sign-off): established per Farhi, Goldstone, Gutmann arXiv:1411.4028 (2014).

Praktisch lernen

Dieses Konzept ist Teil eines Curriculums mit 46 Leveln, einem interaktiven Simulator und Lumen — einem Tutor, dessen Antworten vor der Anzeige geprüft werden. Level 1–5 sind kostenlos.

Kostenlos startenZum Curriculum