Temel Kuantum Fiziği ve Kuantum Teknolojilerine Giriş · 7. Ünite: Kuantum Hesaplama ve Kuantum Bilgi
Deutsch–Jozsa Algoritması
Deutsch–Jozsa algoritması, bir kuantum bilgisayarın belirli bir problemi her deterministik klasik algoritmadan üstel olarak daha az sorguyla kesin olarak çözebildiğini gösteren ilk örnektir. Bu konuda önce tek bitlik Deutsch problemini ve devresini adım adım çözecek, ardından $n$ bitlik genellemenin tam cebirsel türetmesini yapacaksın: faz geri tepmesi ve Walsh–Hadamard girişimi $|0\rangle^{\otimes n}$ genliğini sabit fonksiyonda $\pm 1$, dengeli fonksiyonda tam $0$ yapar. Klasik deterministik algoritmanın en kötü durumda $2^{n-1}+1$ sorgu gerektirdiğini kanıtlayacak, ama olasılıksal bir klasik algoritmanın birkaç sorguyla küçük hata payıyla aynı işi yaptığını görüp avantajın sınırlarını dürüstçe değerlendireceksin. Son olarak Bernstein–Vazirani algoritmasıyla tek sorguda $n$ bitlik gizli bir diziyi bulacak, Simon algoritmasıyla da olasılıksal klasik algoritmalara karşı bile üstel bir ayrımın, Shor algoritmasının habercisi olarak, nasıl elde edildiğini kısaca öğreneceksin.
Öğrenme hedefleri
- Deutsch problemini ($f:\{0,1\}\to\{0,1\}$, $f(0) = f(1)$ mi?) tanımlar ve devrenin her adımındaki durumu yazarak tek orakl sorgusuyla kesin çözümü türetir.
- Deutsch–Jozsa devresinde son durumun $|z\rangle$ genliğinin $2^{-n}\sum_x(-1)^{f(x)+x\cdot z}$ olduğunu gösterir; $|0\rangle^{\otimes n}$ ölçüm olasılığının sabit $f$ için 1, dengeli $f$ için 0 olduğunu kanıtlar.
- Deterministik klasik algoritma için en kötü durum sorgu sayısının $2^{n-1}+1$ olduğunu gerekçelendirir; $k$ rastgele sorgulu olasılıksal algoritmanın hata olasılığını hesaplayarak kuantum avantajının kapsamını değerlendirir.
- Bernstein–Vazirani problemini ($f(x) = s\cdot x$) tek sorguyla çözer, klasik olarak neden $n$ sorgu gerektiğini bilgi kuramsal olarak açıklar.
- Simon problemini ve algoritmasının yapısını (ölçümle $y\cdot s = 0$ denklemleri, Gauss eliminasyonu) nitel olarak açıklar; olasılıksal klasik algoritmalara karşı üstel ayrımın anlamını ve Shor algoritmasıyla bağlantısını tartışır.
Konu anlatımı
Bağlam: Orakl Modeli ve Vaat Problemleri
Deutsch Problemi (n = 1) ve Devresi
Deutsch–Jozsa Genellemesi: Tam Cebirsel Türetme
Klasik Algoritmalarla Karşılaştırma: Dürüst Bir Değerlendirme
Bernstein–Vazirani Algoritması
Simon Algoritması: Üstel Ayrıma Kısa Bir Bakış
Çözümlü Örnekler
Sık Yapılan Hatalar ve Kavram Yanılgıları
Anahtar terimler
- Orakl (kara kutu)
- İçi bilinmeyen ve yalnızca çağrılabilen fonksiyon; kuantumda $U_f|x\rangle|y\rangle = |x\rangle|y\oplus f(x)\rangle$.
- Sorgu karmaşıklığı
- Bir problemi çözmek için oraklın kaç kez çağrılması gerektiği; kapı maliyetinden bağımsız ölçü.
- Vaat problemi
- Girdinin belirli bir sınıfa (ör. sabit ya da dengeli) ait olduğunun garanti edildiği problem; vaat dışı girdide cevap tanımsızdır.
- Sabit ve dengeli fonksiyon
- Sabit: tüm girişlerde aynı değer. Dengeli: girişlerin tam yarısında 0, yarısında 1.
- Deutsch–Jozsa algoritması
- $H^{\otimes(n+1)}$, $U_f$, $H^{\otimes n}$ ile tek sorguda sabit/dengeli kararı; $P(0\cdots0)$ sabitte 1, dengelide 0.
- Düşman (adversary) argümanı
- Algoritmanın sorgularına en elverişsiz cevapları veren hayali bir rakiple alt sınır kanıtlama yöntemi; Deutsch–Jozsa'da $2^{n-1}+1$ sınırını verir.
- Bernstein–Vazirani algoritması
- $f(x) = s\cdot x$ için gizli $s$'yi tek sorguda kesin bulan devre; klasik olarak $n$ sorgu gerekir.
- Simon algoritması
- $f(x) = f(x\oplus s)$ gizli XOR periyodunu $O(n)$ kuantum sorguyla bulur; klasik olarak $\Omega(2^{n/2})$ gerekir, ilk üstel orakl ayrımı.
Örnek soru
Deutsch devresi ($|0\rangle|1\rangle \to H\otimes H \to U_f \to H\otimes I$) bir kez çalıştırılıyor ve ilk kubit ölçümü 1 veriyor. $f:\{0,1\}\to\{0,1\}$ aşağıdakilerden hangisi olabilir?
- $f(x) = 0$
- $f(x) = 1$
- $f(0) = f(1)$ olan herhangi bir fonksiyon
- Ölçüm olasılıksal olduğundan hiçbir şey söylenemez
- $f(x) = 1\oplus x$
Doğru cevap: E
Çözüm
1. Son durum $\pm|f(0)\oplus f(1)\rangle|-\rangle$; ölçüm doğrudan $f(0)\oplus f(1)$'i verir.
2. Sonuç 1 ⇒ $f(0) \ne f(1)$ ⇒ $f$ dengeli: $f(x) = x$ ya da $f(x) = 1\oplus x$.
3. Seçenekler arasında dengeli olan $f(x) = 1\oplus x$.
"Olasılıksal" çeldiricisi yanlıştır: ideal devrede sonuç kesindir, çünkü $|+\rangle$ ve $|-\rangle$ dik durumlardır ve son $H$ onları $|0\rangle$ ve $|1\rangle$'e götürür.
Temel Kuantum Fiziği ve Kuantum Teknolojilerine Giriş: tüm konular