Algoritma Shor

Untuk modul Qiskit in Classrooms ini, pelajar perlu mempunyai persekitaran Python yang berfungsi dengan pakej berikut dipasang:

• qiskit v2.1.0 atau lebih baharu
• qiskit-ibm-runtime v0.40.1 atau lebih baharu
• qiskit-aer v0.17.0 atau lebih baharu
• qiskit.visualization
• numpy
• pylatexenc

Untuk menyediakan dan memasang pakej di atas, lihat panduan Pasang Qiskit. Untuk menjalankan kerja pada komputer kuantum sebenar, pelajar perlu membuat akaun dengan IBM Quantum® dengan mengikuti langkah-langkah dalam panduan Sediakan akaun IBM Cloud anda.

Modul ini telah diuji dan menggunakan tiga saat masa QPU. Ini adalah anggaran sahaja. Penggunaan sebenar anda mungkin berbeza.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Pengenalan

Pada awal 1990-an, terdapat keseronokan yang semakin meningkat tentang potensi komputer kuantum untuk menyelesaikan masalah yang sukar bagi komputer klasik. Beberapa saintis komputer berbakat telah mereka bentuk algoritma yang menunjukkan kekuatan pengkomputeran kuantum untuk beberapa masalah khusus yang direka khas, tetapi tiada seorang pun yang menemui satu "killer app" pengkomputeran kuantum yang pasti akan merevolusikan bidang ini. Itu berlaku sehingga 1994, apabila Peter Shor menghasilkan apa yang kini dikenali sebagai algoritma Shor untuk memfaktorkan nombor besar.

Sudah lama diketahui pada masa itu bahawa mencari faktor perdana nombor besar adalah sangat sukar bagi komputer klasik. Malah, protokol keselamatan internet bergantung pada kesukaran ini. Shor menemui cara untuk mencari faktor-faktor ini dengan lebih cekap secara eksponen dengan memindahkan beberapa langkah yang lebih mencabar kepada komputer kuantum teoritikal pada masa depan.

Dalam modul ini, kita akan meneroka algoritma Shor. Pertama, kita akan memberikan sedikit konteks lebih lanjut tentang algoritma ini, memformalkan masalah yang diselesaikannya dan menerangkan relevansinya kepada keselamatan siber. Seterusnya, kita akan memberikan pengenalan tentang matematik modular dan cara menggunakannya pada masalah pemfaktoran, menunjukkan bagaimana pemfaktoran boleh diturunkan kepada masalah lain yang dipanggil "pencarian peringkat." Kita akan menunjukkan bagaimana Jelmaan Fourier Kuantum dan Anggaran Fasa Kuantum yang kita pelajari dalam modul sebelumnya memainkan peranan, dan cara menggunakannya untuk menyelesaikan masalah pencarian peringkat.

Akhir sekali, kita akan menjalankan algoritma Shor pada komputer kuantum sebenar! Ingatlah, bagaimanapun, algoritma ini hanya akan benar-benar berguna apabila kita mempunyai komputer kuantum yang besar dan tahan kesalahan, yang masih beberapa tahun lagi. Jadi, kita hanya akan memfaktorkan nombor kecil untuk menunjukkan cara algoritma ini berfungsi.

Masalah pemfaktoran

Matlamat masalah pemfaktoran adalah untuk mencari faktor perdana suatu nombor $N$. Untuk sesetengah nombor $N$, ini agak mudah. Contohnya, jika $N$ adalah genap, salah satu faktor perdananya ialah 2. Jika $N$ adalah kuasa perdana, bermaksud $N=p^k$ untuk suatu nombor perdana $p$, adalah juga agak mudah untuk mencari $p$: kita hanya menganggarkan punca $k^{\text{th}}$ bagi $N$ dan mencari perdana berdekatan yang mungkin $p$.

Walau bagaimanapun, komputer klasik menghadapi kesukaran apabila $N$ adalah ganjil dan bukan kuasa perdana. Inilah kes yang ditangani algoritma Shor. Algoritma ini mencari dua faktor $p$ dan $q$ supaya $N=pq$. Ia boleh digunakan secara rekursif sehingga semua faktor adalah perdana. Dalam bahagian seterusnya kita akan melihat bagaimana masalah ini ditangani.

Relevansi kepada keselamatan siber

Banyak skim kriptografi telah dibina berdasarkan hakikat bahawa memfaktorkan nombor besar adalah sukar, termasuk satu yang biasa digunakan hari ini, dipanggil RSA. Dalam RSA, kunci awam dicipta dengan mendarabkan dua nombor perdana besar bersama untuk mendapatkan $N = p\cdot q$. Kemudian, sesiapa sahaja boleh menggunakan kunci awam ini untuk menyulitkan data. Tetapi hanya seseorang yang mempunyai kunci peribadi, $p$ dan $q$, boleh menyahsulit data tersebut.

Jika $N$ mudah difaktorkan, maka sesiapa pun boleh menentukan apakah $p$ dan $q$ dan memecahkan penyulitan. Tetapi ia tidak begitu. Ini adalah masalah yang terkenal sukar. Malah, faktor perdana bagi nombor yang dipanggil RSA1024, yang mempunyai 1024 digit binari dan 309 digit perpuluhan, masih belum ditemui, walaupun hadiah $100,000 ditawarkan untuk pemfaktorannya sejak 1991.

Penyelesaian Shor

Pada 1994, Peter Shor menyedari bahawa komputer kuantum boleh memfaktorkan nombor besar dengan lebih cekap secara eksponen berbanding komputer klasik. Wawasannya bergantung pada hubungan antara masalah pemfaktoran ini dan aritmetik modular. Kita akan melalui pengenalan ringkas tentang aritmetik modular, kemudian kita akan melihat bagaimana kita boleh menggunakannya untuk memfaktorkan $N$.

Aritmetik modular

Aritmetik modular adalah sistem pengiraan yang bersifat kitaran, bermaksud walaupun pengiraan bermula seperti biasa, dengan integer 0, 1, 2, dan seterusnya, pada suatu ketika, selepas tempoh $N$, pengiraan bermula semula. Mari lihat cara ini berfungsi dengan contoh. Katakan tempoh kita adalah 5. Kemudian, semasa kita mengira, di mana kita biasanya mencapai 5, kita sebaliknya memulakan semula pada 0:

$0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, ...$

Ini kerana dalam dunia "modulo-5", 5 bersamaan dengan 0. Kita katakan $5\bmod 5 \ = 0$. Malah, semua gandaan 5 akan bersamaan dengan $0\bmod 5$.

Semak pemahaman anda

Baca soalan di bawah, fikirkan jawapan anda, kemudian klik segitiga untuk mendedahkan penyelesaiannya.

Gunakan aritmetik modular untuk menyelesaikan masalah berikut:

Kamu bertolak dalam perjalanan kereta api transcontinental yang panjang pada pukul 8 pagi. Perjalanan kereta api itu 60 jam lamanya. Pukul berapakah ketika kamu tiba?

Jawapan:

Tempohnya ialah 24, kerana ada 24 jam dalam sehari. Jadi, masalah ini boleh ditulis dalam aritmetik modular sebagai:

$(8+60)\text{mod}(24) = 20$

Jadi, kamu akan tiba di destinasi pada pukul 20:00, atau pukul 8 malam.

$\mathbb{Z}_N$ dan $\mathbb{Z}_N^*$

Selalunya berguna untuk memperkenalkan dua set, $\mathbb{Z}_N$ dan $\mathbb{Z}_N^*$. $\mathbb{Z}_N$ hanyalah set nombor yang wujud dalam dunia "modulo-$N$". Contohnya, apabila kita mengira modulo-5, setnya ialah $\mathbb{Z}_5=\{0,1,2,3,4\}$. Contoh lain: $\mathbb{Z}_{15} = \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$. Kita boleh melakukan penambahan dan pendaraban (modulo $N$) pada elemen dalam $\mathbb{Z}_N$, dan hasil setiap operasi ini juga adalah elemen dalam $\mathbb{Z}_N$, menjadikan $\mathbb{Z}_N$ objek matematik yang dipanggil gelanggang.

Terdapat subset khas $\mathbb{Z}_N$ yang amat menarik perhatian kita untuk algoritma Shor. Iaitu subset nombor dalam $\mathbb{Z}_N$ supaya pembahagi sepunya terbesar antara setiap elemen dan $N$ ialah 1, jadi setiap elemen adalah "ko-perdana" dengan $N$. Jika kita mengambil set nombor ini bersama operasi pendaraban modular, maka ini membentuk objek matematik lain, yang dipanggil kumpulan. Kita menamakan kumpulan ini $\mathbb{Z}_N^*$. Rupanya dengan $\mathbb{Z}_N^*$ (dan kumpulan terhingga secara umum), jika kita memilih mana-mana elemen $a \in \mathbb{Z}_N^*$, dan berulang kali mendarabkan $a$ dengan dirinya sendiri, kita akan sentiasa akhirnya mendapatkan nombor $1$. Bilangan minimum kali seseorang perlu mendarabkan $a$ dengan dirinya sendiri untuk mendapatkan $1$ dipanggil peringkat bagi $a$. Fakta ini akan sangat penting dalam perbincangan kita tentang cara memfaktorkan nombor di bawah.

Semak pemahaman anda

Baca soalan di bawah, fikirkan jawapan anda, kemudian klik segitiga untuk mendedahkan penyelesaiannya.

Apakah $\mathbb{Z}_{15}^*$?

Jawapan:

$\mathbb{Z}_{15}^* = \{1,2,4,7,8,11,13,14\}$

Kita mengecualikan nombor berikut:

$$\begin{aligned} 3: GCD(3,15)=3 \\ 5: GCD(5,15)=5 \\ 6: GCD(6,15)=3 \\ 9: GCD(9,15)=3 \\ 10: GCD(10,15)=5 \\ 12: GCD(12,15)=3 \\ \end{aligned}$$

Apakah peringkat bagi setiap elemen dalam $\mathbb{Z}_{15}^*$?

Jawapan:

Peringkat $r$ adalah nombor terendah supaya $a^r\text{mod}(15)=1$ bagi setiap elemen $a$.

$$\begin{aligned} 1^1\text{mod}(15) = 1, r=1 \\ 2^4\text{mod}(15) = 1, r=4 \\ 4^2\text{mod}(15) = 1, r=2 \\ 7^4\text{mod}(15) = 1, r=4 \\ 8^4\text{mod}(15) = 1, r=4 \\ 11^2\text{mod}(15) = 1, r=2 \\ 13^4\text{mod}(15) = 1, r=4 \\ 14^2\text{mod}(15) = 1, r=2 \\ \end{aligned}$$

Perhatikan bahawa, walaupun kita dapat mencari peringkat nombor dalam $\mathbb{Z}_{15}^*$, ini BUKAN tugas yang mudah secara umum, untuk $N$ yang lebih besar. Inilah inti masalah pemfaktoran dan sebab kita memerlukan komputer kuantum. Kita akan melihat mengapa semasa kita mengerjakan baki notebook ini.

Gunakan aritmetik modular pada masalah pemfaktoran

Kunci untuk mencari faktor $p$ dan $q$ supaya $N=pq$ bergantung pada mencari suatu integer lain $x$ supaya

$x^2 \equiv 1 \bmod N$ dan $x \not\equiv \pm 1 \bmod N.$

Bagaimana mencari $x$ membantu kita mencari faktor $p$ dan $q$? Mari lalui hujah itu sekarang. Sejak $x^2 \equiv 1 \bmod N$, bermaksud $x^2 - 1 \equiv 0 \bmod N$. Dalam erti kata lain, $x^2 - 1$ adalah gandaan $N$. Jadi, untuk suatu integer $l$,

$x^2 - 1 = l N$

Kita boleh memfaktorkan $x^2 - 1$ untuk mendapatkan:

$(x+1)(x-1) = l N$

Daripada andaian awal kita, kita tahu bahawa $x \not\equiv \pm 1 \bmod N$, jadi $N$ tidak membahagi secara sekata ke dalam $x+1$ atau $x-1$. Jadi, dua faktor $N$, iaitu $p$ dan $q$, masing-masing mesti membahagi ke dalam $x-1$ dan $x+1$. Sama ada $p$ adalah faktor $x-1$ dan $q$ adalah faktor $x+1$, atau sebaliknya. Oleh itu, jika kita mengira pembahagi sepunya terbesar (GCD) antara $N$ dan kedua-dua $x-1$ dan $x+1$, itu akan memberi kita faktor $p$ dan $q$. Mengira GCD antara dua nombor adalah tugas yang mudah secara klasik yang boleh dilakukan, contohnya, menggunakan algoritma Euclid.

Semak pemahaman anda

Baca soalan di bawah, fikirkan jawapan anda, kemudian klik segitiga untuk mendedahkan penyelesaiannya.

Mungkin sukar untuk memahami setiap langkah logik di atas, jadi cuba lakukan dengan contoh. Gunakan $N=15$ dan $x=11$. Pertama, sahkan bahawa $x^2 \equiv 1 \text{mod}(N)$ dan $x \not\equiv \pm 1 \bmod N$. Kemudian teruskan untuk mengesahkan setiap langkah. Akhir sekali, kira $\text{GCD}(11\pm1,15)$ dan sahkan bahawa ia adalah faktor-faktor $15$.

Jawapan:

$11^2 = 121$, iaitu $15*8 + 1$, jadi $11^2\bmod 15 = 1$. $\checkmark$

$11 - 1 = 10$, yang tidak bersamaan dengan $0\bmod 15$. $\checkmark$

$11 + 1 = 12$, yang tidak bersamaan dengan $0\bmod 15$. $\checkmark$

Sekarang, kita tahu bahawa $(x+1)(x-1) = l N$ untuk suatu integer $l$. Ini disahkan apabila kita memasukkan $x$ dan $N$: $(12)(10) = l 15$ apabila $l = 8$. $\checkmark$

Sekarang, kita perlu mengira $\text{GCD}(12,15)$ dan $\text{GCD}(10,15)$.

$$\begin{aligned} \text{GCD}(12,15) = 3 \\ \text{GCD}(10,15) = 5 \end{aligned}$$

Jadi, kita telah menemui faktor-faktor $15$!

Algoritma

Kini setelah kita melihat bagaimana mencari suatu integer $x$ supaya $x^2 \equiv 1\bmod N$ membantu kita memfaktorkan $N$, kita boleh melalui algoritma Shor. Ia pada asasnya merupakan cara mencari $x$:

1. Pilih integer rawak Pilih integer rawak $a$ supaya $1 < a < N$.

• Kira $\text{GCD}(a, N)$ secara klasik.
  • Jika $\text{GCD}(a, N) > 1$, kamu telah menemui faktor. Berhenti.
  • Jika tidak, teruskan.

2. Cari peringkat $r$ bagi $a$ modulo $N$ Cari integer positif terkecil $r$ yang memenuhi $a^r \equiv 1 \pmod N$.

3. Semak sama ada peringkatnya genap

• Jika $r$ adalah ganjil, kembali ke langkah 1 dan pilih $a$ baru.
• Jika $r$ adalah genap, teruskan ke langkah 4.

4. Kira $x = a^{r/2} \bmod N$

• Semak bahawa $x \not\equiv 1 \pmod N$ dan $x \not\equiv -1 \pmod N$.
  • Jika $x \equiv \pm 1 \pmod N$, kembali ke langkah 1 dan pilih $a$ baru.
• Jika tidak, kira gcd untuk mengekstrak faktor:

$$p = \text{GCD}(x-1, N), \quad q = \text{GCD}(x+1, N)$$

Ini akan menjadi faktor bukan remeh bagi $N$.

5. Faktor secara rekursif jika perlu

• Jika $p$ dan/atau $q$ bukan perdana, gunakan algoritma ini secara rekursif untuk memfaktorkannya sepenuhnya.
• Apabila semua faktor adalah perdana, pemfaktoran selesai.

Berdasarkan prosedur ini, mungkin tidak jelas mengapa komputer kuantum diperlukan untuk menyelesaikan tugas ini. Ia perlu kerana langkah 2, mencari peringkat $a$ modulo $N$, adalah masalah yang sangat sukar secara klasik. Kerumitannya berskala secara eksponen dalam nombor $N$. Tetapi dengan komputer kuantum, kita hanya perlu menggunakan Anggaran Fasa Kuantum untuk menyelesaikannya. Langkah 4, mencari GCD dua integer, sebenarnya adalah sesuatu yang agak mudah dilakukan secara klasik. Jadi, satu-satunya langkah yang benar-benar memerlukan kuasa komputer kuantum adalah langkah pencarian peringkat. Kita katakan masalah pemfaktoran "diturunkan" kepada masalah pencarian peringkat.

Bahagian yang sukar: pencarian peringkat

Sekarang, kita akan melalui cara kita boleh menggunakan komputer kuantum dalam pencarian peringkat. Pertama, mari kita jelaskan apa yang kita maksudkan dengan "peringkat." Sudah tentu, saya sudah memberitahu anda apa maksud peringkat secara matematik: ia adalah integer bukan sifar pertama $r$ supaya $a^r = 1 \pmod N.$ Tetapi mari lihat sama ada kita boleh mendapatkan sedikit lebih intuisi untuk konsep ini.

Untuk $N$ yang cukup kecil, kita boleh menentukan peringkat hanya dengan mengira setiap kuasa $a$, mengambil modulus $N$ bagi nombor itu, kemudian berhenti apabila kita menemui kuasa $r$ yang memenuhi $a^r = 1 \text{mod}(N)$. Itulah yang kita lakukan dengan contoh kita, $N=15$, di atas. Mari lihat beberapa graf kuasa modular ini untuk beberapa nilai sampel $a$ dan $N$:

Perasan sesuatu? Ini adalah fungsi berkala! Dan peringkat $r$ adalah sama dengan tempohnya! Jadi, pencarian peringkat bersamaan dengan pencarian tempoh.

Komputer kuantum sangat sesuai untuk mencari tempoh fungsi. Untuk ini, kita boleh menggunakan subrutin algoritma yang dipanggil Anggaran Fasa Kuantum. Kita membincangkan QPE dan hubungannya dengan Jelmaan Fourier Kuantum dalam modul sebelumnya. Untuk penyegaran terperinci, pergi ke modul QFT atau pelajaran John Watrous tentang Anggaran Fasa Kuantum dalam kursus Algoritma Kuantumnya. Kita akan melalui intipati prosedur sekarang:

Dalam Anggaran Fasa Kuantum (QPE), kita bermula dengan unitar $U$ dan eigenstate unitar tersebut $|\psi\rangle$. Kemudian, kita menggunakan QPE untuk menganggarkan nilai eigen yang bersesuaian, yang, kerana pengoperasinya adalah unitari, akan berbentuk $e^{2\pi i \theta}$. Jadi, mencari nilai eigen bersamaan dengan mencari nilai $\theta$ dalam fungsi berkala. Circuit kelihatan seperti ini:

di mana bilangan Qubit kawalan (Qubit $m$ teratas dalam rajah di atas) menentukan ketepatan anggaran.

Dalam algoritma Shor, kita menggunakan QPE pada pengoperasi unitari $M_a$:

$M_a|y\rangle \equiv |ay \mod N \rangle .$

Di sini, $|y\rangle$ merujuk kepada keadaan asas komputasi bagi daftar berbilang Qubit, di mana nilai binari Qubit sepadan dengan integer $y$. Contohnya, jika $N=15$ dan $y = 2$, maka $|y\rangle$ diwakili oleh keadaan asas empat Qubit $|0010\rangle$, kerana empat Qubit diperlukan untuk mengekodkan nombor sehingga 15. (Jika konsep ini tidak dikenali, lihat modul Qiskit in classrooms pengantar untuk penyegaran tentang pengekodan binari keadaan kuantum.)

Sekarang, kita perlu mencari eigenstate bagi unitari ini. Jika kita bermula dalam keadaan $|1\rangle$, kita dapat melihat bahawa setiap penggunaan berturutan $U$ akan mendarabkan keadaan daftar kita dengan $a \pmod N$, dan selepas $r$ penggunaan kita akan tiba semula pada keadaan $|1\rangle$. Contohnya dengan $a = 3$ dan $N = 35$:

$$\begin{aligned} M_3|1\rangle &= |3\rangle & \\ M_3^2|1\rangle &= |9\rangle \\ M_3^3|1\rangle &= |27\rangle \\ & \vdots \\ M_3^{(r-1)}|1\rangle &= |12\rangle \\ M_3^r|1\rangle &= |1\rangle \end{aligned}$$

Jadi superposisi keadaan dalam kitaran ini ($|\psi_j\rangle$) dalam bentuk:

$|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$

semuanya adalah eigenstate bagi $M_a$. (Terdapat lebih banyak eigenstate daripada yang di atas sahaja. Tetapi kita hanya mengambil berat tentang yang berbentuk di atas.)

Semak pemahaman anda

Baca soalan di bawah, fikirkan jawapan anda, kemudian klik segitiga untuk mendedahkan penyelesaiannya.

Cari eigenstate bagi unitari yang sepadan dengan $a=2$ dan $N = 15$.

Jawapan:

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2^2|1\rangle &= |4\rangle \\ M_2^3|1\rangle &= |8\rangle \\ M_2^4|1\rangle &= |1\rangle \\ \end{aligned}$$

Jadi, peringkat $r=4$. Eigenstate yang kita minati akan menjadi superposisi saksama semua keadaan yang dilalui di atas, dengan pelbagai fasa:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{1}{4}}|2\rangle+e^{2 \pi i \frac{2}{4}}|4\rangle+e^{2 \pi i \frac{3}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{2}{4}}|2\rangle+e^{2 \pi i \frac{4}{4}}|4\rangle+e^{2 \pi i \frac{6}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{3}{4}}|2\rangle+e^{2 \pi i \frac{6}{4}}|4\rangle+e^{2 \pi i \frac{9}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

Katakan kita dapat memulakan keadaan Qubit kita ke dalam salah satu eigenstate ini (spoiler — kita tidak boleh. Atau, sekurang-kurangnya tidak dengan mudah. Kita akan menerangkan mengapa dan apa yang boleh kita lakukan sebagai gantinya tidak lama lagi). Kemudian kita boleh menggunakan QPE untuk menganggarkan nilai eigen yang sepadan, $\omega_j = e^{2 \pi i \theta_j}$ di mana $\theta_j = \frac{j}{r}$. Kemudian, kita akan dapat menentukan peringkat $r$ dengan persamaan mudah:

$r = \frac{j}{\theta_j}.$

Tetapi ingat, saya berkata bahawa QPE menganggar $\theta_j$ — ia tidak memberikan nilai tepat. Kita perlu anggaran yang cukup baik untuk membezakan antara $r$ dan $r+1$. Lebih banyak Qubit kawalan $m$ yang kita miliki, lebih baik anggarannya. Dalam soalan di akhir pelajaran, anda akan diminta untuk menentukan $m$ minimum yang diperlukan untuk memfaktorkan nombor $N$.

Sekarang, kita perlu menyelesaikan satu masalah. Semua penjelasan di atas tentang cara mencari $r$ bermula dengan menyediakan eigenstate $|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$. Tetapi kita tidak tahu cara melakukannya tanpa sudah mengetahui apa itu $r$. Logiknya bersifat bulat. Kita memerlukan cara untuk menganggar nilai eigen tanpa memulakan eigenstate.

Daripada bermula dengan eigenstate $M_a$, kita boleh menyediakan keadaan awal ke dalam keadaan $n$-Qubit yang sepadan dengan $|1\rangle$ dalam binari (iaitu, $|000...01\rangle$). Walaupun keadaan ini sendiri jelas bukan eigenstate $M_a$, ia adalah superposisi ke atas semua eigenstate $|\psi_k\rangle$:

$|1\rangle = \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle}$

Semak pemahaman anda

Baca soalan di bawah, fikirkan jawapan anda, kemudian klik segitiga untuk mendedahkan penyelesaiannya.

Sahkan bahawa $|1\rangle$ bersamaan dengan superposisi ke atas eigenstate yang anda temui untuk $N=15$ dan $a=2$ dalam soalan semakan sebelumnya.

Jawapan:

Empat eigenstate itu ialah:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

Jadi,

$$\begin{aligned} \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle} &= \frac{1}{2}(|\psi_0\rangle + |\psi_1\rangle + |\psi_2\rangle + |\psi_3\rangle ) \\ &= \frac{1}{4}(|1\rangle+|2\rangle+|4\rangle+|8\rangle+|1\rangle+i|2\rangle-|4\rangle-i|8\rangle+|1\rangle-|2\rangle+|4\rangle-|8\rangle + |1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ &= \frac{1}{4}(4|1\rangle) = |1\rangle \end{aligned}$$

Bagaimana ini membolehkan kita mencari peringkat $r$? Oleh kerana keadaan permulaan adalah superposisi ke atas semua eigenstate dalam bentuk yang disenaraikan di atas, maka algoritma QPE secara serentak menganggar setiap $\theta_k$ yang sepadan dengan eigenstate ini. Jadi, pengukuran $m$ Qubit kawalan pada akhirnya akan menghasilkan anggaran nilai $k/r$ di mana $k \in \{0,1,2,...,r-1\}$ adalah salah satu nilai eigen yang dipilih secara rawak. Jika kita mengulangi Circuit ini beberapa kali dan mendapat beberapa sampel dengan nilai $k$ yang berbeza, kita akan cepat dapat menyimpulkan $r$.

Laksanakan dalam Qiskit

Seperti yang kita sebut tadi, perkakasan kita belum mampu memfaktorkan nombor besar seperti RSA1024. Kita hanya akan memfaktorkan nombor kecil untuk menunjukkan cara algoritma ini berfungsi. Untuk demo ini, kita akan menggunakan versi ringkas kod yang dibentangkan dalam tutorial algoritma Shor. Jika mahu maklumat lanjut, sila lawati tutorial tersebut.

Kita akan menjalankan algoritma menggunakan rangka kerja piawai kita untuk menyelesaikan masalah kuantum, yang dipanggil rangka kerja corak Qiskit. Ini terdiri daripada empat langkah:

1. Memetakan masalah kepada Circuit kuantum
2. Mengoptimumkan Circuit untuk dijalankan pada perkakasan kuantum
3. Melaksanakan Circuit pada komputer kuantum
4. Memproses semula pengukuran

1. Peta

Jom kita faktorkan $N=15$, dengan memilih $a=2$ sebagai integer ko-prima kita.

Pertama, kita perlu membina Circuit yang akan melaksanakan uniter pendaraban modular, $M_a$. Ini sebenarnya bahagian paling rumit dalam keseluruhan pelaksanaan, dan boleh menjadi sangat mahal dari segi pengiraan bergantung kepada cara ia dilakukan. Untuk ini, kita akan sedikit 'menipu': Kita tahu bahawa kita bermula dalam keadaan $|1\rangle$, dan daripada soalan semak terdahulu,

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2|2\rangle &= |4\rangle \\ M_2|4\rangle &= |8\rangle \\ M_2|8\rangle &= |1\rangle \\ \end{aligned}$$

Jadi, kita akan membina satu uniter yang melakukan operasi betul pada empat keadaan ini, tetapi membiarkan semua keadaan lain tidak berubah. Ini dianggap 'menipu' kerana kita menggunakan pengetahuan kita tentang tertib $2\bmod 15$ untuk memudahkan uniter tersebut. Jika kita benar-benar cuba memfaktorkan nombor yang faktornya tidak diketahui, kita tidak boleh berbuat demikian.

Uji kefahaman anda

Baca soalan di bawah, fikirkan jawapan anda, kemudian klik segitiga untuk mendedahkan penyelesaian.

Dengan pengetahuan anda tentang cara operator $M_2$ mengubah keadaan di atas, bina operator tersebut daripada siri gate SWAP, yang menukar keadaan dua Qubit. (Petunjuk: menulis setiap keadaan $|i\rangle$ dalam binari akan membantu.)

Jawapan:

Jom kita tulis semula tindakan $M_2$ pada keadaan dalam binari:

$$\begin{aligned} M_2|0001\rangle &= |0010\rangle \\ M_2|0010\rangle &= |0100\rangle \\ M_2|0100\rangle &= |1000\rangle \\ M_2|1000\rangle &= |0001\rangle \\ \end{aligned}$$

Setiap tindakan ini boleh dicapai dengan SWAP mudah. $M_2|0001\rangle$ dicapai dengan menukar keadaan Qubit $0$ dan $1$. $M_2|0010\rangle$ dicapai dengan menukar keadaan Qubit $1$ dan $2$. Dan seterusnya. Jadi, kita boleh menguraikan matriks $M_2$ kepada siri gate SWAP berikut:

$$M_2 = SWAP(0,1)SWAP(1,2)SWAP(2,3)$$

Ingat bahawa operator bertindak dari kanan ke kiri, jom kita semak bahawa ini mempunyai kesan yang kita inginkan pada setiap keadaan:

$$\begin{aligned} M_2|0001\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0001\rangle \\ &= SWAP(0,1)SWAP(1,2)|0001\rangle \\ &= SWAP(0,1)|0001\rangle \\ &=|0010\rangle \checkmark \\ M_2|0010\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0010\rangle \\ &= SWAP(0,1)SWAP(1,2)|0010\rangle \\ &= SWAP(0,1)|0100\rangle \\ &=|0100\rangle \checkmark \\ M_2|0100\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0100\rangle \\ &= SWAP(0,1)SWAP(1,2)|1000\rangle \\ &= SWAP(0,1)|1000\rangle \\ &=|1000\rangle \checkmark \\ M_2|1000\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|1000\rangle \\ &= SWAP(0,1)SWAP(1,2)|0100\rangle \\ &= SWAP(0,1)|0010\rangle \\ &=|0001\rangle \checkmark \\ \end{aligned}$$

Kini kita boleh mengekodkan Circuit yang bersamaan dengan operator ini dalam Qiskit.

Pertama, kita import pakej yang diperlukan:

# Import necessary packages

import numpy as np
from fractions import Fraction
from math import floor, gcd, log

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import QFTGate
from qiskit.transpiler import generate_preset_pass_manager
from qiskit.visualization import plot_histogram

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

Kemudian, kita buat operator $M_2$:

def M2mod15():
    """
    M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M2 operator
M2 = M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M2, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

Algoritma QPE menggunakan gate controlled-$U$. Jadi, sekarang kita sudah ada Circuit $M_2$, kita perlu menjadikannya Circuit controlled-$M_2$:

def controlled_M2mod15():
    """
    Controlled M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M2 operator
controlled_M2 = controlled_M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M2, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Kini kita ada gate controlled-$U$. Tetapi untuk menjalankan algoritma Quantum Phase Estimation, kita memerlukan controlled-$U^2$, controlled-$U^4$, sehingga controlled-$U^{2^{m-1}}$, di mana $m$ ialah bilangan Qubit yang digunakan untuk menganggar fasa. Lebih banyak Qubit, lebih tepat penganggaran fasa. Kita akan menggunakan $m=8$ Qubit kawalan untuk prosedur penganggaran fasa kita. Jadi, kita perlukan:

$$M_{a^{2^k}}|y\rangle \equiv |a^{2^k} y \bmod N \rangle$$

di mana indeks $k$, dengan $0 \le k \le m-1 = 7$, sepadan dengan Qubit kawalan. Jom kita kira $a^{2^k}\bmod N$ untuk setiap nilai $k$:

def a2kmodN(a, k, N):
    """Compute a^{2^k} (mod N) by repeated squaring"""
    for _ in range(k):
        a = int(np.mod(a**2, N))
    return a

k_list = range(8)
b_list = [a2kmodN(2, k, 15) for k in k_list]

print(b_list)

[2, 4, 1, 1, 1, 1, 1, 1]

Memandangkan $a^{2^k} \bmod N = 1$ untuk $k \ge 2$, semua operator yang sepadan ($M_8$ ke atas) bersamaan dengan identiti. Jadi, kita hanya perlu membina satu lagi matriks, iaitu $M_4.$

Nota: Penyederhanaan ini hanya berfungsi di sini kerana tertib $2 \bmod 15$ ialah $4$. Setelah $k=2$ (jadi $2^k = 4$), setiap kuasa operator seterusnya adalah identiti. Secara umum, untuk nombor $N$ yang lebih besar atau pilihan $a$ yang berbeza, anda tidak boleh melangkau pembinaan kuasa yang lebih tinggi. Inilah salah satu sebab mengapa ini dianggap contoh mainan: nombor kecil membenarkan jalan pintas yang tidak akan berfungsi untuk kes yang lebih besar.

def M4mod15():
    """
    M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M4 operator
M4 = M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M4, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

Dan seperti sebelum ini, kita jadikannya operator controlled-$M_4$:

def controlled_M4mod15():
    """
    Controlled M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M4 operator
controlled_M4 = controlled_M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M4, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Sekarang, kita boleh menyatukan semuanya untuk mencari tertib $2\bmod 15$ dengan Circuit kuantum, menggunakan penganggaran fasa:

# Order finding problem for N = 15 with a = 2
N = 15
a = 2

# Number of qubits
num_target = floor(log(N - 1, 2)) + 1  # for modular exponentiation operators
num_control = 2 * num_target  # for enough precision of estimation

# List of M_b operators in order
k_list = range(num_control)
b_list = [a2kmodN(2, k, 15) for k in k_list]

# Initialize the circuit
control = QuantumRegister(num_control, name="C")
target = QuantumRegister(num_target, name="T")
output = ClassicalRegister(num_control, name="out")
circuit = QuantumCircuit(control, target, output)

# Initialize the target register to the state |1>
circuit.x(num_control)

# Add the Hadamard gates and controlled versions of the
# multiplication gates
for k, qubit in enumerate(control):
    circuit.h(k)
    b = b_list[k]
    if b == 2:
        circuit.compose(
            M2mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    elif b == 4:
        circuit.compose(
            M4mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    else:
        continue  # M1 is the identity operator

# Apply the inverse QFT to the control register
circuit.compose(QFTGate(num_control).inverse(), qubits=control, inplace=True)

# Measure the control register
circuit.measure(control, output)

circuit.draw("mpl", fold=-1)

2. Optimumkan

Setelah memetakan Circuit kita, langkah seterusnya adalah mengoptimumkannya untuk dijalankan pada komputer kuantum tertentu. Pertama kita perlu memuatkan Backend.

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

Jika anda tidak mempunyai masa yang tersedia pada akaun anda atau ingin menggunakan simulator atas sebab tertentu, anda boleh jalankan sel di bawah untuk menyediakan simulator yang akan meniru peranti kuantum yang kita pilih di atas:

pm = generate_preset_pass_manager(optimization_level=2, backend=backend)

transpiled_circuit = pm.run(circuit)

print(f"2q-depth: {transpiled_circuit.depth(lambda x: x.operation.num_qubits==2)}")
print(f"2q-size: {transpiled_circuit.size(lambda x: x.operation.num_qubits==2)}")
print(f"Operator counts: {transpiled_circuit.count_ops()}")
transpiled_circuit.draw(output="mpl", fold=-1, style="clifford", idle_wires=False)

2q-depth: 188
2q-size: 281
Operator counts: OrderedDict({'sx': 548, 'rz': 380, 'cz': 281, 'measure': 8, 'x': 6})

3. Laksanakan

# Sampler primitive to obtain the probability distribution
sampler = Sampler(backend)

# Turn on dynamical decoupling with sequence XpXm
sampler.options.dynamical_decoupling.enable = True
sampler.options.dynamical_decoupling.sequence_type = "XpXm"
# Enable gate twirling
sampler.options.twirling.enable_gates = True

pub = transpiled_circuit
job = sampler.run([pub], shots=1024)

result = job.result()[0]
counts = result.data["out"].get_counts()

plot_histogram(counts, figsize=(35, 5))

Kita dapat melihat empat puncak jelas pada 00000000, 01000000, 10000000, dan 11000000, dengan beberapa kiraan dalam rentetan bit lain disebabkan oleh hingar dalam komputer kuantum. Kita akan mengabaikannya dan hanya menyimpan empat yang dominan dengan menetapkan ambang batas: hanya kiraan melebihi ambang ini yang dianggap isyarat sebenar di atas hingar.

# Dictionary of bitstrings and their counts to keep
counts_keep = {}
# Threshold to filter
threshold = np.max(list(counts.values())) / 2

for key, value in counts.items():
    if value > threshold:
        counts_keep[key] = value

print(counts_keep)

4. Proses semula

Untuk algoritma Shor, sebahagian besar algoritma dilaksanakan secara klasik. Jadi, kita akan letak selebihnya dalam langkah "pemprosesan semula", selepas kita mendapat pengukuran dari komputer kuantum. Setiap pengukuran di atas boleh ditukar kepada integer, yang setelah dibahagi dengan $2^m$, merupakan anggaran kita untuk $\frac{k}{r}$, di mana $k$ adalah rawak setiap kali.

a = 2
N = 15

FACTOR_FOUND = False
num_attempt = 0

while not FACTOR_FOUND:
    print(f"\nATTEMPT {num_attempt}:")
    # Here, we get the bitstring by iterating over outcomes
    # of a previous hardware run with multiple shots.
    # Instead, we can also perform a single-shot measurement
    # here in the loop.
    bitstring = list(counts_keep.keys())[num_attempt]
    num_attempt += 1
    # Find the phase from measurement
    decimal = int(bitstring, 2)
    phase = decimal / (2**num_control)  # phase = k / r
    print(f"Phase: theta = {phase}")

    # Guess the order from phase
    frac = Fraction(phase).limit_denominator(N)
    r = frac.denominator  # order = r
    print(f"Order of {a} modulo {N} estimated as: r = {r}")

    if phase != 0:
        # Guesses for factors are gcd(a^{r / 2} ± 1, 15)
        if r % 2 == 0:
            x = pow(a, r // 2, N) - 1
            d = gcd(x, N)
            if d > 1:
                FACTOR_FOUND = True
                print(f"*** Non-trivial factor found: {x} ***")

ATTEMPT 0:
Phase: theta = 0.0
Order of 2 modulo 15 estimated as: r = 1

ATTEMPT 1:
Phase: theta = 0.75
Order of 2 modulo 15 estimated as: r = 4
*** Non-trivial factor found: 3 ***

Kesimpulan

Setelah melalui modul ini, anda mungkin terpukau dengan kecemerlangan Peter Shor yang telah mencipta algoritma yang begitu bijak. Tapi semoga anda juga telah mencapai tahap pemahaman baru tentang kesederhanaan yang mengelirukan ini. Walaupun algoritma ini mungkin kelihatan sangat (atau menakutkan) kompleks, jika anda memecahkannya kepada setiap langkah logik dan melaluinya secara perlahan, anda juga akan dapat menjalankan algoritma Shor.

Walaupun kita masih jauh daripada menggunakan algoritma ini untuk memfaktorkan nombor seperti RSA1024, komputer kuantum kita semakin baik setiap hari, dan apabila ambang yang dipanggil toleransi kerosakan dicapai, algoritma seperti ini akan segera menyusul. Ini adalah masa yang menarik untuk belajar tentang pengkomputeran kuantum!

Masalah

Konsep kritikal:

• Sistem kriptografi moden bergantung pada kesukaran klasik untuk memfaktorkan integer besar.
• Aritmetik modular — termasuk struktur $\mathbb{Z}_N$ dan $\mathbb{Z}_N^*$ — menyediakan asas matematik untuk algoritma Shor.
• Masalah memfaktorkan integer $N$ boleh diturunkan kepada masalah mencari tertib suatu nombor modulo $N$.
• Pencarian tertib kuantum menggunakan teknik penganggaran fasa kuantum untuk menentukan tempoh fungsi $a^x \mod N$.
• Algoritma Shor terdiri daripada aliran kerja hibrid klasik-kuantum yang memilih asas, melakukan pencarian tertib kuantum, kemudian mengira faktor secara klasik daripada hasilnya.

Benar/Salah:

1. B/S Kecekapan algoritma Shor mengancam keselamatan penyulitan RSA.
2. B/S Algoritma Shor boleh dilaksanakan dengan cekap pada mana-mana komputer kuantum masa kini.
3. B/S Algoritma Shor menggunakan penganggaran fasa kuantum (QPE) sebagai subrutin utama.
4. B/S Bahagian klasik algoritma Shor melibatkan pengiraan pembahagi sepunya terbesar (GCD).
5. B/S Algoritma Shor hanya berfungsi untuk memfaktorkan nombor genap.
6. B/S Satu jalankan algoritma Shor yang berjaya sentiasa menjamin faktor yang betul.

Jawapan pendek:

1. Mengapa algoritma Shor dianggap ancaman masa depan yang berpotensi kepada penyulitan RSA?
2. Mengapa mencari tempoh, atau tertib, fungsi eksponen modular berguna untuk memfaktorkan nombor dalam algoritma Shor?

Soalan cabaran:

1. Berapa banyak Qubit kawalan $m$ yang kita perlukan untuk nombor $N$ yang cuba kita faktorkan bagi mendapatkan ketepatan dalam QPE yang diperlukan untuk mencari nilai tertib $r$ yang betul?

2. Mengikuti prosedur yang kita gariskan di sini untuk memfaktorkan 15, kini cuba faktorkan 21.