Deutsch–Jozsa: tek soruda kesin cevap

Bir fonksiyonun sabit mi dengeli mi olduğunu tek bir sorguda kesin olarak bulan ilk kuantum algoritması. Faz geri tepmesi ve kâhin kavramlarını tanı.

Problem

Elimizde bit dizilerini alıp 0 ya da 1 döndüren bir fonksiyon f var; içini göremiyoruz, yalnızca sorabiliyoruz. Bize söz verilmiş: f ya sabittir (her girişe aynı cevabı verir) ya da dengelidir (girişlerin tam yarısına 0, yarısına 1 verir). Hangisi?

n bitlik girişlerde klasik bir bilgisayar en kötü durumda girişlerin yarısından bir fazlasını sormak zorundadır. Deutsch–Jozsa algoritması ise tek bir sorguyla kesin cevap verir.

Kâhin ve faz geri tepmesi

Kuantum algoritmalarında fonksiyon bir “kâhin” (oracle) devresiyle verilir. Kâhin, yardımcı kübiti f(x) ile XOR’lar. Yardımcı kübit önce X ve H ile (|0⟩ − |1⟩)/√2 durumuna getirilirse ilginç bir şey olur: XOR yardımcı kübiti değiştirmez, onun yerine girişe (−1)^f(x) fazı yazılır. Buna faz geri tepmesi denir.

Deneme alanındaki örnekte q0 ve q1 giriş, q2 yardımcı kübittir. İki CNOT, f(x) = x0 XOR x1 fonksiyonunu kodlar; bu fonksiyon dengelidir.

Neden tek sorgu yeter?

Girişler H ile bütün olası değerlerin süperpozisyonuna sokulur, kâhin her birine kendi fazını yazar, sonra girişlere tekrar H uygulanır. Fonksiyon sabitse bütün fazlar aynıdır ve girişim girişleri kesin olarak 00…0’a döndürür. Dengeliyse 00…0’ın genliği tam olarak sıfırlanır.

Yani girişlerde 00 görürsen fonksiyon sabittir, başka bir şey görürsen dengelidir; olasılık değil, kesinlik. Problem yapay görünse de kâhin ve faz geri tepmesi fikri Grover, Shor ve faz tahmininin temelidir.

Kendin dene

İki CNOT’u kaldır: kâhin artık hiçbir şey yapmaz, yani f sabit 0 olur. Girişler (q1 q0) 00 okur; sonuç 100’e döner.

Tarayıcıda dene (kurulum yok)

Akılda kalsın

Kâhin, fonksiyonu bir kuantum devresi olarak verir.
Yardımcı kübit (|0⟩ − |1⟩)/√2 durumundaysa kâhin girişe (−1)^f(x) fazını yazar: faz geri tepmesi.
Sabit fonksiyonda girişler kesin olarak 00…0, dengelide hiçbir zaman 00…0 okunmaz.
Klasik olarak en kötü durumda üstel sayıda sorgu gerekir; kuantumda tek sorgu yeter.

Kendini sına

Deutsch–Jozsa devresinde girişler 00 dışında bir değer okursa ne anlarız?

Fonksiyon sabittir
Fonksiyon dengelidir
Hiçbir şey; tekrar ölçmek gerekir

Cevabı göster

Fonksiyon dengelidir. Sabit fonksiyonda girişim girişleri kesin olarak 00…0’a döndürür; başka bir sonuç, fonksiyonun dengeli olduğunu kesin olarak gösterir.

← Faz ve Bloch küresi: görünmeyen ayar · Bernstein–Vazirani: gizli diziyi tek seferde bul →