Kuantum Karmaşıklık Sınıfı BQP

Bir bilgisayarın neyi “makul sürede ve güvenilir biçimde” çözebildiğini konuşmak için karmaşıklık sınıfları tanımlanır; kuantum bilgisayarın resmî karnesi de BQP (Bounded-error Quantum Polynomial time) sınıfıdır. Bu derste BQP'yi harfi harfine tanımlayacak, klasik akrabası BPP ile karşılaştıracağız, bilinen içerme zincirini kuracağız ve sınıfın neyi çözdüğüyle neyi çözmediğini somut örneklerle ayıracağız. Serinin tamamı için Kuantum Hesaplama dersleri sayfasına, sınıf kavramının klasik temeli için Klasik Karmaşıklık Sınıfları P ve NP dersine bakabilirsin.

BQP Nedir? Tanımın Üç Ayarı

Bir karar problemi L, BQP'dedir derken kastımız şudur: giriş uzunluğu n olan her x için çalışan, polinom sayıda kapıdan oluşan ve tek tip (uniform) bir kuantum devre ailesi Qₙ öyle vardır ki — x ∈ L ise devrenin 1 (evet) ölçme olasılığı en az 2/3; x ∉ L ise bu olasılık en çok 1/3'tür. Tanım üç ayar taşır. Kuantum: hesap, |ψ⟩ = Σₓ αₓ|x⟩ gibi süperpozisyonlar üstünde üniteryen kapılarla yürür; n kübitlik kayıt 2ⁿ genlik taşır ve ölçüm, |αₓ|² olasılığıyla sonuç verir. Polinom zaman: kapı sayısı n ile polinom biçimde büyür. Sınırlı hata (bounded error): doğru cevap, 1/2'den belirgin biçimde büyük sabit bir olasılıkla gelir.

2/3 hem keyfî hem değildir: 1/2 ile 1 arasındaki hangi sabiti koyarsan aynı sınıf çıkar, çünkü hata tekrarlamayla üstel biçimde söndürülebilir. Küçük bir hesap akışı:

1. Aynı girişte devreyi k kez bağımsız koştur; her koşumda 1 ya da 0 ölç.
2. Oyları topla; 1 çoğunluksa “evet” de.
3. x ∈ L ise her koşum en az 2/3 olasılıkla 1 verir; yani 1'lerin beklenen payı 2/3'tür.
4. Hoeffding eşitsizliğiyle yanlış çoğunluk olasılığı en çok e^(−k/18) olur: k = 90 için bu e⁻⁵ ≈ %0,67.
5. Toplam maliyet 90 · poly(n) kalır: hâlâ polinom, yani sınıf değişmez.

İki incelik daha: ertelenmiş ölçüm ilkesine göre ara ölçümleri en sona taşımak kabul olasılığını hiç değiştirmez, bu yüzden tanımda tek bir son ölçümle yetinilir. “Tek tip olma” şartı ise P ve BPP tanımlarındaki uniformity şartının kuantum karşılığıdır: devreleri n'den üreten gerçek bir algoritma bulunmalıdır.

BQP ile BPP: Tek Fark, Kapılar

BQP'nin en yakın klasik akrabası, Olasılıksal Karmaşıklık BPP dersinde tanımlanan BPP'dir: yazma-tura atan bir klasik makine, polinom zamanda ve en çok 1/3 hatayla karar verir. Çerçeve birebir aynıdır — karar problemi, polinom zaman, sabit hata payı; tek fark, ara adımların neyle yürütüldüğüdür:

• BPP rastgele bitler taşır; olasılıklar yalnızca toplanır, girişim yoktur.
• BQP üniteryen kapılarla genlikleri toplar ve silebilir; girişim, sonda ölçülen dağılımı değiştirir.
• İkisinde de ölçüm olasılıksaldır; hata, aynı tekrar tekniğiyle söndürülür.
• P ⊆ BPP ⊆ BQP zinciri bilinir: klasik kapılar tersinir biçimde kuantum devresine çevrilir, Hadamard kapısı da (|0⟩ + |1⟩)/√2 hazırlayıp ölçerek adil yazma-tura sağlar; yani BPP'nin yaptığı her iş BQP'de yapılabilir.

BQP'nin Haritadaki Yeri

Kuantumun gücünü tartarken pusulamız şu zincirdir: P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE. BQP'yi 1990'larda Bernstein ve Vazirani tanımladı; BQP'nin PP'ye girdiği Adleman–DeMarrais–Huang'ın 1997 sonucudur. Katılıklar ise açık sorudur: BQP ≠ P mi, BQP ile NP arasında nasıl bir ilişki var mı — hiçbiri kanıtlanmadı. Çarpanlara ayırmanın BQP'de olması BQP ≠ P'yi kanıtlamaz; o problemin P'de olmadığı da kanıtlanabilmiş değildir.

• Bilinen: P ve BPP BQP'nin içinde; BQP, PP ve PSPACE'nin içinde.
• Açık: BQP ≠ P mi; BQP ile NP arasındaki ilişkinin iki yönü de bilinmiyor.
• Oracle işaretleri: bazı oracle'lara göre NP ⊄ BQP (Grover'ın yalnızca karekök vermesi); bazılarına göre BQP ⊄ NP, hatta polinom hiyerarşisi PH bile (Raz–Tal 2019). Oracle ayrışmasının ne anlama geldiğini Oracle Modelleri dersi işliyor.

BQP'de Ne Var, Ne Yok?

Bir sınıf, içinde bilinen algoritmalarla şekillenir. BQP'nin vitrininde üç büyük kalem var:

• Çarpanlara ayırma ve ayrık logaritma: Shor algoritmasıyla polinom zamanda; BQP'yi dünyaya tanıtan sonuç → Shor Algoritması.
• Kuantum sistemlerinin simülasyonu: Feynman'ın ilham verdiği, sınıfın kuruluş motivasyonu; molekül ve malzeme hesapları bugün en gerçekçi kuantum uygulaması sayılır.
• Yapılandırılmamış arama: N adayda O(√N) sorgu; üstel değil, karekök düzeyinde hızlanma → Kuantum Hızlanması.

Neyin olmadığı en az bunun kadar önemli: NP-tam problemler için BQP'de polinom zamanlı algoritma bilinmiyor ve elimizdeki işaretler aksini söylüyor. Somut sayalım: n değişkenli 3-SAT'ın aday uzayı 2ⁿ'dir; Grover'ı uygulasan bile sorgu sayısı O(2^(n/2)) ≈ 1,41ⁿ kalır — üstellikten kurtulamazsın. Kanıt tabii yok; hızlanmanın cinsinin problemden probleme değiştiğini gösteren sorgu alt sınırlarını Sorgu Karmaşıklığı dersi inceliyor.

Sık Yapılan Hatalar ve Yanılgılar

• “BQP tüm zor problemleri çözer.” Hayır; NP-tam problemler için polinom zamanlı kuantum algoritması yoktur ve varolması da beklenmez.
• “2/3 sabiti tanımın kalbidir.” Değil; 1/2'den büyük her sabit aynı sınıfı verir, hata k tekrarla üstel söner.
• “BQP ≠ P kanıtlandı.” Hayır; ⊆ biliniyor, katılık açık. Shor güçlü bir kanıttır ama kanıt değildir.
• “BQP ⊆ NP ya da NP ⊆ BQP biliniyor.” İkisi de açık; yalnızca oracle ayrışmaları var, onlar da dünya içindeki soruyu kapatmaz.
• “BQP gürültülü makineleri tanımlar.” Tanımlamaz; sınıf ideal (gürültüsüz) kübitler üstünde kurulur. Gürültüyle mücadele sonraki ünitenin konusudur — Bit Flip ve Phase Flip Hataları tam bu boşluğu doldurur.

Özetle BQP, “polinom zamanda, sınırlı hatayla, kuantum” demenin ortak dilidir; kuantum hesaplamanın neyi vaat ettiğini, neyi vaat etmediğini bu ölçüyle konuşuruz. Tüm dersler için konu anlatımı indeksine, hesaplamanın geleceği için Yapay Zekâ derslerine, klasik temeller için Yazılım (Bilgisayar) derslerine göz atabilirsin.

Kaynaklar ve İleri Okuma

BQP — Vikipedi (İngilizce) — Sınıfın tanımı, bilinen içerme ilişkileri ve oracle sonuçlarının özeti.

Quantum Complexity Theory (Bernstein–Vazirani, SIAM J. Comput. 26(5), 1997) — BQP'yi bugünkü biçimiyle tanımlayan temel makale.

Quantum Computing Since Democritus — Ders Notları (S. Aaronson) — Karmaşıklık sınıfları ile kuantumun gücü arasındaki bağı erişilebilir biçimde işleyen notlar.

Quantum Computing — Stanford Encyclopedia of Philosophy — Kuantum hesaplamanın gücü ve sınırlarına dair hakemli genel bakış.