Kuantum Fourier dönüşümü: periyodu yakala

Shor algoritmasının kalbindeki kuantum Fourier dönüşümünü iki kübitle kur. Periyodik bir durumun, periyodu ele veren tepelere nasıl dönüştüğünü gör.

Fourier dönüşümü ne yapar?

Klasik Fourier dönüşümü bir sinyali frekanslarına ayırır: bir şarkıdaki notaları ya da bir ölçümdeki tekrarlanan deseni bulmanın yoludur. Kuantum Fourier dönüşümü (QFT) aynı işi genliklere yapar: tekrar eden (periyodik) bir genlik desenini, periyodu ele veren birkaç belirgin sonuca çevirir.

Shor algoritması çarpanlara ayırmayı bir periyot bulma problemine çevirir; periyodu bulmak için de QFT’yi kullanır.

İki kübitlik QFT

QFT yalnızca H kapılarından ve kontrollü faz kapılarından oluşur. İki kübitte dört adımdır: q1’e H, q0 kontrollü ve q1 hedefli bir CS (kontrollü çeyrek tur), q0’a H, en sonda da kübitlerin sırasını düzelten bir SWAP. n kübitte kapı sayısı yaklaşık n²/2’dir; klasik hızlı Fourier dönüşümünün n·2ⁿ işleminden üstel olarak azdır.

Deneme alanındaki ilk H, 00 ve 10 durumlarının eşit karışımını hazırlar: dört kutuluk bir dizide 0 ve 2 numaralı kutular dolu, yani periyot 2. QFT bunu 00 ve 10’da iki tepeye çevirir; tepeler arasındaki mesafe 4 / periyot = 2’dir.

Dikkat: QFT sihirli değnek değil

QFT, genliklerin Fourier dönüşümünü hesaplar ama sonucu doğrudan okuyamayız; yalnızca bir ölçüm alırız. Bu yüzden QFT, sonucun birkaç belirgin tepede toplandığı periyot bulma ve faz tahmini gibi problemlerde işe yarar. Bir sonraki derste QFT’nin tersini faz okumak için kullanacağız.

Kendin dene

İlk H kapısını kaldır: giriş artık yalnızca 00, yani periyot yok. QFT dört sonucu da %25 yapar; tepe kalmaz.

Tarayıcıda dene (kurulum yok)

Akılda kalsın

QFT periyodik bir genlik desenini periyodu ele veren tepelere çevirir.
H ve kontrollü faz kapılarından oluşur; n kübitte yaklaşık n²/2 kapı gerekir.
Shor algoritması periyot bulmak için QFT kullanır.
Sonuç yalnızca ölçümle okunur; QFT tepeleri belirgin olan problemlerde işe yarar.

Kendini sına

Dört kutuluk bir durumda 0 ve 2 numaralı kutular doluysa QFT sonrası tepeler nerede olur?

00 ve 01
00 ve 10
Dört sonuç da eşit

Cevabı göster

00 ve 10. Periyot 2 olduğu için tepeler 4 / 2 = 2 aralıkla, 0 ve 2 numaralı sonuçlarda, yani 00 ve 10’da çıkar.

← Grover ayrıntılı: kâhin ve difüzyon · Faz tahmini: bir kapının sırrını ölç →