Penjelasan sederhana tentang transformasi Shor / QFT sebagai paku payung

Sebagai programmer non-matematikawan / perangkat lunak, saya mencoba memahami cara kerja QFT (Quantum Fourier Transformation).

Mengikuti video YouTube ini: https://www.youtube.com/watch?v=wUwZZaI5u0c

Dan blogpost ini: https://www.scottaaronson.com/blog/?p=208

Saya punya pemahaman dasar tentang bagaimana Anda dapat menghitung / membangun periode menggunakan interferensi. Tetapi ketika mencoba menjelaskan hal ini kepada seorang kolega saya mengalami masalah. Saya menggunakan contoh-contoh berikut, N = 15, a = 7, jadi periode yang perlu saya temukan adalah r = 4.

Polanya adalah: 7, 4, 13, 1, 7, 4, 13, 1, 7, 4, 13, 1 (etc)

Jika saya membayangkan roda (seperti dalam video YouTube) atau jam (seperti blogpost) saya dapat melihat bahwa lingkaran dengan 4 titik / jam dengan 4 jam menciptakan pola yang konstruktif dan yang lainnya tidak.

Tetapi apa yang terjadi dengan lingkaran dengan 2 titik, atau jam dengan 2 jam, mereka akan mendapatkan magnitudo / pola konstruktif yang sama dengan 4? Loopnya dua kali lebih cepat, tetapi selain itu, hasilnya sama?

Bagaimana QFT mengatasi hal ini?

(Bonus: Bisakah Anda menjelaskan dalam istilah awam tanpa terlalu rumit matematika?)

Biarkan saya mencoba memberikan jawaban yang agak tidak konvensional untuk pertanyaan ini:

As a non-mathematician/software programmer I'm trying to grasp
how QFT (Quantum Fourier Transformation) works.

Misalkan kita memiliki komputer kuantum yang dapat memanipulasi qubit. The keadaan kuantum dari sebuah komputer kuantum seperti tepat menggambarkan keadaan saat ini komputer kuantum ini. Hal ini cukup terkenal bahwa kita dapat mengekspresikan keadaan kuantum ini sebagai vektor dari bilangan kompleks. Mari kita coba memvisualisasikan bilangan kompleks ini dengan cara yang ringkas.$n$$2^n$

Untuk itu, perhatikan garis horizontal, di mana poin digambarkan. Mereka dilabeli sesuai dengan posisi masing-masing pada baris, yaitu, titik pertama diberi label dengan , dan titik terakhir diberi label oleh . Kita bisa melihat ini pada gambar di bawah ini.$2^n$$|0\rangle$$|2^n-1\rangle$

Sekarang, coba bayangkan bahwa pada setiap titik, yang digambarkan di atas, garis ini menusuk lingkaran jari-jari menembus tengah. Artinya, ada lingkaran yang ditempatkan tepat pada titik-titik yang digambarkan di atas, dan garis menghubungkan bagian tengah semua lingkaran ini. Saya telah mencoba menggambarkan ini pada gambar di bawah, tetapi keterampilan menggambar 3D saya tidak benar-benar top-notch, jadi Anda harus memaafkan saya untuk itu.$1$$2^n$

Yang menyenangkan dari gambar ini di atas adalah bahwa ia dapat secara unik mewakili keadaan komputer kuantum -qubit dengan menandai tepat satu titik di semua lingkaran. Lebih eksplisit, keadaan kuantum apa pun dari komputer kuantum -qubit dapat digambarkan dalam gambar di atas dengan menggambar satu salib ( ) di semua lingkaran. Sebaliknya, gambar seperti itu mewakili keadaan kuantum, sepanjang kuadrat jarak persilangan ke titik pusat dijumlahkan dengan . Dengan kata lain, jika kita menghitung semua jarak dari titik-titik yang ditandai ke titik tengah, lalu kuadratkan jarak-jarak ini, dan kemudian menambahkan semuanya, kita mensyaratkan bahwa hasilnya sama dengan . Contoh negara ditunjukkan di bawah ini:$n$$n$$\times$$1$$1$

Sepanjang pelaksanaan suatu program, keadaan komputer kuantum terus berubah, dan dengan demikian, demikian pula representasi visual. Oleh karena itu, sepanjang pelaksanaan program kuantum, titik-titik yang ditandai ( s), terus bergerak, dalam batas-batas lingkaran masing-masing.$\times$

$3$$3$ Quantum Fourier Transform -qubit dijalankan.

$3$$|0\rangle$$1$$|0\rangle$

Pertanyaannya sekarang adalah apa yang terjadi pada keadaan kuantum ketika kita menerapkan Quantum Fourier Transform. Ternyata, ketika Quantum Fourier Transform diterapkan ke keadaan yang ditunjukkan di atas, keadaan yang dihasilkan dari sistem kuantum menjadi:

$1/\sqrt{8}$

$|1\rangle$

Sekarang, jika kita menerapkan Quantum Fourier Transform, status yang dihasilkan menjadi:

Kita dapat melihat bahwa keadaan yang dihasilkan menjadi semacam bentuk heliks. Selain itu, amati bahwa jika kita menambahkan satu lingkaran ekstra ke kanan negara paling kanan, maka heliks akan menyelesaikan satu revolusi dengan tepat.

$|j\rangle$$j$$|3\rangle$

$3$

$j$$|j\rangle$ , yang merupakan arah sebaliknya dari pemetaan kita pikirkan sebelumnya.

Ide inilah yang merupakan komponen penting dalam algortihm Shor. Gagasan utamanya adalah mengambil urutan angka yang Anda gambarkan:

7, 4, 13, 1, 7, 4, 13, 1, 7, 4, 13, 1 (etc)

$|4\rangle$ , yaitu, periode urutan ini.

CATATAN 1: Ada banyak detail yang saya lewatkan di paragraf terakhir. Namun, jawaban ini sudah mengandung banyak informasi, yang menurut saya perlu dimasukkan sebelum orang dapat mencoba menambahkan rincian ini ke gambar. Jika ada yang ingin saya menambahkan detail ini, saya mungkin akan melakukannya di tahap selanjutnya.

$2^n$

Dalam contoh Anda, pola dibuat oleh fungsi atau rangkaian perkalian modular f (x) = kapak (mod N) Sirkuit dan pola kuantum ini juga diberikan dalam manual Q IBM dari Pengalaman Q IBM .

Jadi dalam satu lingkaran dengan input awal x = 1

x = 1 f (x) = 7 * 1 (mod 15) = 7

x = 7 f (x) = 7 * 7 (mod 15) = 4

x = 4 => 13

x = 13 => 1

Pola 1 7 4 13 1 diulang setiap 4 kali. Jadi rangkaian diperbaiki untuk a dan mod 15 yang diberikan dan selalu mengembalikan r = 4. Jika Anda ingin r = 2, Anda memerlukan fungsi pengali lain