Algoritma Shor

Sekarang kita akan beralih ke masalah faktorisasi bilangan bulat, dan melihat bagaimana masalah ini bisa diselesaikan secara efisien di komputer kuantum menggunakan estimasi fase. Algoritma yang akan kita dapatkan adalah algoritma Shor untuk faktorisasi bilangan bulat. Shor tidak mendeskripsikan algoritmanya secara khusus dalam hal estimasi fase, tapi itu adalah cara yang alami dan intuitif untuk menjelaskan cara kerjanya.

Kita akan mulai dengan membahas masalah perantara yang dikenal sebagai masalah pencarian orde dan melihat bagaimana estimasi fase memberikan solusi untuk masalah ini. Kita kemudian akan melihat bagaimana solusi efisien untuk masalah pencarian orde memberikan kita solusi efisien untuk masalah faktorisasi bilangan bulat. (Ketika solusi untuk satu masalah memberikan solusi untuk masalah lain seperti ini, kita bilang bahwa masalah kedua mereduksi ke yang pertama — jadi dalam hal ini kita mereduksi faktorisasi bilangan bulat ke pencarian orde.) Bagian kedua dari algoritma Shor ini sama sekali tidak menggunakan komputasi kuantum; ini sepenuhnya klasik. Komputasi kuantum hanya diperlukan untuk menyelesaikan pencarian orde.

Masalah pencarian orde

Beberapa teori bilangan dasar

Untuk menjelaskan masalah pencarian orde dan bagaimana ia bisa diselesaikan menggunakan estimasi fase, akan sangat membantu untuk mulai dengan beberapa konsep dasar teori bilangan, dan memperkenalkan beberapa notasi yang berguna seiring pembahasan.

Untuk memulai, untuk setiap bilangan bulat positif $N,$ definisikan himpunan $\mathbb{Z}_N$ seperti ini.

$$\mathbb{Z}_N = \{0,1,\ldots,N-1\}$$

Sebagai contoh, $\mathbb{Z}_1 = \{0\},\;$ $\mathbb{Z}_2 = \{0,1\},\;$ $\mathbb{Z}_3 = \{0,1,2\},\;$ dan seterusnya.

Ini adalah himpunan bilangan, tapi kita bisa menganggapnya lebih dari sekadar himpunan. Khususnya, kita bisa memikirkan operasi aritmetika pada $\mathbb{Z}_N$ seperti penjumlahan dan perkalian — dan jika kita sepakat untuk selalu mengambil jawaban kita modulo $N$ (yaitu, membagi dengan $N$ dan mengambil sisa sebagai hasilnya), kita akan selalu tetap dalam himpunan ini ketika kita melakukan operasi ini. Dua operasi spesifik penjumlahan dan perkalian, keduanya diambil modulo $N,$ mengubah $\mathbb{Z}_N$ menjadi sebuah ring, yang merupakan jenis objek yang sangat penting dalam aljabar.

Misalnya, $3$ dan $5$ adalah elemen dari $\mathbb{Z}_7,$ dan jika kita mengalikannya kita mendapat $3\cdot 5 = 15,$ yang meninggalkan sisa $1$ ketika dibagi $7.$ Kadang kita mengekspresikan ini sebagai berikut.

$$3 \cdot 5 \equiv 1 \; (\textrm{mod } 7)$$

Tapi kita juga bisa menulis $3 \cdot 5 = 1,$ asalkan sudah jelas bahwa kita bekerja dalam $\mathbb{Z}_7,$ hanya untuk menjaga notasi kita sesederhana mungkin.

Sebagai contoh, berikut adalah tabel penjumlahan dan perkalian untuk $\mathbb{Z}_6.$

$$\begin{array}{c|cccccc} + & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \\ \end{array} \qquad \begin{array}{c|cccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \end{array}$$

Di antara $N$ elemen dari $\mathbb{Z}_N,$ elemen-elemen $a\in\mathbb{Z}_N$ yang memenuhi $\gcd(a,N) = 1$ adalah istimewa. Seringkali himpunan yang berisi elemen-elemen ini dinotasikan dengan tanda bintang seperti ini.

$$\mathbb{Z}_N^{\ast} = \{a\in \mathbb{Z}_N : \gcd(a,N) = 1\}$$

Jika kita memusatkan perhatian pada operasi perkalian, himpunan $\mathbb{Z}_N^{\ast}$ membentuk sebuah grup — khususnya sebuah grup abelian — yang merupakan jenis objek penting lainnya dalam aljabar. Ini adalah fakta dasar tentang himpunan-himpunan ini (dan grup hingga pada umumnya), bahwa jika kita memilih sembarang elemen $a\in\mathbb{Z}_N^{\ast}$ dan berulang kali mengalikan $a$ dengan dirinya sendiri, kita akan selalu akhirnya mendapat angka $1.$

Untuk contoh pertama, ambil $N=6.$ Kita punya bahwa $5\in\mathbb{Z}_6^{\ast}$ karena $\gcd(5,6) = 1,$ dan jika kita mengalikan $5$ dengan dirinya sendiri kita mendapat $1,$ seperti yang dikonfirmasi tabel di atas.

$$5^2 = 1 \quad \text{(working within $\mathbb{Z}_6$)}$$

Sebagai contoh kedua, ambil $N = 21.$ Jika kita menelusuri bilangan dari $0$ hingga $20,$ yang memiliki GCD sama dengan $1$ dengan $21$ adalah sebagai berikut.

$$\mathbb{Z}_{21}^{\ast} = \{1,2,4,5,8,10,11,13,16,17,19,20\}$$

Untuk setiap elemen ini, dimungkinkan untuk memangkatkan bilangan tersebut ke pangkat bilangan bulat positif untuk mendapat $1.$ Berikut adalah pangkat terkecil yang berhasil:

$$\begin{array}{ccc} 1^{1} = 1 \quad & 8^{2} = 1 \quad & 16^{3} = 1 \\[1mm] 2^{6} = 1 \quad & 10^{6} = 1 \quad & 17^{6} = 1 \\[1mm] 4^{3} = 1 \quad & 11^{6} = 1 \quad & 19^{6} = 1 \\[1mm] 5^{6} = 1 \quad & 13^{2} = 1 \quad & 20^{2} = 1 \end{array}$$

Tentu saja kita bekerja dalam $\mathbb{Z}_{21}$ untuk semua persamaan ini, yang tidak kita tulis — kita anggap itu implisit untuk menghindari kerumitan. Kita akan terus melakukan itu di sepanjang sisa pelajaran.

Pernyataan masalah dan hubungan dengan estimasi fase

Sekarang kita bisa menyatakan masalah pencarian orde.

Pencarian orde

Input: bilangan bulat positif $N$ dan $a$ yang memenuhi $\gcd(N,a) = 1$
Output: bilangan bulat positif terkecil $r$ sedemikian sehingga $a^r \equiv 1$ $(\textrm{mod } N)$

Atau, dalam hal notasi yang baru kita perkenalkan di atas, kita diberi $a \in \mathbb{Z}_N^{\ast},$ dan kita mencari bilangan bulat positif terkecil $r$ sedemikian sehingga $a^r = 1.$ Bilangan $r$ ini disebut orde dari $a$ modulo $N.$

Untuk menghubungkan masalah pencarian orde dengan estimasi fase, mari kita pikirkan tentang operasi yang didefinisikan pada sebuah sistem yang keadaan klasiknya bersesuaian dengan $\mathbb{Z}_N,$ di mana kita mengalikan dengan elemen tetap $a\in\mathbb{Z}_N^{\ast}.$

$$M_a \vert x\rangle = \vert ax \rangle \qquad \text{(for each $x\in\mathbb{Z}_N$)}$$

Untuk jelasnya, kita melakukan perkalian dalam $\mathbb{Z}_N,$ jadi tersirat bahwa kita mengambil hasil kali modulo $N$ di dalam ket pada sisi kanan persamaan.

Misalnya, jika kita ambil $N = 15$ dan $a=2,$ maka aksi $M_2$ pada basis standar $\{\vert 0\rangle,\ldots,\vert 14\rangle\}$ adalah sebagai berikut.

$$\begin{array}{ccc} M_{2} \vert 0 \rangle = \vert 0\rangle \quad & M_{2} \vert 5 \rangle = \vert 10\rangle \quad & M_{2} \vert 10 \rangle = \vert 5\rangle \\[1mm] M_{2} \vert 1 \rangle = \vert 2\rangle \quad & M_{2} \vert 6 \rangle = \vert 12\rangle \quad & M_{2} \vert 11 \rangle = \vert 7\rangle \\[1mm] M_{2} \vert 2 \rangle = \vert 4\rangle \quad & M_{2} \vert 7 \rangle = \vert 14\rangle \quad & M_{2} \vert 12 \rangle = \vert 9\rangle \\[1mm] M_{2} \vert 3 \rangle = \vert 6\rangle \quad & M_{2} \vert 8 \rangle = \vert 1\rangle \quad & M_{2} \vert 13 \rangle = \vert 11\rangle \\[1mm] M_{2} \vert 4 \rangle = \vert 8\rangle \quad & M_{2} \vert 9 \rangle = \vert 3\rangle \quad & M_{2} \vert 14 \rangle = \vert 13\rangle \end{array}$$

Ini adalah operasi uniter asalkan $\gcd(a,N)=1;$ ini mengacak elemen-elemen basis standar $\{\vert 0\rangle,\ldots,\vert N-1\rangle\},$ jadi sebagai matriks ia adalah matriks permutasi. Jelas dari definisinya bahwa operasi ini deterministik, dan cara sederhana untuk melihat bahwa ia invertibel adalah dengan memikirkan orde $r$ dari $a$ modulo $N,$ dan menyadari bahwa invers dari $M_a$ adalah $M_a^{r-1}.$

$$M_a^{r-1} M_a = M_a^r = M_{a^r} = M_1 = \mathbb{I}$$

Ada cara lain untuk memikirkan invers yang tidak memerlukan pengetahuan tentang $r$ (yang, bagaimanapun juga, adalah yang ingin kita hitung). Untuk setiap elemen $a\in\mathbb{Z}_N^{\ast}$ selalu ada elemen unik $b\in\mathbb{Z}_N^{\ast}$ yang memenuhi $ab=1.$ Kita notasikan elemen $b$ ini dengan $a^{-1},$ dan ia bisa dihitung secara efisien; perluasan dari algoritma GCD Euclid melakukannya dengan biaya kuadratik dalam $\operatorname{lg}(N).$ Dan dengan demikian

$$M_{a^{-1}} M_a = M_{a^{-1}a} = M_1 = \mathbb{I}.$$

Jadi, operasi $M_a$ bersifat deterministik sekaligus invertibel. Itu berarti ia digambarkan oleh matriks permutasi, dan karenanya uniter.

Sekarang mari kita pikirkan tentang vektor eigen dan nilai eigen dari operasi $M_a,$ dengan asumsi bahwa $a\in\mathbb{Z}_N^{\ast}.$ Seperti yang baru saja diargumentasikan, asumsi ini memberi tahu kita bahwa $M_a$ adalah uniter.

Ada $N$ nilai eigen dari $M_a,$ mungkin termasuk nilai eigen yang sama yang diulang beberapa kali, dan secara umum ada beberapa kebebasan dalam memilih vektor eigen yang bersesuaian — tapi kita tidak perlu mengkhawatirkan semua kemungkinan itu. Mari kita mulai sederhana dan hanya mengidentifikasi satu vektor eigen dari $M_a.$

$$\vert \psi_0 \rangle = \frac{\vert 1 \rangle + \vert a \rangle + \cdots + \vert a^{r-1} \rangle}{\sqrt{r}}$$

Bilangan $r$ adalah orde dari $a$ modulo $N,$ di sini dan di seluruh sisa pelajaran. Nilai eigen yang terkait dengan vektor eigen ini adalah $1$ karena tidak berubah saat kita kalikan dengan $a.$

$$M_a \vert \psi_0 \rangle = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert a^r \rangle}{\sqrt{r}} = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert 1 \rangle}{\sqrt{r}} = \vert \psi_0 \rangle$$

Ini terjadi karena $a^r = 1,$ jadi setiap keadaan basis standar $\vert a^k \rangle$ digeser ke $\vert a^{k+1} \rangle$ untuk $k\leq r-1,$ dan $\vert a^{r-1} \rangle$ digeser kembali ke $\vert 1\rangle.$ Secara informal, ini seperti kita sedang mengaduk $\vert \psi_0 \rangle$ perlahan, tapi ia sudah sepenuhnya teraduk sehingga tidak ada yang berubah.

Berikut adalah contoh lain dari vektor eigen $M_a.$ Yang ini lebih menarik dalam konteks pencarian orde dan estimasi fase.

$$\vert \psi_1 \rangle = \frac{\vert 1 \rangle + \omega_r^{-1} \vert a \rangle + \cdots + \omega_r^{-(r-1)}\vert a^{r-1} \rangle}{\sqrt{r}}$$

Atau, kita bisa menulis vektor ini menggunakan penjumlahan sebagai berikut.

$$\vert \psi_1 \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle$$

Di sini kita melihat bilangan kompleks $\omega_r = e^{2\pi i/r}$ muncul secara alami, karena cara kerja perkalian dengan $a$ modulo $N.$ Kali ini nilai eigen yang bersesuaian adalah $\omega_r.$ Untuk melihat ini, kita bisa menghitung terlebih dahulu sebagai berikut.

$$M_a \vert \psi_1 \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} M_a\vert a^k \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^{k+1} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-(k - 1)} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\omega_r \sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle$$

Kemudian, karena $\omega_r^{-r} = 1 = \omega_r^0$ dan $\vert a^r \rangle = \vert 1\rangle = \vert a^0\rangle,$ kita lihat bahwa

$$\frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle = \vert\psi_1\rangle,$$

jadi $M_a \vert\psi_1\rangle = \omega_r \vert\psi_1\rangle.$

Menggunakan penalaran yang sama, kita bisa mengidentifikasi pasangan vektor eigen/nilai eigen tambahan untuk $M_a.$ Untuk setiap pilihan $j\in\{0,\ldots,r-1\}$ kita punya bahwa

$$\vert \psi_j \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-jk} \vert a^k \rangle$$

adalah vektor eigen dari $M_a$ yang nilai eigen bersesuaiannya adalah $\omega_r^j.$

$$M_a \vert \psi_j \rangle = \omega_r^j \vert \psi_j \rangle$$

Ada vektor eigen lain dari $M_a,$ tapi kita tidak perlu memperhatikannya — kita akan fokus hanya pada vektor eigen $\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle$ yang baru kita identifikasi.

Pencarian orde melalui estimasi fase

Untuk menyelesaikan masalah pencarian orde bagi pilihan $a\in\mathbb{Z}_N^{\ast}$ tertentu, kita bisa menerapkan prosedur estimasi fase pada operasi $M_a.$

Untuk melakukan ini, kita perlu mengimplementasikan tidak hanya $M_a$ secara efisien dengan sirkuit kuantum, tapi juga $M_a^2,$ $M_a^4,$ $M_a^8,$ dan seterusnya, sejauh yang diperlukan untuk mendapatkan estimasi yang cukup presisi dari prosedur estimasi fase. Di sini kita akan menjelaskan bagaimana hal ini bisa dilakukan, dan kita akan mencari tahu berapa banyak presisi yang dibutuhkan nanti.

Mari mulai dengan operasi $M_a$ itu sendiri. Secara alami, karena kita bekerja dengan model sirkuit kuantum, kita akan menggunakan notasi biner untuk mengkodekan angka-angka antara $0$ dan $N-1.$ Angka terbesar yang perlu kita kodekan adalah $N-1,$ sehingga jumlah bit yang kita butuhkan adalah

$$n = \operatorname{lg}(N-1) = \lfloor \log(N-1) \rfloor + 1.$$

Sebagai contoh, jika $N = 21$ maka $n = \operatorname{lg}(N-1) = 5.$ Berikut tampilan pengkodean elemen $\mathbb{Z}_{21}$ sebagai string biner dengan panjang $5.$

$$\begin{gathered} 0 \mapsto 00000\\[1mm] 1 \mapsto 00001\\[1mm] \vdots\\[1mm] 20 \mapsto 10100 \end{gathered}$$

Dan sekarang, berikut definisi tepat bagaimana $M_a$ didefinisikan sebagai operasi $n$-qubit.

$$M_a \vert x\rangle = \begin{cases} \vert ax \; (\textrm{mod}\;N)\rangle & 0\leq x < N\\[1mm] \vert x\rangle & N\leq x < 2^n \end{cases}$$

Intinya adalah meskipun kita hanya peduli bagaimana $M_a$ bekerja untuk $\vert 0\rangle,\ldots,\vert N-1\rangle,$ kita tetap harus menentukan bagaimana cara kerjanya untuk $2^n - N$ keadaan basis standar yang tersisa — dan kita perlu melakukan ini dengan cara yang tetap menghasilkan operasi uniter. Mendefinisikan $M_a$ sehingga tidak melakukan apa-apa pada keadaan basis standar yang tersisa berhasil mencapai ini.

Dengan menggunakan algoritma perkalian dan pembagian bilangan bulat yang dibahas di pelajaran sebelumnya, bersama dengan metodologi untuk implementasi reversibel tanpa sampah, kita bisa membangun sirkuit kuantum yang menjalankan $M_a,$ untuk pilihan $a\in\mathbb{Z}_N^{\ast}$ apapun, dengan biaya $O(n^2).$ Berikut satu cara untuk melakukan ini.

1. Bangun sirkuit untuk menjalankan operasi

   $$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \vert y \oplus f_a(x)\rangle$$

   di mana

   $$f_a(x) = \begin{cases} ax \; (\textrm{mod}\;N) & 0\leq x < N\\[1mm] x & N\leq x < 2^n \end{cases}$$

   menggunakan metode yang dijelaskan di pelajaran sebelumnya. Ini memberi kita sirkuit berukuran $O(n^2).$

2. Tukar dua sistem $n$-qubit menggunakan $n$ gerbang swap untuk menukar qubit-qubit secara individual.

3. Mirip dengan langkah pertama, bangun sirkuit untuk operasi

   $$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \bigl\vert y \oplus f_{a^{-1}}(x)\bigr\rangle$$

   di mana $a^{-1}$ adalah invers dari $a$ di $\mathbb{Z}_N^{\ast}.$

Dengan menginisialisasi $n$ qubit bawah dan menggabungkan tiga langkah tersebut, kita mendapatkan transformasi berikut:

$$\vert x \rangle \vert 0^n \rangle \stackrel{\text{step 1}}{\mapsto} \vert x \rangle \vert f_a(x)\rangle \stackrel{\text{step 2}}{\mapsto} \vert f_a(x)\rangle \vert x \rangle \stackrel{\text{step 3}}{\mapsto} \vert f_a(x)\rangle \bigl\vert x \oplus f_{a^{-1}}(f_a(x)) \bigr\rangle = \vert f_a(x)\rangle\vert 0^n \rangle$$

Metode ini memerlukan qubit workspace, tapi qubit tersebut dikembalikan ke keadaan terinisialisasi di akhir, yang memungkinkan kita menggunakan sirkuit ini untuk estimasi fase. Total biaya sirkuit yang kita dapatkan adalah $O(n^2).$

Untuk menjalankan $M_a^2,$ $M_a^4,$ $M_a^8,$ dan seterusnya, kita bisa menggunakan metode yang sama persis, kecuali kita mengganti $a$ dengan $a^2,$ $a^4,$ $a^8,$ dan seterusnya, sebagai elemen $\mathbb{Z}_N^{\ast}.$ Artinya, untuk pangkat $k$ apapun yang kita pilih, kita bisa membuat sirkuit untuk $M_a^k$ bukan dengan mengiterasi sirkuit untuk $M_a$ sebanyak $k$ kali, melainkan dengan menghitung $b = a^k \in \mathbb{Z}_N^{\ast}$ kemudian menggunakan sirkuit untuk $M_b.$

Penghitungan pangkat $a^k \in \mathbb{Z}_N$ adalah masalah pemangkatan modular yang disebutkan di pelajaran sebelumnya. Penghitungan ini bisa dilakukan secara klasik, menggunakan algoritma pemangkatan modular yang disebutkan di pelajaran sebelumnya (sering disebut algoritma pangkat dalam teori bilangan komputasional). Sebenarnya, kita hanya membutuhkan pangkat $a$ yang merupakan pangkat-2, yaitu $a^2, a^4, \ldots a^{2^{m-1}} \in \mathbb{Z}_N^{\ast},$ dan kita bisa mendapatkan pangkat-pangkat ini dengan mengkuadratkan secara iteratif sebanyak $m-1$ kali. Setiap pengkuadratan bisa dilakukan dengan sirkuit Boolean berukuran $O(n^2).$

Pada dasarnya, apa yang efektif kita lakukan di sini adalah mengalihkan masalah pengulangan $M_a$ hingga $2^{m-1}$ kali ke penghitungan klasik yang efisien. Dan beruntung sekali hal ini memungkinkan! Untuk pilihan sirkuit kuantum yang sembarang dalam masalah estimasi fase, hal ini kemungkinan besar tidak mungkin dilakukan — dan dalam kasus itu biaya yang dihasilkan untuk estimasi fase tumbuh secara eksponensial terhadap jumlah qubit kontrol $m.$

Solusi dengan vektor eigen yang mudah didapat

Untuk memahami bagaimana kita bisa menyelesaikan masalah pencarian orde menggunakan estimasi fase, mari mulai dengan mengasumsikan bahwa kita menjalankan prosedur estimasi fase pada operasi $M_a$ menggunakan vektor eigen $\vert\psi_1\rangle.$ Mendapatkan vektor eigen ini ternyata tidak mudah, jadi ini bukan akhir dari cerita — tapi sangat membantu untuk mulai dari sini.

Nilai eigen dari $M_a$ yang bersesuaian dengan vektor eigen $\vert \psi_1\rangle$ adalah

$$\omega_r = e^{2\pi i \frac{1}{r}}.$$

Yaitu, $\omega_r = e^{2\pi i \theta}$ untuk $\theta = 1/r.$ Jadi, jika kita menjalankan prosedur estimasi fase pada $M_a$ menggunakan vektor eigen $\vert\psi_1\rangle,$ kita akan mendapatkan aproksimasi dari $1/r.$ Dengan menghitung kebalikannya kita akan bisa mengetahui $r$ — asalkan aproksimasi kita cukup baik.

Lebih detailnya, ketika kita menjalankan prosedur estimasi fase menggunakan $m$ qubit kontrol, yang kita dapatkan adalah sebuah angka $y\in\{0,\ldots,2^m-1\}.$ Kita kemudian mengambil $y/2^m$ sebagai tebakan untuk $\theta,$ yang dalam kasus ini adalah $1/r.$ Untuk mencari tahu apa itu $r$ dari aproksimasi ini, hal yang alami adalah menghitung kebalikan dari aproksimasi kita dan membulatkan ke bilangan bulat terdekat.

$$\left\lfloor \frac{2^m}{y} + \frac{1}{2} \right\rfloor$$

Sebagai contoh, misalkan $r = 6$ dan kita menjalankan estimasi fase pada $M_a$ dengan vektor eigen $\vert\psi_1\rangle$ menggunakan $m = 5$ bit kontrol. Aproksimasi $5$-bit terbaik untuk $1/r = 1/6$ adalah $5/32,$ dan kita punya peluang yang cukup besar (sekitar $68\%$ dalam kasus ini) untuk mendapatkan hasil $y=5$ dari estimasi fase. Kita punya

$$\frac{2^m}{y} = \frac{32}{5} = 6.4,$$

dan pembulatan ke bilangan bulat terdekat menghasilkan $6,$ yang merupakan jawaban yang benar.

Di sisi lain, jika kita tidak menggunakan cukup presisi, kita mungkin tidak mendapatkan jawaban yang benar. Misalnya, jika kita mengambil $m = 4$ qubit kontrol dalam estimasi fase, kita mungkin mendapatkan aproksimasi $4$-bit terbaik untuk $1/r = 1/6,$ yaitu $3/16.$ Mengambil kebalikannya menghasilkan

$$\frac{2^m}{y} = \frac{16}{3} = 5.333 \cdots$$

dan pembulatan ke bilangan bulat terdekat menghasilkan jawaban yang salah yaitu $5.$

Jadi berapa banyak presisi yang kita butuhkan untuk mendapatkan jawaban yang benar? Kita tahu bahwa orde $r$ adalah bilangan bulat, dan secara intuitif apa yang kita butuhkan adalah presisi yang cukup untuk membedakan $1/r$ dari kemungkinan-kemungkinan terdekat, termasuk $1/(r+1)$ dan $1/(r-1).$ Angka yang paling dekat dengan $1/r$ yang perlu kita waspadai adalah $1/(r+1),$ dan jarak antara dua angka ini adalah

$$\frac{1}{r} - \frac{1}{r+1} = \frac{1}{r(r+1)}.$$

Jadi, jika kita ingin memastikan kita tidak salah mengira $1/r$ dengan $1/(r+1),$ cukup menggunakan presisi yang memastikan aproksimasi terbaik $y/2^m$ ke $1/r$ lebih dekat ke $1/r$ daripada ke $1/(r+1).$ Jika kita menggunakan presisi yang cukup sehingga

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert < \frac{1}{2 r (r+1)},$$

sehingga kesalahannya kurang dari setengah jarak antara $1/r$ dan $1/(r+1),$ maka $y/2^m$ akan lebih dekat ke $1/r$ daripada ke kemungkinan lain manapun, termasuk $1/(r+1)$ dan $1/(r-1).$

Kita bisa memverifikasi ini sebagai berikut. Misalkan

$$\frac{y}{2^m} = \frac{1}{r} + \varepsilon$$

untuk $\varepsilon$ yang memenuhi

$$\vert\varepsilon\vert < \frac{1}{2 r (r+1)}.$$

Ketika kita mengambil kebalikannya kita mendapatkan

$$\frac{2^m}{y} = \frac{1}{\frac{1}{r} + \varepsilon} = \frac{r}{1+\varepsilon r} = r - \frac{\varepsilon r^2}{1+\varepsilon r}.$$

Dengan memaksimalkan di pembilang dan meminimalkan di penyebut, kita bisa membatasi seberapa jauh kita dari $r$ sebagai berikut.

$$\left\vert \frac{\varepsilon r^2}{1+\varepsilon r} \right\vert \leq \frac{ \frac{r^2}{2 r(r+1)}}{1 - \frac{r}{2r(r+1)}} = \frac{r}{2 r + 1} < \frac{1}{2}$$

Kita kurang dari $1/2$ jauhnya dari $r,$ jadi seperti yang diharapkan kita akan mendapatkan $r$ saat kita membulatkan.

Sayangnya, karena kita belum tahu apa itu $r,$ kita tidak bisa menggunakannya untuk memberi tahu kita berapa banyak akurasi yang dibutuhkan. Yang bisa kita lakukan adalah menggunakan fakta bahwa $r$ harus lebih kecil dari $N$ untuk memastikan kita menggunakan presisi yang cukup. Khususnya, jika kita menggunakan akurasi yang cukup untuk menjamin bahwa aproksimasi terbaik $y/2^m$ ke $1/r$ memenuhi

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert \leq \frac{1}{2N^2},$$

maka kita akan memiliki presisi yang cukup untuk menentukan $r$ dengan benar saat kita mengambil kebalikannya. Mengambil $m = 2\operatorname{lg}(N)+1$ memastikan kita memiliki peluang tinggi untuk mendapatkan estimasi dengan presisi ini menggunakan metode yang dijelaskan sebelumnya. (Mengambil $m = 2\operatorname{lg}(N)$ sudah cukup jika kita nyaman dengan batas bawah 40% pada probabilitas keberhasilan.)

Solusi umum

Seperti yang baru saja kita lihat, jika kita memiliki vektor eigen $\vert \psi_1 \rangle$ dari $M_a,$ kita bisa mengetahui $r$ melalui estimasi fase, selama kita menggunakan cukup qubit kontrol untuk melakukan ini dengan presisi yang memadai. Sayangnya, tidak mudah untuk mendapatkan vektor eigen $\vert\psi_1\rangle,$ jadi kita perlu mencari cara untuk melanjutkan.

Mari sejenak misalkan kita melanjutkan seperti di atas, kecuali dengan vektor eigen $\vert\psi_k\rangle$ sebagai pengganti $\vert\psi_1\rangle,$ untuk pilihan $k\in\{0,\ldots,r-1\}$ apapun yang ingin kita pertimbangkan. Hasil yang kita dapatkan dari prosedur estimasi fase akan berupa aproksimasi

$$\frac{y}{2^m} \approx \frac{k}{r}.$$

Dengan asumsi kita tidak mengetahui $k$ maupun $r,$ ini mungkin atau mungkin tidak memungkinkan kita mengidentifikasi $r.$ Misalnya, jika $k = 0$ kita akan mendapatkan aproksimasi $y/2^m$ ke $0,$ yang sayangnya tidak memberi kita informasi apapun. Namun, ini adalah kasus yang tidak biasa; untuk nilai $k$ lainnya, kita setidaknya akan bisa mempelajari sesuatu tentang $r.$

Kita bisa menggunakan algoritma yang dikenal sebagai algoritma pecahan berlanjut untuk mengubah aproksimasi $y/2^m$ kita menjadi pecahan-pecahan terdekat — termasuk $k/r$ jika aproksimasi tersebut cukup baik. Kita tidak akan menjelaskan algoritma pecahan berlanjut di sini. Sebagai gantinya, berikut pernyataan fakta yang sudah diketahui tentang algoritma ini.

Fakta

Diberikan bilangan bulat $N\geq 2$ dan bilangan real $\alpha\in(0,1),$ ada paling banyak satu pilihan bilangan bulat $u,v\in\{0,\ldots,N-1\}$ dengan $v\neq 0$ dan $\gcd(u,v)=1$ yang memenuhi $\vert \alpha - u/v\vert < \frac{1}{2N^2}.$ Diberikan $\alpha$ dan $N,$ algoritma pecahan berlanjut menemukan $u$ dan $v,$ atau melaporkan bahwa keduanya tidak ada. Algoritma ini bisa diimplementasikan sebagai sirkuit Boolean berukuran $O((\operatorname{lg}(N))^3).$

Jika kita memiliki aproksimasi yang sangat dekat $y/2^m$ ke $k/r,$ dan kita menjalankan algoritma pecahan berlanjut untuk $N$ dan $\alpha = y/2^m,$ kita akan mendapatkan $u$ dan $v,$ seperti yang dijelaskan dalam fakta tersebut. Sebuah analisis dari fakta tersebut memungkinkan kita menyimpulkan bahwa

$$\frac{u}{v} = \frac{k}{r}.$$

Perhatikan khususnya bahwa kita tidak harus bisa mengetahui $k$ dan $r,$ kita hanya mengetahui $k/r$ dalam bentuk paling sederhana.

Misalnya, dan seperti yang sudah kita perhatikan, kita tidak akan mendapatkan informasi apapun dari $k=0.$ Tapi itulah satu-satunya nilai $k$ di mana hal itu terjadi. Ketika $k$ bukan nol, $k$ mungkin memiliki faktor persekutuan dengan $r,$ tapi angka $v$ yang kita dapatkan dari algoritma pecahan berlanjut setidaknya harus membagi $r.$

Mungkin tidak langsung jelas, tapi memang benar bahwa jika kita bisa mengetahui $u$ dan $v$ untuk $u/v = k/r$ dengan $k\in\{0,\ldots,r-1\}$ dipilih secara acak seragam, maka kemungkinan besar kita bisa memulihkan $r$ hanya setelah beberapa sampel. Khususnya, jika tebakan kita untuk $r$ adalah kelipatan persekutuan terkecil dari semua nilai penyebut $v$ yang kita amati, kita akan benar dengan probabilitas tinggi. Secara intuitif, beberapa nilai $k$ tidak bagus karena memiliki faktor persekutuan dengan $r,$ dan faktor-faktor persekutuan tersebut tersembunyi dari kita saat kita mengetahui $u$ dan $v.$ Tapi pilihan $k$ yang acak kecil kemungkinannya menyembunyikan faktor-faktor $r$ untuk waktu lama, dan probabilitas kita gagal menebak $r$ dengan benar melalui pengambilan kelipatan persekutuan terkecil dari penyebut yang kita amati turun secara eksponensial terhadap jumlah sampel.

Masih tersisa masalah bagaimana cara kita mendapatkan vektor eigen $\vert\psi_k\rangle$ dari $M_a$ untuk menjalankan prosedur estimasi fase. Ternyata, kita sebenarnya tidak perlu membuatnya!

Yang akan kita lakukan sebagai gantinya adalah menjalankan prosedur estimasi fase pada keadaan $\vert 1\rangle,$ yang kita maksudkan sebagai pengkodean biner $n$-bit dari angka $1,$ sebagai pengganti vektor eigen $\vert\psi\rangle$ dari $M_a.$ Sejauh ini, kita hanya membahas menjalankan prosedur estimasi fase pada vektor eigen tertentu, tapi tidak ada yang mencegah kita menjalankan prosedur pada keadaan input yang bukan vektor eigen dari $M_a,$ dan itulah yang kita lakukan di sini dengan keadaan $\vert 1\rangle.$ (Ini bukan vektor eigen dari $M_a$ kecuali $a=1,$ yang bukan pilihan yang akan kita minati.)

Alasan memilih keadaan $\vert 1\rangle$ sebagai pengganti vektor eigen dari $M_a$ adalah persamaan berikut ini benar.

$$\vert 1\rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle$$

Salah satu cara untuk memverifikasi persamaan ini adalah dengan membandingkan hasil kali dalam dari kedua sisi dengan setiap keadaan basis standar, menggunakan rumus-rumus yang disebutkan sebelumnya dalam pelajaran untuk membantu mengevaluasi hasil untuk sisi kanan. Akibatnya, kita akan mendapatkan hasil pengukuran yang persis sama seolah-olah kita telah memilih $k\in\{0,\ldots,r-1\}$ secara acak seragam dan menggunakan $\vert\psi_k\rangle$ sebagai vektor eigen.

Lebih detailnya, mari bayangkan kita menjalankan prosedur estimasi fase dengan keadaan $\vert 1\rangle$ sebagai pengganti salah satu vektor eigen $\vert\psi_k\rangle.$ Setelah transformasi Fourier kuantum invers dilakukan, ini meninggalkan kita dengan keadaan

$$\frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle \vert \gamma_k\rangle,$$

di mana

$$\vert\gamma_k\rangle = \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (k/r - y/2^m)} \vert y\rangle.$$

Vektor $\vert\gamma_k\rangle$ merepresentasikan keadaan dari $m$ qubit teratas setelah invers transformasi Fourier kuantum dilakukan pada qubit-qubit tersebut.

Jadi, berkat fakta bahwa $\{\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle\}$ adalah himpunan ortonormal, kita menemukan bahwa pengukuran $m$ qubit teratas menghasilkan aproksimasi $y/2^m$ ke nilai $k/r$ di mana $k\in\{0,\ldots,r-1\}$ dipilih secara acak seragam. Seperti yang sudah kita bahas, ini memungkinkan kita mengetahui $r$ dengan tingkat kepercayaan yang tinggi setelah beberapa kali menjalankan secara independen, yang merupakan tujuan kita.

Total biaya

Biaya untuk mengimplementasikan setiap controlled-unitary $M_a^k$ adalah $O(n^2).$ Ada $m$ operasi controlled-unitary, dan kita punya $m = O(n),$ sehingga total biaya untuk operasi controlled-unitary adalah $O(n^3).$ Selain itu, kita memiliki $m$ gerbang Hadamard (yang berkontribusi $O(n)$ pada biaya), dan transformasi Fourier kuantum invers berkontribusi $O(n^2)$ pada biaya. Jadi, biaya operasi controlled-unitary mendominasi biaya keseluruhan prosedur — yang karenanya adalah $O(n^3).$

Selain sirkuit kuantum itu sendiri, ada beberapa penghitungan klasik yang perlu dilakukan di sepanjang jalan. Ini termasuk menghitung pangkat $a^k$ di $\mathbb{Z}_N$ untuk $k = 2, 4, 8, \ldots, 2^{m-1},$ yang diperlukan untuk membuat gerbang controlled-unitary, serta algoritma pecahan berlanjut yang mengubah aproksimasi $\theta$ menjadi pecahan. Penghitungan-penghitungan ini bisa dilakukan oleh sirkuit Boolean dengan total biaya $O(n^3).$

Seperti biasanya, semua batas ini bisa diperbaiki menggunakan algoritma yang asimtotis lebih cepat; batas-batas ini mengasumsikan kita menggunakan algoritma standar untuk operasi aritmetika dasar.

Pemfaktoran melalui pencarian orde

Hal terakhir yang perlu kita bahas adalah bagaimana menyelesaikan masalah pencarian orde membantu kita untuk memfaktorkan. Bagian ini sepenuhnya klasik — tidak ada kaitannya secara khusus dengan komputasi kuantum.

Berikut ide dasarnya. Kita ingin memfaktorkan angka $N,$ dan kita bisa melakukan ini secara rekursif. Secara khusus, kita bisa fokus pada tugas memecah $N,$ yang berarti menemukan dua bilangan bulat $b,c\geq 2$ di mana $N = bc.$ Ini tidak mungkin jika $N$ adalah bilangan prima, tapi kita bisa secara efisien menguji apakah $N$ adalah prima menggunakan algoritma uji keprimaan terlebih dahulu, dan jika $N$ bukan prima kita akan mencoba memecahnya. Setelah kita memecah $N,$ kita bisa sederhananya merekursi pada $b$ dan $c$ sampai semua faktor kita prima dan kita mendapatkan pemfaktoran prima dari $N.$

Memecah bilangan bulat genap itu mudah: kita cukup menghasilkan $2$ dan $N/2.$

Memecah pangkat sempurna juga mudah, yaitu angka berbentuk $N = s^j$ untuk bilangan bulat $s,j\geq 2,$ hanya dengan mengaproksimasi akar-akar $N^{1/2},$ $N^{1/3},$ $N^{1/4},$ dan seterusnya, serta memeriksa bilangan bulat terdekat sebagai kandidat untuk $s.$ Kita tidak perlu melanjutkan lebih dari $\log(N)$ langkah dalam urutan ini, karena pada titik itu akarnya turun di bawah $2$ dan tidak akan mengungkapkan kandidat tambahan.

Bagus bahwa kita bisa melakukan kedua hal ini karena pencarian orde tidak akan membantu kita memfaktorkan bilangan genap atau pangkat prima, di mana angka $s$ kebetulan prima. Jika $N$ ganjil dan bukan pangkat prima, namun demikian, pencarian orde memungkinkan kita memecah $N.$

Algoritma probabilistik untuk memecah bilangan bulat ganjil komposit N yang bukan pangkat prima

1. Pilih secara acak $a\in\{2,\ldots,N-1\}.$

2. Hitung $d=\gcd(a,N).$

3. Jika $d > 1$ maka hasilkan $b = d$ dan $c = N/d$ lalu berhenti. Jika tidak lanjutkan ke langkah berikutnya mengetahui bahwa $a\in\mathbb{Z}_N^{\ast}.$

4. Misalkan $r$ adalah orde dari $a$ modulo $N.$ (Di sinilah kita membutuhkan pencarian orde.)

5. Jika $r$ genap:

   5.1 Hitung $x = a^{r/2} - 1$ modulo $N$
   5.2 Hitung $d = \gcd(x,N).$
   5.3 Jika $d>1$ maka hasilkan $b=d$ dan $c = N/d$ lalu berhenti.

6. Jika titik ini tercapai, algoritma gagal menemukan faktor dari $N.$

Satu kali jalannya algoritma ini mungkin gagal menemukan faktor dari $N.$ Secara khusus, ini terjadi dalam dua situasi:

• Orde dari $a$ modulo $N$ adalah ganjil.
• Orde dari $a$ modulo $N$ adalah genap dan $\gcd\bigl(a^{r/2} - 1, N\bigr) = 1.$

Menggunakan teori bilangan dasar bisa dibuktikan bahwa, untuk pilihan acak $a,$ dengan probabilitas setidaknya $1/2$ tidak satupun dari kejadian ini terjadi. Faktanya, probabilitas bahwa salah satu kejadian terjadi adalah paling banyak $2^{-(m-1)}$ untuk $m$ adalah jumlah faktor prima berbeda dari $N,$ itulah mengapa asumsi bahwa $N$ bukan pangkat prima diperlukan. (Asumsi bahwa $N$ ganjil juga diperlukan agar fakta ini benar.)

Ini berarti setiap kali menjalankan memiliki setidaknya 50% peluang untuk memecah $N.$ Oleh karena itu, jika kita menjalankan algoritma sebanyak $t$ kali, memilih $a$ secara acak setiap kali, kita akan berhasil memecah $N$ dengan probabilitas setidaknya $1 - 2^{-t}.$

Ide dasar di balik algoritma ini adalah sebagai berikut. Jika kita memiliki pilihan $a$ di mana orde $r$ dari $a$ modulo $N$ adalah genap, maka $r/2$ adalah bilangan bulat dan kita bisa mempertimbangkan bilangan-bilangan

$$a^{r/2} - 1\; (\textrm{mod}\; N) \quad \text{and} \quad a^{r/2} + 1\; (\textrm{mod}\; N).$$

Menggunakan rumus $Z^2 - 1 = (Z+1)(Z-1),$ kita menyimpulkan bahwa

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr) = a^r - 1.$$

Sekarang, kita tahu bahwa $a^r \; (\textrm{mod}\; N) = 1$ berdasarkan definisi orde — yang merupakan cara lain mengatakan bahwa $N$ habis membagi $a^r - 1.$ Itu berarti $N$ habis membagi hasil kali

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr).$$

Agar ini benar, semua faktor prima dari $N$ harus juga merupakan faktor prima dari $a^{r/2} - 1$ atau $a^{r/2} + 1$ (atau keduanya) — dan untuk pilihan acak $a$ ternyata kecil kemungkinannya semua faktor prima dari $N$ membagi salah satu suku dan tidak satupun membagi suku yang lain. Jika tidak, selama beberapa faktor prima dari $N$ membagi suku pertama dan beberapa membagi suku kedua, kita akan bisa menemukan faktor tak-trivial dari $N$ dengan menghitung GCD dengan suku pertama.