Bernstein-Vazirani Algoritması

1990’ların başında Ethan Bernstein ve Umesh Vazirani, klasik bilgisayarın en az n sorgu gerektirdiği bir problemi kuantum bilgisayarın tek oracle sorgusuyla çözebileceğini gösterdi; Bernstein-Vazirani algoritması bu yüzden kuantum hesaplamanın klasik olasılıksal hesaplamadan farklı olabileceğinin ilk kanıtlarından sayılır. Bu derste problemi tanımlayacak, faz geri vuruşu hilesini kuracak ve devreyi küçük bir örnekle adım adım hesaplayacağız. Serinin tamamı için Kuantum Hesaplama dersleri sayfasına bakabilirsin.

Problem: Oracle’ın İçindeki Gizli Bit Dizisi

Problemi netleştirelim. Elinde bir siyah kutu, yani oracle var: n bitlik bir x alıyor ve f(x) = a·x = a₀x₀ ⊕ a₁x₁ ⊕ ⋯ ⊕ aₙ₋₁xₙ₋₁ hesaplıyor. Burada · olağan çarpma değil, mod 2’de bit bazlı iç çarpımdır: her aᵢ ile xᵢ’yi çarpıp (mantıksal VE) sonuçları mod 2’de topla (XOR). a₀a₁⋯aₙ₋₁ kutuya gömülü gizli dizidir; soru, onu en az kaç sorguyla öğrenebileceğindir.

Klasik cevap n sorgudur ve bu sayı iyileştirilemez: 100⋯0 girdisi sana f(100⋯0) = a₀’ı verir, 010⋯0 ile a₁’ı öğrenirsin; her sorgu diziden tam bir bit açar. Daha azı mümkün değildir, çünkü her sorgu en fazla 1 bit yeni bilgi taşır, öğrenilecekse n bağımsız bilinmeyen bit vardır. Bernstein-Vazirani’nin iddiası bu sınırda başlar: kuantum bilgisayar aynı oracle’ı tek kez çağırıp dizinin tamamını öğrenir.

Faz Geri Vuruşu: Oracle’ı Faz Kaynağına Çevirmek

Algoritmanın motoru, önceki derste Deutsch-Jozsa Algoritması’nda gördüğümüz faz geri vuruşu (phase kickback) hilesidir. Kuantum oracle f’yi iki kayıt üzerinde üniter kılar: U_f|x⟩|y⟩ = |x⟩|y ⊕ f(x)⟩; tanım üniterdir çünkü U_f’i iki kez uygulamak başlangıca döndürür. Asıl hile yardımcı kübiti |0⟩ ya da |1⟩ yerine |−⟩ = (|0⟩ − |1⟩)/√2 durumuna hazırlamaktır: |−⟩’nin bileşenlerini değiştirmek, dalgaya (−1)^f(x) çarpmaya denktir. Yani

U_f|x⟩|−⟩ = (−1)^(f(x))|x⟩|−⟩.

|−⟩, her U_f’nin f(x) değerine bağlı özdeğerli özvektörüdür; oracle artık bilgiyi bitlere değil dalganın faz desenine yazar. Yardımcı kübit saptığı için dolanıklık oluşmaz; sonraki hesap tek giriş kaydı üstünde döner. Faz tek başına ölçülemez ama Hadamard katmanı bu deseni okunabilir bite çevirir.

Algoritma Adım Adım

Devre n giriş kübiti ve 1 yardımcı kübit üstünde dört adımdan oluşur:

1. Başlangıç: |0⟩^⊗n|1⟩; girişler sıfırda, yardımcı kübit |1⟩’de.
2. İlk Hadamard katmanı: tüm kübitlere H uygulanır: girişler |s⟩ = (1/√2ⁿ) Σₓ |x⟩’e gider (H|0⟩ = |+⟩), yardımcı kübit H|1⟩ = |−⟩ ile faz geri vuruşuna hazırlanır.
3. Oracle sorgusu (tek sorgu): faz geri vuruşuyla durum (1/√2ⁿ) Σₓ (−1)^(a·x)|x⟩ ⊗ |−⟩ olur; gizli dizi artık işaret fonksiyonu (−1)^(a·x) olarak kodlanmıştır.
4. İkinci Hadamard katmanı ve ölçüm: girişlere yeniden H^⊗n uygulanır ve giriş kaydı ölçülür.

Son adım neden a verir? Hadamard’ın temel özdeşliğine bak: H^⊗n|x⟩ = (1/√2ⁿ) Σᵧ (−1)^(x·y)|y⟩. Bu Walsh-Hadamard dönüşümü bit desenleri ile faz profillerini bire bir eşler; 3. adımdaki profil (−1)^(a·x) olduğundan H^⊗n bu durumu |a⟩’ya taşır:

H^⊗n (1/√2ⁿ) Σₓ (−1)^(a·x)|x⟩ = |a⟩.

Bu yüzden ölçüm ideal devrede gizli diziyi olasılık 1 ile verir; tahmin yok, istatistik yok. Norm da yerinde durur: H ve U_f üniterdir, normu korur.

Küçük bir hesap: n = 3, gizli dizi a = 101

Girdi |000⟩|1⟩; ilk Hadamard katmanından sonra durum (1/√8) Σₓ |x⟩|−⟩. Oracle, f(x) = x₀ ⊕ x₂ olduğundan (−1)^(x₀⊕x₂) fazlarını yazar. Çarpan kübit bazına ayrışır: her i için (1/√2) Σₓᵢ (−1)^(aᵢxᵢ)|xᵢ⟩; yani aᵢ = 0 ise kübit |+⟩’ta, aᵢ = 1 ise |−⟩’ta kalır. Giriş kaydı böylece |−⟩ ⊗ |+⟩ ⊗ |−⟩ olur — 1’ler tam da |−⟩’ye düşen kübitlerdir. Son Hadamard katmanı H|−⟩ = |1⟩, H|+⟩ = |0⟩ kuralıyla bunu |1⟩|0⟩|1⟩’e çevirir; ölçüm 101 verir. n kaç olursa olsun akış aynıdır: faz deseni Hadamard’dan geçince doğrudan bit dizisi olarak okunur.

Klasikle Karşılaştırma ve Algoritmanın Yeri

• Sorgu sayısı: klasik en iyi n sorgu, kuantum 1 sorgu; ayırma sorgu sayısında üsteldir, kapı sayısına bakarsan polinom düzeyine iner.
• Deutsch-Jozsa ile ilişki: Deutsch-Jozsa, f’nin sabit mi dengeli mi olduğunu ayrıştırır; BV, f’nin doğrusal olacağı garanti edildiğinde özel hâlidir (bu ailenin tek kübitlik ucu Deutsch Algoritması’dır). Aynı devre, garantili durumda ayrıştırma değil, gizli dizinin kendisini verir.
• Tarihsel önem: Bernstein-Vazirani (1993/1997), BQP’nin BPP’den farklı olabileceğinin ilk oracle ayrışmasını verdi; Simon Algoritması ve Shor’ın yolu buradan açıldı.
• Dürüst bir not: doğrusal fonksiyonu öğrenmek pratikte zor değildir; değer, ilke kanıtında. Gerçek üstel kazançlar Simon ve Shor’un konusudur.

Bu bağlamı karmaşıklık tarafına taşımak istersen Kuantum Karmaşıklık Sınıfı BQP dersi bu ayrışmanın çerçevesini çizer.

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

• Yardımcı kübiti |+⟩’ye hazırlamak: faz geri vuruşu ancak |−⟩ özvektörüyle çalışır; |+⟩’de oracle dolanıklık kurar ve ölçüm rastgeleşir. Doğru başlangıç |1⟩’dir; ilk Hadamard onu |−⟩’ye taşır.
• a·x’i sıradan çarpma sanmak: burada ·, AND-sonra-XOR (mod 2 iç çarpım) anlamındadır; tamsayı çarpımı değil. 101 · 011 = 0⊕0⊕1 = 1 gibi hesaplanır.
• “Algoritma bazen yanılmaz mı?” diye düşünmek: ideal devrede ölçüm a’yı olasılık 1 verir; hata yalnızca gürültülü donanımdan gelir, algoritmanın kendisinden değil.
• Tek sorguyu bedava sanmak: oracle’ın kendisi CX kapılarıyla kurulur; derinlik ve bağlantı kısıtları gerçek maliyettir. Gerçek cihazda çok sayıda deneme (shot) alıp sonucu istatistiksel okumak gerekir.

Gürültülü cihazda devreyi çalıştırmayı Backend ve Cihaz Kavramı, ölçüm sayılarını okumayı Sonuçların İstatistiksel Analizi dersi anlatır; ideal %100 ile gerçek donanımdaki %90-99 arasındaki farkın sebebi gürültüdür.

Kaynaklar ve İleri Okuma

Bernstein–Vazirani algorithm (Wikipedia) — Algoritmanın devresi, klasik n sorgu karşılaştırması ve BQP-BPP bağlamının kısa özeti.

Fundamentals of Quantum Algorithms (IBM Quantum Learning) — IBM’in ücretsiz kuantum algoritmaları kursu; Deutsch-Jozsa ve Simon dersleri bu dersin doğrudan komşularıdır.

Quantum complexity theory (Wikipedia) — BV’nin tarihsel ayrışmasını konumlandıran BQP, BPP ve oracle modeli çerçevesi.

Hadamard transform (Wikipedia) — Bit desenini faz profiline çeviren Walsh-Hadamard dönüşümünün matematiksel tanımı.