Bernstein–Vazirani: gizli diziyi tek seferde bul

Bir fonksiyonun içine saklanmış bit dizisini, klasik olarak gereken n sorgu yerine tek sorguda okuyan algoritma. Kâhinin nasıl kurulduğunu adım adım gör.

Problem

Fonksiyon f(x) = s·x (mod 2) biçimindedir: gizli bir s bit dizisiyle girişin bit bit çarpımlarının toplamının teki. Amaç s’yi bulmak. Klasik olarak her seferinde tek bir biti 1 olan girişler sorarak s’nin bitlerini teker teker öğrenirsin; n bit için n sorgu gerekir.

Kâhini kurmak

f(x) = s·x, s’nin 1 olan her biti için o giriş kübitinden yardımcı kübite bir CNOT çekilerek kurulur. Deneme alanında s = 101: q0 ve q2’den q3’e birer CNOT var, q1’den yok.

Devre Deutsch–Jozsa ile aynı iskelete sahiptir: girişlere H, yardımcıya X ve H, kâhin, sonra yine H. Faz geri tepmesi girişlere (−1)^(s·x) fazını yazar ve son H kapıları bu faz desenini doğrudan s’ye çevirir.

Ne öğrendik?

Tek sorguda, kesin olarak, n bitin hepsi. Hızlanma üstel değil doğrusaldır (n’ye karşı 1), ama kuantum paralelliğinin ve girişimin birlikte nasıl çalıştığını gösteren en temiz örneklerden biridir. Gerçek donanımda ilk denenen algoritmalardandır.

Kendin dene

q2’den q3’e giden CNOT’u kaldır: gizli dizi 001 olur ve girişler (q2 q1 q0) tek seferde 001 okur; sonuç 1001.

Tarayıcıda dene (kurulum yok)

Akılda kalsın

f(x) = s·x (mod 2) kâhini, s’nin 1 olan her biti için bir CNOT ile kurulur.
Faz geri tepmesi ve son H kapıları, faz desenini doğrudan s’ye çevirir.
Klasik olarak n sorgu, kuantumda tek sorgu gerekir.

Kendini sına

Gizli dizi s = 110 ise kâhinde hangi kübitlerden yardımcı kübite CNOT çekilir?

q0 ve q1
q1 ve q2
Yalnızca q0

Cevabı göster

q1 ve q2. s = 110 dizisinde q2 ve q1 bitleri 1, q0 biti 0’dır; bu yüzden q1 ve q2’den CNOT çekilir.

← Deutsch–Jozsa: tek soruda kesin cevap · Grover ayrıntılı: kâhin ve difüzyon →