QAOA
QAOA (Quantum Approximate Optimization Algorithm), kombinatörik optimizasyonu kuantum bir devreyle klasik bir iyileştirme döngüsünü el sıkıştırarak çözen hibrit algoritmadır. Bu derste Max-Cut problemi üzerinden QAOA'yı sıfırdan kuracak, p = 1 için hesabı adım adım yapacak ve sık yanılgıları ayıklayacağız. Serinin tamamı için Kuantum Hesaplama dersleri sayfasına bakabilirsin; kübit ve süperpozisyona hâkim değilsen önce Kuantum Hesaplama 101 dersine bak.
Problem: Kombinatörik Optimizasyon ve Max-Cut
QAOA'nın hedefi: n adet ikili karar (her düğümü A grubuna mı, B grubuna mı koyacağız?) ve 2ⁿ karar dizisinin her birine puan veren maliyet fonksiyonu C(z) tanımlı; en yüksek puanlı diziyi ararız — klasik tarama üstel büyür. Örneğimiz Max-Cut: grafiğin düğümlerini iki gruba böl, gruplar arasında kalan kenar sayısını en büyüt. Üçgende bir düğümü tek bırakmak iki kenar keser ve üçgenin en iyi kesimidir; düğümler çoğaldıkça elle bulmak hızla imkânsızlaşır.
Kararı kübitlere taşımak kolaydır: her düğüme bir kübit, her dizeye baz durumu |z⟩ karşılık gelir. Bitleri ±1 değişkenlerine sᵢ = (−1)^(zᵢ) ile çevirirsek kesim sayısı, her (i, j) kenarı için (1 − sᵢsⱼ)/2 toplanarak bulunur: aynı gruptaki kenar 0, farklı gruptaki 1 puan verir. Operatör karşılığı C = Σ_kenar ½(1 − ZᵢZⱼ)'dir (|0⟩'u +1, |1⟩'i −1 ile çarpan σᶻ'yi Z diye yazdık); bu operatör köşegendir ve C|z⟩ = C(z)|z⟩ özdeğer ilişkisini sağlar; en iyi kesim, C'nin en büyük özdeğerli durumudur. QAOA beklenti değeri ⟨C⟩'yi büyütmeye çalışır.
Devre: Başlangıç, Maliyet ve Karıştırıcı Katmanları
Devre |+⟩'den başlar: her kübite Hadamard uygulanınca kayıt |+⟩^⊗n = (1/√(2ⁿ)) Σ_z |z⟩ olur; her genlik 1/√(2ⁿ) ve karelerin toplamı 1 — durum normalize. Bunun sebebi karıştırıcıdır: B = σₓ₁ + σₓ₂ + ⋯ + σₓₙ için B|+⟩^⊗n = n|+⟩^⊗n, yani başlangıç B'nin özdurumudur.
Sonra iki tür katman p kez tekrarlanır. Maliyet katmanı U(C, γ) = e^(−iγC): C köşegen olduğu için her baz durumuna yalnızca faz basar, U(C, γ)|z⟩ = e^(−iγC(z))|z⟩. Katsayıların büyüklüğü 1 olduğundan katman üniteryendir; olasılıkları değil girişimi değiştirir. Kenar terimleri değişmeli olduğundan her kenara bir çift kübit RZZ(2γ) kapısı yeter; e^(−iγC)'yi devreye çevirmek bir Hamiltonian Simülasyonu meselesidir. Karıştırıcı katmanı U(B, β) = e^(−iβB), tek kübitlere ayrışır ve her parça RX(2β) kapısıdır; çünkü e^(−iβσₓ) = cos β·I − i sin β·σₓ.
İş bölümü: maliyet katmanı iyi kesimlere faz basar; karıştırıcı bu fazları girişime sokup olasılığı çözümlere kaydırır. p katman sonunda |ψ⟩ = U(B, β_p) U(C, γ_p) ⋯ U(B, β₁) U(C, γ₁)|+⟩^⊗n; en sağdaki önce uygulanır; ayarlanacak 2p serbest açı vardır. p büyüdükçe dizilim, B'nin temel durumundan C'ninkine geçen adyabatik evrimin basamaklı yaklaşımına dönüşür; p → ∞'da en iyi kesim bulunur.
Hibrit Döngü: Ölç, Ortalama Al, İyileştir
Devreyi ölçtüğünde bitstring z, P(z) = |⟨z|ψ⟩|² ile çıkar; beklenti değeri F(γ, β) = Σ_z C(z)·P(z) ise ancak ölçüm ortalamasıyla kestirilir. "Hibrit" sıfatı buradan gelir: açıları kuantum devresi, iyileştirmeyi klasik algoritma taşır. Bir tur şöyle işler:
- Hadamard kapılarıyla |+⟩^⊗n hazırla.
- Güncel açılarla p katman uygula.
- Devreyi yüzlerce kez ölç; C(z)'leri puanla, ortalamayı al.
- Klasik iyileştirici (COBYLA, SPSA gibi) ortalamayı büyütecek yeni (γ, β) önersin.
- İyileşme durana dek yinele; son turda en yüksek C(z)'li bitstring'i al.
Bu iskelet VQE Varyasyonel Özdeğer Çözücü dersindeki döngüyle aynı; fark ansatzın kaynağı ve ölçümdür, aşağıda kıyaslıyoruz. ⟨C⟩'yi daha az ölçümle kestirmek için Genlik Tahmini dersine bakabilirsin.
Küçük Bir Hesap: Tek Kenarlı Grafikte p = 1
İki kübit ve aralarında tek kenar alalım: C(00) = C(11) = 0 (kesilmedi), C(01) = C(10) = 1 (kesildi). Başlangıç |++⟩ = ½(|00⟩ + |01⟩ + |10⟩ + |11⟩): dört genlik, her biri ½. γ₁'lik maliyet katmanı |01⟩ ile |10⟩'ya e^(−iγ₁) fazı basar, diğerlerine dokunmaz; β₁'lik karıştırıcı genlikleri komşu durumlar arasında kaydırır. İki katmanı açıp dört olasılığı toplayınca kapalı sonuç çıkar: P(kesim) = ½ + ½·sin(γ₁)·sin(4β₁).
Sınayalım: β₁ = 0'da karıştırıcı yoktur, P(kesim) = ½ — fazlar tek başına yetmez. γ₁ = π/2 ve β₁ = π/8'de iki sinüs de 1 olur: P(kesim) = 1; ölçüm kesinlikle |01⟩ ya da |10⟩ verir; nihai durum, global bir faza kadar −(i/√2)(|01⟩ + |10⟩) olan dolanık bir durumdur. Gerçek grafiklerde manzara engebelidir: p = 1'de üç-düzenli grafiklerde beklenen kesimin en iyinin en az 0,6924 katı olduğu kanıtlandı (Farhi ve ark., 2014); p büyüdükçe oran genelde iyileşir ama açı manzarasında yerel çukurlar belirir.
Sık Yapılan Hatalar ve VQE ile Kıyas
Yanılgıları ayıklamak öğrenmenin yarısıdır:
- "QAOA en iyi sonucu bulur." Hayır; "yaklaşık" sözü oradadır: kalite p'ye ve açı optimizasyonuna bağlıdır. İyileştiricinin büyüttüğü şey ⟨C⟩ ortalamasıdır; verdiğin cevap tek bir bitstring'dir, son turda bol örnekleyip en iyisini seç.
- "Karıştırıcı her zaman σₓ'lerin toplamı olmalı." Görevi, çözüm kümesi içinde kalırken olasılığı taşımaktır; sabit sayıda 1 isteyen problemlerde XY tipi karıştırıcı kullanılır.
- "Derin devre her zaman daha iyi." Teoride p → ∞ iyidir; gürültülü donanımda derinlik sinyali bozar. QAOA sığ devrelerle çalışabildiği için güncel cihazlara uygundur; gürültünün yıkımını Hata Toleranslı Kuantum Hesaplama ve Mantıksal Kübitler derslerinde işlemiştik.
- "QAOA her problemde klasikten hızlıdır." Genel bir kanıt yok; klasik taklidi kolaylaşan sınıflar bile biliniyor. Umut, problem yapısına tam oturan ansatstadır.
QAOA ile VQE arasındaki fark nedir?
- Ansatz: VQE'nin devresi çoğunlukla kimya bilgisiyle tasarlanır; QAOA'nınki problemden, C ve B'den doğar.
- Hedef: VQE bir Hamiltonyenin temel enerjisini en küçükler; QAOA kombinatörik maliyetin beklentisini iyileştirir.
- Ölçüm: VQE enerji terimlerini ayrı kestirir; QAOA baz durumlarında örnekleyip puan ortalaması alır.
QAOA ana kübit platformlarında koşuyor: kapılı süperiletken kübitlerde derinliği düşük tutmaya, nötr atomlarda Rydberg engellemesinin graf yapısıyla doğal uyumuna güvenilir.
Sık Sorulan Sorular
QAOA nedir ve hangi problemlerde kullanılır?
Kombinatörik optimizasyon problemleri için hibrit bir kuantum algoritmasıdır: problemden türeyen p katmanlı bir devre, klasik iyileştiricinin ayarladığı 2p açıyla çalışır ve ölçüm ortalaması ⟨C⟩ iyileştirilir. Max-Cut, en küçük düğüm kapsaması gibi problemlerde kullanılır.
QAOA ile VQE arasındaki fark nedir?
İkisi de varyasyonel (hibrit) algoritmadır; fark ansatzın kaynağı ve hedeftir: VQE'nin devresi çoğunlukla kimya bilgisiyle kurulur ve bir Hamiltonyenin temel enerjisini arar; QAOA'nın devresi doğrudan maliyet C ile karıştırıcı B'den doğar ve kombinatörik maliyeti iyileştirir.
QAOA'da p parametresi neyi kontrol eder?
p, üst üste binen maliyet + karıştırıcı katman çiftlerinin sayısıdır; 2p serbest açı doğurur. p büyüdükçe devre adyabatik evrimin daha iyi yaklaşımına dönüşür; ama gürültü derinlikle sinyali bozabildiğinden p, cihazın kaldırdığı kadar seçilir.
QAOA klasik algoritmalardan kesin olarak daha mı iyidir?
Hayır; pratik ölçekte üstünlük kanıtı yoktur, klasik taklidi kolaylaşan sınıflar bile bilinir. Kesin sonuçlar mütevazıdır: p = 1'de üç-düzenli grafiklerde beklenen kesim, en iyinin en az 0,6924 katıdır.
Kaynaklar ve İleri Okuma
Farhi, Goldstone, Gutmann — A Quantum Approximate Optimization Algorithm (arXiv:1411.4028) — QAOA'yı tanıtan 2014 makalesi; 0,6924 sınırı buradan gelir.
Quantum optimization algorithms — Wikipedia — QAOA'nın kuantum optimizasyondaki yerine kısa bakış.
Qiskit: Max-Cut and Traveling Salesman Problem — Max-Cut'i Ising Hamiltonyenine çevirip varyasyonel çözücülerle çözen resmî eğitim.
PennyLane: Intro to QAOA — maliyet ve karıştırıcı katmanlarından devre kuran uygulamalı anlatım.