Algoritma Shor

Untuk modul Qiskit in Classrooms ini, siswa harus memiliki lingkungan Python yang berfungsi dengan paket-paket berikut terinstal:

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

Untuk mengatur dan menginstal paket-paket di atas, lihat panduan Instal Qiskit. Untuk menjalankan job di komputer kuantum sungguhan, siswa perlu membuat akun IBM Quantum® dengan mengikuti langkah-langkah di panduan Siapkan akun IBM Cloud-mu.

Modul ini telah diuji dan menggunakan tiga detik waktu QPU. Ini hanya perkiraan. Penggunaan aktualmu bisa berbeda.

# 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'

Pengantar

Di awal tahun 1990-an, ada kegembiraan yang berkembang seputar potensi komputer kuantum untuk memecahkan masalah yang sulit bagi komputer klasik. Beberapa ilmuwan komputer berbakat telah merancang algoritma yang menunjukkan kekuatan komputasi kuantum untuk beberapa masalah niche yang dibuat-buat, tapi belum ada yang menemukan satu "killer app" komputasi kuantum yang pasti akan merevolusi bidang ini. Itu berlangsung sampai tahun 1994, ketika Peter Shor menemukan apa yang sekarang disebut algoritma Shor untuk memfaktorkan bilangan besar.

Saat itu sudah diketahui bahwa menemukan faktor prima dari bilangan besar sangat sulit bagi komputer klasik. Bahkan, protokol keamanan internet mengandalkan kesulitan ini. Shor menemukan cara untuk menemukan faktor-faktor ini secara eksponensial lebih efisien dengan mengalihkan beberapa langkah yang lebih menantang ke komputer kuantum teoritis di masa depan.

Dalam modul ini, kita akan mengeksplorasi algoritma Shor. Pertama, kita akan memberikan sedikit lebih banyak konteks untuk algoritma ini, memformalkan masalah yang diselesaikannya dan menjelaskan relevansinya terhadap keamanan siber. Selanjutnya, kita akan memberikan pengantar tentang matematika modular dan cara menerapkannya pada masalah pemfaktoran, menunjukkan bagaimana pemfaktoran mereduksi ke masalah lain yang disebut "pencarian orde." Kita akan menunjukkan bagaimana Quantum Fourier Transform dan Quantum Phase Estimation yang telah kita pelajari di modul sebelumnya berperan, dan cara menggunakannya untuk memecahkan masalah pencarian orde.

Akhirnya, kita akan menjalankan algoritma Shor di komputer kuantum sungguhan! Tapi ingat, algoritma ini benar-benar hanya akan berguna ketika kita memiliki komputer kuantum yang besar dan toleran terhadap kesalahan, yang masih beberapa tahun lagi. Jadi, kita hanya akan memfaktorkan bilangan kecil untuk mendemonstrasikan cara kerja algoritma ini.

Masalah pemfaktoran

Tujuan masalah pemfaktoran adalah menemukan faktor prima dari sebuah bilangan $N$. Untuk beberapa bilangan $N$, ini cukup mudah. Misalnya, jika $N$ genap, salah satu faktor primanya adalah 2. Jika $N$ adalah perpangkatan prima, artinya $N=p^k$ untuk suatu bilangan prima $p$, juga cukup mudah menemukan $p$: kita hanya perlu mendekati akar ke-$k^{\text{th}}$ dari $N$ dan mencari bilangan prima terdekat yang bisa menjadi $p$.

Di mana komputer klasik kesulitan, yaitu ketika $N$ ganjil dan bukan perpangkatan prima. Inilah kasus yang ditangani algoritma Shor. Algoritma ini menemukan dua faktor $p$ dan $q$ sedemikian sehingga $N=pq$. Algoritma ini bisa diterapkan secara rekursif sampai semua faktor adalah prima. Di bagian berikutnya kita akan melihat bagaimana masalah ini ditangani.

Relevansi terhadap keamanan siber

Banyak skema kriptografi dibangun berdasarkan fakta bahwa memfaktorkan bilangan besar itu sulit, termasuk salah satu yang umum digunakan saat ini, disebut RSA. Dalam RSA, kunci publik dibuat dengan mengalikan dua bilangan prima besar untuk mendapatkan $N = p\cdot q$. Kemudian, siapa pun bisa menggunakan kunci publik ini untuk mengenkripsi data. Tapi hanya orang yang memiliki kunci privat, $p$ dan $q$, yang bisa mendekripsi data itu.

Jika $N$ mudah difaktorkan, maka siapa pun akan bisa menentukan apa itu $p$ dan $q$ dan membobol enkripsinya. Tapi tidak seperti itu. Ini adalah masalah yang terkenal sulit. Bahkan, faktor prima dari sebuah bilangan yang disebut RSA1024, yang panjangnya 1024 digit biner dan 309 digit desimal, belum ditemukan sampai saat ini, meskipun hadiah sebesar $100.000 sudah ditawarkan untuk pemfaktorannya sejak tahun 1991.

Solusi Shor

Pada tahun 1994, Peter Shor menyadari bahwa komputer kuantum bisa memfaktorkan bilangan besar secara eksponensial lebih efisien daripada komputer klasik. Wawasannya mengandalkan hubungan antara masalah pemfaktoran ini dan aritmatika modular. Kita akan membahas pengantar singkat tentang aritmatika modular, lalu kita akan melihat bagaimana kita bisa menggunakannya untuk memfaktorkan $N$.

Aritmatika modular

Aritmatika modular adalah sistem penghitungan yang bersifat siklik, artinya meski penghitungan dimulai dengan cara biasa, dengan bilangan bulat 0, 1, 2, dst., pada titik tertentu, setelah periode $N$, penghitungan dimulai lagi dari awal. Mari kita lihat cara kerjanya dengan contoh. Katakanlah periode kita adalah 5. Kemudian, saat kita menghitung, di mana kita biasanya mencapai 5, kita malah mulai lagi dari 0:

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

Ini karena dalam dunia "modulo-5", 5 setara dengan 0. Kita katakan bahwa $5\bmod 5 \ = 0$. Bahkan, semua kelipatan 5 akan setara dengan $0\bmod 5$.

Cek pemahaman

Baca pertanyaan di bawah, pikirkan jawabanmu, lalu klik segitiga untuk melihat solusinya.

Gunakan aritmatika modular untuk menyelesaikan masalah berikut:

Kamu berangkat naik kereta lintas benua yang panjang pada pukul 8 pagi. Perjalanan kereta berlangsung 60 jam. Pukul berapa saat kamu tiba?

Jawaban:

Periodenya adalah 24, karena ada 24 jam dalam sehari. Jadi, masalah ini bisa ditulis dalam aritmatika modular sebagai:

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

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

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

Seringkali berguna untuk memperkenalkan dua himpunan, $\mathbb{Z}_N$ dan $\mathbb{Z}_N^*$. $\mathbb{Z}_N$ adalah himpunan bilangan yang ada di dunia "modulo-$N$". Misalnya, saat kita menghitung modulo-5, himpunannya adalah $\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 bisa melakukan penjumlahan dan perkalian (modulo $N$) pada elemen-elemen di $\mathbb{Z}_N$, dan hasil setiap operasi ini juga merupakan elemen di $\mathbb{Z}_N$, menjadikan $\mathbb{Z}_N$ sebuah objek matematika yang disebut ring.

Ada subset khusus dari $\mathbb{Z}_N$ yang sangat menarik bagi kita untuk algoritma Shor. Yaitu subset dari bilangan-bilangan di $\mathbb{Z}_N$ sedemikian sehingga pembagi persekutuan terbesar antara setiap elemen dan $N$ adalah 1, sehingga setiap elemen "ko-prima" dengan $N$. Jika kita mengambil himpunan bilangan-bilangan ini bersama operasi perkalian modular, maka ini membentuk objek matematika lain, yang disebut grup. Kita sebut grup ini $\mathbb{Z}_N^*$. Ternyata dengan $\mathbb{Z}_N^*$ (dan grup hingga pada umumnya), jika kita memilih elemen mana pun $a \in \mathbb{Z}_N^*$, dan berulang kali mengalikan $a$ dengan dirinya sendiri, kita pada akhirnya selalu akan mendapatkan angka $1$. Jumlah minimum kali seseorang harus mengalikan $a$ dengan dirinya sendiri untuk mendapatkan $1$ disebut orde dari $a$. Fakta ini akan sangat penting untuk pembahasan kita tentang cara memfaktorkan bilangan di bawah ini.

Cek pemahaman

Baca pertanyaan di bawah, pikirkan jawabanmu, lalu klik segitiga untuk melihat solusinya.

Apa itu $\mathbb{Z}_{15}^*$?

Jawaban:

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

Kita mengecualikan bilangan-bilangan 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}$$

Apa orde dari setiap elemen di $\mathbb{Z}_{15}^*$?

Jawaban:

Orde $r$ adalah bilangan terkecil sedemikian sehingga $a^r\text{mod}(15)=1$ untuk 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 bahwa, meski kita bisa menemukan orde dari bilangan-bilangan di $\mathbb{Z}_{15}^*$, ini BUKAN tugas yang mudah secara umum, untuk $N$ yang lebih besar. Ini adalah inti dari masalah pemfaktoran dan mengapa kita membutuhkan komputer kuantum. Kita akan melihat alasannya saat kita mengerjakan sisa notebook ini.

Terapkan aritmatika modular pada masalah pemfaktoran

Kunci untuk menemukan faktor $p$ dan $q$ sedemikian sehingga $N=pq$ bergantung pada penemuan bilangan bulat lain $x$ sedemikian sehingga

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

Bagaimana menemukan $x$ membantu kita menemukan faktor $p$ dan $q$? Mari kita telusuri argumennya sekarang. Karena $x^2 \equiv 1 \bmod N$, itu berarti $x^2 - 1 \equiv 0 \bmod N$. Dengan kata lain, $x^2 - 1$ adalah kelipatan dari $N$. Jadi, untuk suatu bilangan bulat $l$,

$x^2 - 1 = l N$

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

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

Dari asumsi awal kita tahu bahwa $x \not\equiv \pm 1 \bmod N$, sehingga $N$ tidak habis membagi $x+1$ maupun $x-1$. Jadi, dua faktor dari $N$, $p$ dan $q$, masing-masing harus membagi $x-1$ dan $x+1$. Entah $p$ adalah faktor dari $x-1$ dan $q$ adalah faktor dari $x+1$, atau sebaliknya. Oleh karena itu, jika kita menghitung pembagi persekutuan terbesar (GCD) antara $N$ dan keduanya $x-1$ serta $x+1$, itu akan memberi kita faktor $p$ dan $q$. Menghitung GCD antara dua bilangan adalah tugas yang mudah secara klasik yang bisa dilakukan, misalnya, menggunakan algoritma Euclid.

Cek pemahaman

Baca pertanyaan di bawah, pikirkan jawabanmu, lalu klik segitiga untuk melihat solusinya.

Mungkin sulit untuk memahami setiap langkah logika di atas, jadi coba kerjakan dengan contoh. Gunakan $N=15$ dan $x=11$. Pertama, verifikasi bahwa $x^2 \equiv 1 \text{mod}(N)$ dan $x \not\equiv \pm 1 \bmod N$. Kemudian lanjutkan untuk memverifikasi setiap langkah. Akhirnya, hitung $\text{GCD}(11\pm1,15)$ dan verifikasi bahwa mereka adalah faktor dari $15$.

Jawaban:

$11^2 = 121$, yang merupakan $15*8 + 1$, sehingga $11^2\bmod 15 = 1$. $\checkmark$

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

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

Sekarang, kita tahu bahwa $(x+1)(x-1) = l N$ untuk suatu bilangan bulat $l$. Ini diverifikasi saat kita memasukkan $x$ dan $N$: $(12)(10) = l 15$ ketika $l = 8$. $\checkmark$

Sekarang, kita perlu menghitung $\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 menemukan faktor-faktor dari $15$!

Algoritma

Sekarang kita sudah melihat bagaimana menemukan bilangan bulat $x$ sedemikian sehingga $x^2 \equiv 1\bmod N$ membantu kita memfaktorkan $N$, kita bisa menelusuri algoritma Shor. Intinya berpusat pada menemukan $x$:

1. Pilih bilangan bulat acak Pilih bilangan bulat acak $a$ sedemikian sehingga $1 < a < N$.

• Hitung $\text{GCD}(a, N)$ secara klasik.
  • Jika $\text{GCD}(a, N) > 1$, kamu sudah menemukan faktornya. Berhenti.
  • Jika tidak, lanjutkan.

2. Temukan orde $r$ dari $a$ modulo $N$ Temukan bilangan bulat positif terkecil $r$ yang memenuhi $a^r \equiv 1 \pmod N$.

3. Periksa apakah orde itu genap

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

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

• Periksa bahwa $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, hitung gcd untuk mengekstrak faktor-faktornya:

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

Ini akan menjadi faktor non-trivial dari $N$.

5. Faktorkan secara rekursif jika diperlukan

• Jika $p$ dan/atau $q$ bukan prima, terapkan algoritma secara rekursif untuk memfaktorkannya sepenuhnya.
• Setelah semua faktor adalah prima, pemfaktoran selesai.

Berdasarkan prosedur ini, mungkin tidak jelas mengapa komputer kuantum diperlukan untuk menyelesaikan tugas ini. Ini diperlukan karena langkah 2, menemukan orde $a$ modulo $N$, secara klasik merupakan masalah yang sangat sulit. Kompleksitasnya bertambah secara eksponensial terhadap bilangan $N$. Tapi dengan komputer kuantum, kita hanya perlu memanfaatkan Quantum Phase Estimation untuk menyelesaikannya. Langkah 4, menemukan GCD dari dua bilangan bulat, sebenarnya cukup mudah dilakukan secara klasik. Jadi, satu-satunya langkah yang benar-benar membutuhkan kekuatan komputer kuantum adalah langkah pencarian orde. Kita katakan bahwa masalah pemfaktoran "mereduksi" ke masalah pencarian orde.

Bagian yang sulit: pencarian orde

Sekarang, kita akan membahas bagaimana kita bisa menggunakan komputer kuantum dalam pencarian orde. Pertama, mari kita perjelas apa yang kita maksud dengan "orde." Tentu saja, aku sudah memberitahumu apa arti orde secara matematis: ini adalah bilangan bulat non-nol pertama $r$ sedemikian sehingga $a^r = 1 \pmod N.$ Tapi mari kita lihat apakah kita bisa mendapatkan sedikit lebih banyak intuisi untuk konsep ini.

Untuk $N$ yang cukup kecil, kita bisa menentukan orde hanya dengan menghitung setiap perpangkatan dari $a$, mengambil modulus $N$ dari bilangan itu, lalu berhenti saat kita menemukan pangkat $r$ yang memenuhi $a^r = 1 \text{mod}(N)$. Itulah yang kita lakukan dengan contoh kita, $N=15$, di atas. Mari kita lihat beberapa grafik dari perpangkatan modular ini untuk beberapa nilai sampel dari $a$ dan $N$:

Perhatikan sesuatu? Ini adalah fungsi periodik! Dan orde $r$ sama dengan periodenya! Jadi, pencarian orde setara dengan pencarian periode.

Komputer kuantum sangat cocok untuk menemukan periode dari fungsi. Untuk ini, kita bisa menggunakan subrutin algoritma yang disebut Quantum Phase Estimation. Kita membahas QPE dan hubungannya dengan Quantum Fourier Transform di modul sebelumnya. Untuk penyegaran yang lebih detail, kunjungi modul QFT atau pelajaran John Watrous tentang Quantum Phase Estimation di kursus Algoritma Kuantum miliknya. Kita akan menelusuri inti prosedurnya sekarang:

Dalam Quantum Phase Estimation (QPE), kita mulai dengan unitary $U$ dan eigenstate dari unitary tersebut $|\psi\rangle$. Kemudian, kita menggunakan QPE untuk mendekati nilai eigennya yang sesuai, yang, karena operatornya adalah unitary, akan berbentuk $e^{2\pi i \theta}$. Jadi, menemukan nilai eigen setara dengan menemukan nilai $\theta$ dalam fungsi periodik. Circuit-nya terlihat seperti ini:

di mana jumlah qubit kontrol ($m$ qubit teratas dalam gambar di atas) menentukan presisi perkiraan.

Dalam algoritma Shor, kita menggunakan QPE pada operator unitary $M_a$:

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

Di sini, $|y\rangle$ menunjukkan computational basis state dari register multi-Qubit, di mana nilai biner dari qubit-Qubit tersebut sesuai dengan bilangan bulat $y$. Misalnya, jika $N=15$ dan $y = 2$, maka $|y\rangle$ direpresentasikan oleh basis state empat-Qubit $|0010\rangle$, karena empat qubit diperlukan untuk mengkodekan bilangan hingga 15. (Jika konsep ini belum familiar, lihat modul pengantar Qiskit in classrooms untuk penyegaran tentang pengkodean biner status kuantum.)

Sekarang, kita perlu mencari tahu eigenstate dari unitary ini. Jika kita mulai dalam keadaan $|1\rangle$, kita bisa melihat bahwa setiap penerapan $U$ yang berturutan akan mengalikan keadaan register kita dengan $a \pmod N$, dan setelah $r$ penerapan kita akan tiba di keadaan $|1\rangle$ lagi. Misalnya 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 dari keadaan dalam siklus ini ($|\psi_j\rangle$) berbentuk:

$|\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 dari $M_a$. (Ada lebih banyak eigenstate selain ini. Tapi kita hanya peduli dengan yang berbentuk di atas.)

Cek pemahaman

Baca pertanyaan di bawah, pikirkan jawabanmu, lalu klik segitiga untuk melihat solusinya.

Temukan eigenstate dari unitary yang sesuai dengan $a=2$ dan $N = 15$.

Jawaban:

$$\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, orde $r=4$. Eigenstate yang kita minati akan berupa superposisi merata dari semua keadaan yang telah disiklus di atas, dengan berbagai fase:

$$\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}$$

Katakanlah kita bisa menginisialisasi keadaan qubit kita ke salah satu eigenstate ini (spoiler — kita tidak bisa. Atau, setidaknya tidak mudah. Kita akan menjelaskan alasannya dan apa yang bisa kita lakukan sebagai gantinya sebentar lagi). Kemudian kita bisa menggunakan QPE untuk memperkirakan nilai eigen yang sesuai, $\omega_j = e^{2 \pi i \theta_j}$ di mana $\theta_j = \frac{j}{r}$. Kemudian, kita akan bisa menentukan orde $r$ dengan persamaan sederhana:

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

Tapi ingat, aku bilang bahwa QPE memperkirakan $\theta_j$ — itu tidak memberi kita nilai yang tepat. Kita perlu perkiraan yang cukup baik untuk membedakan antara $r$ dan $r+1$. Semakin banyak qubit kontrol $m$ yang kita miliki, semakin baik perkiraannya. Dalam soal-soal di akhir pelajaran, kamu akan diminta untuk menentukan $m$ minimum yang diperlukan untuk memfaktorkan suatu bilangan $N$.

Sekarang, kita harus menyelesaikan sebuah masalah. Semua penjelasan di atas tentang cara menemukan $r$ dimulai dengan menyiapkan eigenstate $|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$. Tapi kita tidak tahu cara melakukannya tanpa sudah mengetahui $r$. Logikanya melingkar. Kita membutuhkan cara untuk memperkirakan nilai eigen tanpa menginisialisasi eigenstate.

Alih-alih memulai dengan eigenstate dari $M_a$, kita bisa menyiapkan keadaan awal ke keadaan $n$-Qubit yang sesuai dengan $|1\rangle$ dalam biner (yaitu, $|000...01\rangle$). Meskipun keadaan ini jelas bukan eigenstate dari $M_a$, ini adalah superposisi atas semua eigenstate $|\psi_k\rangle$:

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

Cek pemahaman

Baca pertanyaan di bawah, pikirkan jawabanmu, lalu klik segitiga untuk melihat solusinya.

Verifikasi bahwa $|1\rangle$ setara dengan superposisi atas eigenstate yang kamu temukan untuk $N=15$ dan $a=2$ dalam pertanyaan cek sebelumnya.

Jawaban:

Empat eigenstate tersebut adalah:

$$\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 memungkinkan kita menemukan orde $r$? Karena keadaan awal adalah superposisi atas semua eigenstate dari bentuk yang tercantum di atas, maka algoritma QPE secara bersamaan memperkirakan masing-masing $\theta_k$ yang sesuai dengan eigenstate-eigenstate ini. Jadi, pengukuran dari $m$ qubit kontrol di akhir akan menghasilkan pendekatan nilai $k/r$ di mana $k \in \{0,1,2,...,r-1\}$ adalah salah satu nilai eigen yang dipilih secara acak. Jika kita mengulangi Circuit ini beberapa kali dan mendapatkan beberapa sampel dengan nilai $k$ yang berbeda, kita akan segera bisa menentukan $r$.

Implementasi di Qiskit

Seperti yang kita sebutkan sebelumnya, hardware kita belum sampai pada titik di mana kita bisa memfaktorkan bilangan besar seperti RSA1024. Kita hanya akan memfaktorkan bilangan kecil untuk mendemonstrasikan cara kerja algoritma ini. Untuk demo ini, kita akan menggunakan versi yang disederhanakan dari kode yang disajikan dalam tutorial algoritma Shor. Jika kamu ingin lebih banyak detail, silakan kunjungi tutorial tersebut.

Kita akan menjalankan algoritma menggunakan framework standar kita untuk memecahkan masalah kuantum, yang disebut framework Qiskit patterns. Ini terdiri dari empat langkah:

1. Pemetaan masalahmu ke Circuit kuantum
2. Optimalkan Circuit untuk dijalankan di hardware kuantum
3. Jalankan Circuit-mu di komputer kuantum
4. Pasca-proses pengukuran

1. Peta

Mari kita faktorkan $N=15$, memilih $a=2$ sebagai bilangan bulat ko-prima kita.

Pertama, kita perlu membangun Circuit yang akan mengimplementasikan unitary perkalian modular, $M_a$. Ini sebenarnya bagian yang paling rumit dari seluruh implementasi, dan bisa sangat mahal secara komputasi, tergantung cara melakukannya. Untuk ini, kita akan sedikit curang: Kita tahu bahwa kita mulai dalam keadaan $|1\rangle$, dan dari pertanyaan cek sebelumnya,

$$\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 membangun unitary yang melakukan operasi yang benar pada empat keadaan ini, tapi membiarkan semua keadaan lain apa adanya. Ini curang karena kita menggunakan pengetahuan kita tentang orde $2\bmod 15$ untuk menyederhanakan unitary. Jika kita benar-benar mencoba memfaktorkan suatu bilangan yang faktor-faktornya tidak diketahui oleh kita, kita tidak akan bisa melakukan ini.

Cek pemahamanmu

Baca pertanyaan di bawah ini, pikirkan jawabanmu, lalu klik segitiga untuk melihat solusinya.

Dengan pengetahuanmu tentang bagaimana operator $M_2$ mentransformasi state-state di atas, bangun operator tersebut dari serangkaian gate SWAP, yang menukar state dua qubit. (Petunjuk: menulis setiap state $|i\rangle$ dalam biner akan membantu.)

Jawaban:

Mari kita tulis ulang aksi $M_2$ pada state-state dalam biner:

$$\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 aksi ini bisa dicapai dengan SWAP sederhana. $M_2|0001\rangle$ dicapai dengan menukar state qubit $0$ dan $1$. $M_2|0010\rangle$ dicapai dengan menukar state qubit $1$ dan $2$. Dan seterusnya. Jadi, kita bisa mengurai matriks $M_2$ menjadi serangkaian gate SWAP berikut:

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

Ingat bahwa operator bekerja dari kanan ke kiri, mari kita periksa bahwa ini memiliki efek yang kita inginkan pada setiap state:

$$\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}$$

Sekarang kita bisa membuat kode Circuit yang setara dengan operator ini di Qiskit.

Pertama, kita impor paket-paket 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 punya Circuit $M_2$, kita perlu membuatnya menjadi 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)

Sekarang kita punya gate controlled-$U$. Tapi untuk menjalankan algoritma Quantum Phase Estimation, kita perlu controlled-$U^2$, controlled-$U^4$, hingga controlled-$U^{2^{m-1}}$, di mana $m$ adalah jumlah qubit yang digunakan untuk memperkirakan fase. Semakin banyak qubit, semakin presisi estimasi fase. Kita akan menggunakan $m=8$ qubit kontrol untuk prosedur estimasi fase kita. Jadi, kita perlu:

$$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$, bersesuaian dengan qubit kontrol. Sekarang mari kita hitung $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]

Karena $a^{2^k} \bmod N = 1$ untuk $k \ge 2$, semua operator yang bersesuaian ($M_8$ ke atas) ekuivalen dengan identitas. Jadi, kita hanya perlu membuat satu matriks lagi, $M_4.$

Catatan: Penyederhanaan ini hanya berlaku di sini karena orde $2 \bmod 15$ adalah $4$. Begitu $k=2$ (sehingga $2^k = 4$), setiap pangkat operator berikutnya adalah identitas. Secara umum, untuk bilangan $N$ yang lebih besar atau pilihan $a$ yang berbeda, kamu tidak bisa melewati konstruksi pangkat-pangkat yang lebih tinggi. Inilah salah satu alasan mengapa ini dianggap sebagai contoh mainan: angka-angka kecil memungkinkan jalan pintas yang tidak akan berhasil untuk kasus 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 sebelumnya, kita membuatnya menjadi 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 bisa menyatukan semuanya untuk menemukan orde $2\bmod 15$ dengan Circuit kuantum, menggunakan estimasi fase:

# 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. Optimize

Sekarang kita sudah memetakan Circuit kita, langkah berikutnya adalah mengoptimalkannya untuk dijalankan pada komputer kuantum tertentu. Pertama kita perlu memuat Backend.

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

Jika kamu tidak punya waktu yang tersedia di akunmu atau ingin menggunakan simulator karena alasan apapun, kamu bisa menjalankan sel di bawah ini untuk menyiapkan simulator yang akan meniru perangkat 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. Execute

# 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 melihat empat puncak yang jelas di 00000000, 01000000, 10000000, dan 11000000, dengan beberapa hitungan pada bitstring lain akibat noise di komputer kuantum. Kita akan mengabaikan ini dan hanya menyimpan empat yang dominan dengan menerapkan ambang batas: hanya hitungan di atas ambang batas ini yang dianggap sebagai sinyal nyata di atas noise.

# 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. Post-process

Untuk algoritma Shor, sebagian besar algoritma dijalankan secara klasik. Jadi, kita akan menempatkan sisanya di langkah "post-processing", setelah kita mendapatkan pengukuran dari komputer kuantum. Setiap pengukuran di atas dapat dikonversi menjadi bilangan bulat, yang, setelah dibagi dengan $2^m$, adalah perkiraan kita untuk $\frac{k}{r}$, di mana $k$ adalah acak 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 mempelajari modul ini, kamu mungkin merasa kagum dengan kecerdasan Peter Shor yang menemukan algoritma yang begitu cerdik. Tapi semoga kamu juga telah mencapai pemahaman baru tentang kesederhanaannya yang menipu. Meskipun algoritma ini mungkin tampak sangat (atau mengintimidasi) kompleks, jika kamu uraikan menjadi setiap langkah logika dan menelusurinya perlahan, kamu pun akan bisa menjalankan algoritma Shor.

Meskipun kita masih jauh dari menggunakan algoritma ini untuk memfaktorkan angka seperti RSA1024, komputer kuantum kita terus berkembang setiap hari, dan begitu ambang batas yang disebut toleransi kesalahan tercapai, algoritma-algoritma seperti inilah yang akan segera menyusul. Ini adalah waktu yang menarik untuk belajar tentang komputasi kuantum!

Soal-soal

Konsep kritis:

• Sistem kriptografi modern mengandalkan sulitnya pemfaktoran bilangan bulat besar secara klasik.
• Aritmetika modular — termasuk struktur $\mathbb{Z}_N$ dan $\mathbb{Z}_N^*$ — memberikan fondasi matematis untuk algoritma Shor.
• Masalah pemfaktoran bilangan bulat $N$ bisa direduksi menjadi masalah menemukan orde suatu bilangan modulo $N$.
• Pencarian orde kuantum menggunakan teknik estimasi fase kuantum untuk menentukan periode fungsi $a^x \mod N$.
• Algoritma Shor terdiri dari alur kerja hibrida klasik–kuantum yang memilih basis, melakukan pencarian orde kuantum, kemudian secara klasik menghitung faktor-faktor dari hasilnya.

Benar/Salah:

1. B/S Efisiensi algoritma Shor mengancam keamanan enkripsi RSA.
2. B/S Algoritma Shor bisa dijalankan secara efisien pada komputer kuantum modern manapun.
3. B/S Algoritma Shor menggunakan estimasi fase kuantum (QPE) sebagai subrutin kunci.
4. B/S Bagian klasik dari algoritma Shor melibatkan perhitungan faktor persekutuan terbesar (FPB).
5. B/S Algoritma Shor hanya bekerja untuk memfaktorkan bilangan genap.
6. B/S Satu kali menjalankan algoritma Shor dengan sukses selalu menjamin faktor yang benar.

Jawaban singkat:

1. Mengapa algoritma Shor dianggap sebagai ancaman masa depan yang potensial terhadap enkripsi RSA?
2. Mengapa menemukan periode, atau orde, dari fungsi eksponensial modular membantu pemfaktoran bilangan dalam algoritma Shor?

Soal tantangan:

1. Berapa banyak qubit kontrol $m$ yang kita butuhkan untuk bilangan $N$ yang ingin kita faktorkan guna memperoleh presisi dalam QPE yang diperlukan untuk menemukan nilai orde $r$ yang benar?

2. Mengikuti prosedur yang kita uraikan di sini untuk memfaktorkan 15, sekarang coba faktorkan 21.