Algoritma Shor

Sekarang kita akan beralih perhatian kepada masalah pemfaktoran integer, dan lihat bagaimana ia boleh diselesaikan dengan cekap pada komputer kuantum menggunakan penganggaran fasa. Algoritma yang akan kita peroleh ialah algoritma Shor untuk pemfaktoran integer. Shor tidak menggambarkan algoritmanya khususnya dalam sebutan penganggaran fasa, tetapi itu adalah cara yang semula jadi dan intuitif untuk menerangkan cara ia berfungsi.

Kita akan mulakan dengan membincangkan masalah perantaraan yang dikenali sebagai masalah pencarian order dan melihat bagaimana penganggaran fasa memberikan penyelesaian kepada masalah ini. Kemudian kita akan lihat bagaimana penyelesaian yang cekap kepada masalah pencarian order memberi kita penyelesaian yang cekap kepada masalah pemfaktoran integer. (Apabila penyelesaian kepada satu masalah memberikan penyelesaian kepada masalah lain seperti ini, kita katakan masalah kedua diturunkan kepada yang pertama — jadi dalam kes ini kita menurunkan pemfaktoran integer kepada pencarian order.) Bahagian kedua algoritma Shor ini langsung tidak menggunakan pengiraan kuantum; ia sepenuhnya klasik. Pengiraan kuantum hanya diperlukan untuk menyelesaikan pencarian order.

Masalah pencarian order

Beberapa teori nombor asas

Untuk menerangkan masalah pencarian order dan cara ia boleh diselesaikan menggunakan penganggaran fasa, adalah berguna untuk bermula dengan beberapa konsep teori nombor asas, dan memperkenalkan beberapa notasi yang berguna sepanjang jalan.

Untuk bermula, bagi sebarang integer positif $N,$ takrifkan set $\mathbb{Z}_N$ seperti berikut.

$$\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 set nombor, tetapi kita boleh memikirkannya sebagai lebih daripada sekadar set. Khususnya, kita boleh memikirkan operasi aritmetik pada $\mathbb{Z}_N$ seperti penambahan dan pendaraban — dan jika kita bersetuju untuk sentiasa mengambil jawapan kita modulo $N$ (iaitu, bahagikan dengan $N$ dan ambil bakinya sebagai hasil), kita akan sentiasa kekal dalam set ini apabila melakukan operasi-operasi ini. Dua operasi khusus penambahan dan pendaraban, kedua-duanya diambil modulo $N,$ menjadikan $\mathbb{Z}_N$ sebagai sebuah gelanggang, yang merupakan jenis objek yang sangat penting dalam algebra.

Sebagai contoh, $3$ dan $5$ adalah elemen $\mathbb{Z}_7,$ dan jika kita mendarabkan mereka bersama kita mendapat $3\cdot 5 = 15,$ yang meninggalkan baki $1$ apabila dibahagikan dengan $7.$ Kadangkala kita ungkapkan ini seperti berikut.

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

Tetapi kita juga boleh menulis $3 \cdot 5 = 1,$ dengan syarat telah dijelaskan bahawa kita bekerja dalam $\mathbb{Z}_7,$ hanya untuk memastikan notasi kita semudah mungkin.

Sebagai contoh, berikut adalah jadual penambahan dan pendaraban 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}$$

Antara $N$ elemen $\mathbb{Z}_N,$ elemen $a\in\mathbb{Z}_N$ yang memenuhi $\gcd(a,N) = 1$ adalah istimewa. Kerap kali set yang mengandungi elemen-elemen ini dilambangkan dengan tanda bintang seperti berikut.

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

Jika kita menumpukan perhatian pada operasi pendaraban, set $\mathbb{Z}_N^{\ast}$ membentuk sebuah kumpulan — khususnya kumpulan abelian — yang merupakan satu lagi jenis objek penting dalam algebra. Ia adalah fakta asas tentang set-set ini (dan kumpulan terhingga secara umum), bahawa jika kita memilih mana-mana elemen $a\in\mathbb{Z}_N^{\ast}$ dan mendarabkan $a$ berulang kali kepada dirinya sendiri, kita akan sentiasa akhirnya mendapat nombor $1.$

Sebagai contoh pertama, mari kita ambil $N=6.$ Kita ada bahawa $5\in\mathbb{Z}_6^{\ast}$ kerana $\gcd(5,6) = 1,$ dan jika kita mendarabkan $5$ kepada dirinya sendiri kita mendapat $1,$ seperti yang disahkan oleh jadual di atas.

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

Sebagai contoh kedua, mari kita ambil $N = 21.$ Jika kita melalui nombor dari $0$ hingga $20,$ yang mempunyai GCD sama dengan $1$ dengan $21$ adalah seperti berikut.

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

Bagi setiap elemen ini, adalah mungkin untuk menaikkan nombor itu kepada kuasa integer positif untuk mendapat $1.$ Berikut adalah kuasa terkecil yang berfungsi:

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

Sudah tentu kita bekerja dalam $\mathbb{Z}_{21}$ untuk semua persamaan ini, yang tidak kita tulis — kita anggap ia tersirat untuk mengelakkan kerumitan. Kita akan terus berbuat demikian sepanjang sisa pelajaran ini.

Pernyataan masalah dan hubungan dengan penganggaran fasa

Sekarang kita boleh menyatakan masalah pencarian order.

Pencarian order

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

Sebagai alternatif, dalam sebutan notasi yang baru kita perkenalkan di atas, kita diberi $a \in \mathbb{Z}_N^{\ast},$ dan kita mencari integer positif terkecil $r$ supaya $a^r = 1.$ Nombor $r$ ini dipanggil order bagi $a$ modulo $N.$

Untuk menghubungkan masalah pencarian order dengan penganggaran fasa, mari kita fikirkan tentang operasi yang ditakrifkan pada sistem yang keadaan klasiknya berpadanan dengan $\mathbb{Z}_N,$ di mana kita mendarab 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 lebih jelas, kita melakukan pendaraban dalam $\mathbb{Z}_N,$ jadi ia tersirat bahawa kita mengambil hasil darab modulo $N$ di dalam ket pada sebelah kanan persamaan.

Sebagai contoh, jika kita ambil $N = 15$ dan $a=2,$ maka tindakan $M_2$ pada asas piawai $\{\vert 0\rangle,\ldots,\vert 14\rangle\}$ adalah seperti 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 unitary dengan syarat $\gcd(a,N)=1;$ ia mengocok elemen asas piawai $\{\vert 0\rangle,\ldots,\vert N-1\rangle\},$ jadi sebagai matriks ia adalah matriks permutasi. Jelas dari takrifannya bahawa operasi ini adalah deterministik, dan cara mudah untuk melihat bahawa ia boleh dinyahbalik adalah dengan memikirkan order $r$ bagi $a$ modulo $N,$ dan menyedari bahawa penyongsangan $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 penyongsangan yang tidak memerlukan sebarang pengetahuan tentang $r$ (yang, setelah semua, adalah apa yang kita cuba kira). Bagi setiap elemen $a\in\mathbb{Z}_N^{\ast}$ sentiasa ada elemen unik $b\in\mathbb{Z}_N^{\ast}$ yang memenuhi $ab=1.$ Kita tandakan elemen $b$ ini dengan $a^{-1},$ dan ia boleh dikira dengan cekap; sambungan algoritma GCD Euclid melakukannya dengan kos kuadratik dalam $\operatorname{lg}(N).$ Dan dengan itu

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

Jadi, operasi $M_a$ adalah deterministik dan boleh dinyahbalik. Ini bermakna ia diterangkan oleh matriks permutasi, dan oleh itu adalah unitary.

Sekarang mari kita fikirkan tentang vektor eigen dan nilai eigen operasi $M_a,$ dengan mengandaikan bahawa $a\in\mathbb{Z}_N^{\ast}.$ Seperti yang baru sahaja dihujahkan, andaian ini memberitahu kita bahawa $M_a$ adalah unitary.

Terdapat $N$ nilai eigen $M_a,$ mungkin termasuk nilai eigen yang sama berulang beberapa kali, dan secara umum ada kebebasan dalam memilih vektor eigen yang sepadan — tetapi kita tidak perlu risau tentang semua kemungkinan. Mari kita mulakan dengan mudah dan kenalpasti hanya satu vektor eigen $M_a.$

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

Nombor $r$ adalah order bagi $a$ modulo $N,$ di sini dan sepanjang sisa pelajaran ini. Nilai eigen yang berkaitan dengan vektor eigen ini adalah $1$ kerana ia tidak berubah apabila kita mendarab 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 berlaku kerana $a^r = 1,$ jadi setiap keadaan asas piawai $\vert a^k \rangle$ dialihkan ke $\vert a^{k+1} \rangle$ untuk $k\leq r-1,$ dan $\vert a^{r-1} \rangle$ dialihkan kembali ke $\vert 1\rangle.$ Secara kasarnya, ia seperti kita mengacau $\vert \psi_0 \rangle$ perlahan-lahan, tetapi ia sudah sepenuhnya teracau jadi tiada apa yang berubah.

Berikut adalah contoh lain vektor eigen $M_a.$ Yang ini lebih menarik dalam konteks pencarian order dan penganggaran fasa.

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

Sebagai alternatif, kita boleh menulis vektor ini menggunakan hasil tambah seperti 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 nombor kompleks $\omega_r = e^{2\pi i/r}$ muncul secara semula jadi, disebabkan cara pendaraban dengan $a$ berfungsi modulo $N.$ Kali ini nilai eigen yang sepadan adalah $\omega_r.$ Untuk melihat ini, kita boleh mengira seperti 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, kerana $\omega_r^{-r} = 1 = \omega_r^0$ dan $\vert a^r \rangle = \vert 1\rangle = \vert a^0\rangle,$ kita lihat bahawa

$$\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 penaakulan yang sama, kita boleh mengenal pasti pasangan vektor eigen/nilai eigen tambahan untuk $M_a.$ Bagi sebarang pilihan $j\in\{0,\ldots,r-1\}$ kita ada bahawa

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

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

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

Terdapat vektor eigen lain bagi $M_a,$ tetapi kita tidak perlu memikirkannya — kita akan fokus semata-mata pada vektor eigen $\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle$ yang baru kita kenalpasti.

Pencarian peringkat melalui anggaran fasa

Untuk menyelesaikan masalah pencarian peringkat bagi pilihan $a\in\mathbb{Z}_N^{\ast}$ yang diberikan, kita boleh menggunakan prosedur anggaran fasa ke atas operasi $M_a.$

Untuk melakukan ini, kita perlu melaksanakan bukan sahaja $M_a$ dengan cekap menggunakan Circuit kuantum, tetapi juga $M_a^2,$ $M_a^4,$ $M_a^8,$ dan seterusnya, sejauh yang diperlukan untuk mendapatkan anggaran yang cukup tepat daripada prosedur anggaran fasa. Di sini kita akan terangkan cara ini boleh dilakukan, dan kita akan menentukan dengan tepat berapa banyak ketepatan yang diperlukan kemudian.

Mari kita mulakan dengan operasi $M_a$ itu sendiri. Secara semula jadi, kerana kita bekerja dengan model Circuit kuantum, kita akan menggunakan notasi perduaan untuk mengekod nombor antara $0$ dan $N-1.$ Nombor terbesar yang perlu kita ekodkan ialah $N-1,$ jadi bilangan bit yang diperlukan ialah

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

Sebagai contoh, jika $N = 21$ kita dapat $n = \operatorname{lg}(N-1) = 5.$ Ini rupa pengekodkan elemen $\mathbb{Z}_{21}$ sebagai rentetan perduaan panjang $5.$

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

Dan kini, ini definisi tepat bagaimana $M_a$ ditakrifkan 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 ialah walaupun kita hanya peduli tentang cara $M_a$ berfungsi untuk $\vert 0\rangle,\ldots,\vert N-1\rangle,$ kita memang perlu menentukan cara ia berfungsi untuk baki $2^n - N$ keadaan asas piawai — dan kita perlu melakukan ini dengan cara yang masih memberikan operasi unitari. Dengan menakrifkan $M_a$ supaya ia tidak melakukan apa-apa kepada keadaan asas piawai yang selebihnya, matlamat ini tercapai.

Menggunakan algoritma untuk pendaraban integer dan pembahagian yang dibincangkan dalam pelajaran sebelumnya, bersama-sama dengan metodologi untuk pelaksanaan boleh-balik bebas-sampah bagi algoritma tersebut, kita boleh membina Circuit kuantum yang menjalankan $M_a,$ untuk sebarang pilihan $a\in\mathbb{Z}_N^{\ast},$ dengan kos $O(n^2).$ Berikut adalah satu cara ia boleh dilakukan.

1. Bina Circuit 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 kaedah yang diterangkan dalam pelajaran sebelumnya. Ini memberi kita Circuit bersaiz $O(n^2).$

2. Tukar dua sistem $n$-Qubit menggunakan $n$ gate swap untuk menukar Qubit satu per satu.

3. Sama seperti langkah pertama, bina Circuit 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}$ ialah songsangan $a$ dalam $\mathbb{Z}_N^{\ast}.$

Dengan memulakan $n$ Qubit bawah dan menggabungkan tiga langkah, kita mendapat transformasi ini:

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

Kaedah ini memerlukan Qubit ruang kerja, tetapi ia dipulangkan ke keadaan mulanya pada akhir, yang membolehkan kita menggunakan Circuit ini untuk anggaran fasa. Jumlah kos Circuit yang kita peroleh ialah $O(n^2).$

Untuk menjalankan $M_a^2,$ $M_a^4,$ $M_a^8,$ dan seterusnya, kita boleh menggunakan kaedah yang sama persis, kecuali kita menggantikan $a$ dengan $a^2,$ $a^4,$ $a^8,$ dan seterusnya, sebagai elemen $\mathbb{Z}_N^{\ast}.$ Artinya, untuk sebarang kuasa $k$ yang kita pilih, kita boleh mencipta Circuit untuk $M_a^k$ bukan dengan mengulang $k$ kali Circuit untuk $M_a,$ tetapi sebaliknya dengan mengira $b = a^k \in \mathbb{Z}_N^{\ast}$ dan kemudian menggunakan Circuit untuk $M_b.$

Pengiraan kuasa $a^k \in \mathbb{Z}_N$ adalah masalah pemangkatan modular yang disebut dalam pelajaran sebelumnya. Pengiraan ini boleh dilakukan secara klasik, menggunakan algoritma pemangkatan modular yang disebut dalam pelajaran sebelumnya (sering disebut algoritma kuasa dalam teori nombor komputasi). Malah, kita hanya memerlukan kuasa pangkat-2 bagi $a,$ khususnya $a^2, a^4, \ldots a^{2^{m-1}} \in \mathbb{Z}_N^{\ast},$ dan kita boleh mendapatkan kuasa-kuasa ini dengan mengkuasaduakan secara berulang sebanyak $m-1$ kali. Setiap pengkuasaduaan boleh dilakukan oleh Circuit Boolean bersaiz $O(n^2).$

Pada dasarnya, apa yang kita lakukan di sini ialah memindahkan masalah mengulang $M_a$ sebanyak $2^{m-1}$ kali kepada pengiraan klasik yang cekap. Dan bernasib baik bahawa ini mungkin dilakukan! Untuk pilihan Circuit kuantum sewenang-wenang dalam masalah anggaran fasa, kemungkinan ini tidak mungkin — dan dalam kes itu kos anggaran fasa yang terhasil berkembang secara eksponen dalam bilangan Qubit kawalan $m.$

Penyelesaian dengan eigenvector yang sesuai

Untuk memahami cara kita menyelesaikan masalah pencarian peringkat menggunakan anggaran fasa, mari kita mulakan dengan andaian bahawa kita menjalankan prosedur anggaran fasa ke atas operasi $M_a$ menggunakan eigenvector $\vert\psi_1\rangle.$ Mendapatkan eigenvector ini tidaklah mudah, ternyata, jadi ini bukan penghujung cerita — tetapi berguna untuk bermula di sini.

Nilai eigen $M_a$ yang sepadan dengan eigenvector $\vert \psi_1\rangle$ ialah

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

Iaitu, $\omega_r = e^{2\pi i \theta}$ untuk $\theta = 1/r.$ Jadi, jika kita menjalankan prosedur anggaran fasa ke atas $M_a$ menggunakan eigenvector $\vert\psi_1\rangle,$ kita akan mendapat anggaran bagi $1/r.$ Dengan mengira songsangannya kita akan dapat mengetahui $r$ — dengan syarat anggaran kita cukup baik.

Secara lebih terperinci, apabila kita menjalankan prosedur anggaran fasa menggunakan $m$ Qubit kawalan, yang kita perolehi ialah nombor $y\in\{0,\ldots,2^m-1\}.$ Kemudian kita ambil $y/2^m$ sebagai teka-teki untuk $\theta,$ yang dalam kes ini ialah $1/r.$ Untuk mengetahui $r$ daripada anggaran ini, perkara yang wajar dilakukan ialah mengira songsangan anggaran kita dan membundarkan kepada integer terdekat.

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

Sebagai contoh, katakan $r = 6$ dan kita menjalankan anggaran fasa ke atas $M_a$ dengan eigenvector $\vert\psi_1\rangle$ menggunakan $m = 5$ bit kawalan. Anggaran $5$ bit terbaik kepada $1/r = 1/6$ ialah $5/32,$ dan kita mempunyai peluang yang agak baik (kira-kira $68\%$ dalam kes ini) untuk mendapat hasil $y=5$ daripada anggaran fasa. Kita ada

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

dan membundarkan kepada integer terdekat memberi $6,$ iaitu jawapan yang betul.

Sebaliknya, jika kita tidak menggunakan ketepatan yang cukup, kita mungkin tidak mendapat jawapan yang betul. Contohnya, jika kita mengambil $m = 4$ Qubit kawalan dalam anggaran fasa, kita mungkin mendapat anggaran $4$ bit terbaik kepada $1/r = 1/6,$ iaitu $3/16.$ Mengira songsangannya menghasilkan

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

dan membundarkan kepada integer terdekat memberi jawapan yang salah iaitu $5.$

Jadi berapa banyak ketepatan yang kita perlukan untuk mendapat jawapan yang betul? Kita tahu bahawa peringkat $r$ adalah integer, dan secara intuitif apa yang kita perlukan ialah ketepatan yang cukup untuk membezakan $1/r$ daripada kemungkinan berdekatan, termasuk $1/(r+1)$ dan $1/(r-1).$ Nombor yang paling rapat dengan $1/r$ yang perlu kita bimbangkan ialah $1/(r+1),$ dan jarak antara dua nombor ini ialah

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

Jadi, jika kita ingin memastikan kita tidak silap $1/r$ dengan $1/(r+1),$ cukuplah menggunakan ketepatan yang menjamin anggaran terbaik $y/2^m$ kepada $1/r$ lebih rapat kepada $1/r$ berbanding $1/(r+1).$ Jika kita menggunakan ketepatan yang cukup supaya

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

supaya ralat kurang daripada separuh jarak antara $1/r$ dan $1/(r+1),$ maka $y/2^m$ akan lebih rapat kepada $1/r$ berbanding mana-mana kemungkinan lain, termasuk $1/(r+1)$ dan $1/(r-1).$

Kita boleh menyemak ini seperti berikut. Andaikan bahawa

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

untuk $\varepsilon$ yang memenuhi

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

Apabila kita mengira songsangannya kita dapat

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

Dengan memaksimumkan pengangka dan meminimumkan penyebut, kita boleh menganggar sejauh mana kita dari $r$ seperti 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$ jauh dari $r,$ jadi seperti yang dijangkakan kita akan mendapat $r$ apabila membundarkan.

Malangnya, kerana kita belum tahu $r,$ kita tidak boleh menggunakannya untuk memberitahu kita berapa banyak ketepatan yang diperlukan. Apa yang boleh kita lakukan sebaliknya ialah menggunakan fakta bahawa $r$ mestilah lebih kecil dari $N$ untuk memastikan kita menggunakan ketepatan yang mencukupi. Khususnya, jika kita menggunakan ketepatan yang cukup untuk menjamin anggaran terbaik $y/2^m$ kepada $1/r$ memenuhi

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

maka kita akan mempunyai ketepatan yang cukup untuk menentukan $r$ dengan betul apabila kita mengira songsangannya. Mengambil $m = 2\operatorname{lg}(N)+1$ memastikan kita mempunyai peluang tinggi untuk mendapat anggaran dengan ketepatan ini menggunakan kaedah yang diterangkan sebelumnya. (Mengambil $m = 2\operatorname{lg}(N)$ sudah cukup jika kita selesa dengan had bawah 40% untuk kebarangkalian kejayaan.)

Penyelesaian umum

Seperti yang baru kita lihat, jika kita mempunyai eigenvector $\vert \psi_1 \rangle$ bagi $M_a,$ kita boleh mengetahui $r$ melalui anggaran fasa, selagi kita menggunakan Qubit kawalan yang cukup untuk melakukan ini dengan ketepatan yang mencukupi. Malangnya, tidak mudah untuk mendapatkan eigenvector $\vert\psi_1\rangle,$ jadi kita perlu memikirkan cara untuk meneruskan.

Mari kita andaikan seketika bahawa kita meneruskan seperti di atas, tetapi dengan eigenvector $\vert\psi_k\rangle$ menggantikan $\vert\psi_1\rangle,$ untuk sebarang pilihan $k\in\{0,\ldots,r-1\}$ yang kita pilih untuk fikirkan. Hasil yang kita peroleh daripada prosedur anggaran fasa akan menjadi anggaran

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

Dengan andaian bahawa kita tidak mengetahui sama ada $k$ mahupun $r,$ ini mungkin atau mungkin tidak membolehkan kita mengenal pasti $r.$ Contohnya, jika $k = 0$ kita akan mendapat anggaran $y/2^m$ kepada $0,$ yang malangnya tidak memberitahu kita apa-apa. Walau bagaimanapun, ini kes yang luar biasa; untuk nilai $k$ yang lain, kita sekurang-kurangnya akan dapat mempelajari sesuatu tentang $r.$

Kita boleh menggunakan algoritma yang dikenali sebagai algoritma pecahan berterusan untuk menukar anggaran $y/2^m$ kita kepada pecahan-pecahan berdekatan — termasuk $k/r$ jika anggaran cukup baik. Kita tidak akan menerangkan algoritma pecahan berterusan di sini. Sebaliknya, ini adalah pernyataan fakta yang diketahui tentang algoritma ini.

Fakta

Diberi integer $N\geq 2$ dan nombor nyata $\alpha\in(0,1),$ terdapat paling banyak satu pilihan integer $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}.$ Diberi $\alpha$ dan $N,$ algoritma pecahan berterusan mencari $u$ dan $v,$ atau melaporkan bahawa ia tidak wujud. Algoritma ini boleh dilaksanakan sebagai Circuit Boolean bersaiz $O((\operatorname{lg}(N))^3).$

Jika kita mempunyai anggaran $y/2^m$ yang sangat rapat kepada $k/r,$ dan kita menjalankan algoritma pecahan berterusan untuk $N$ dan $\alpha = y/2^m,$ kita akan mendapat $u$ dan $v,$ seperti yang diterangkan dalam fakta tersebut. Analisis fakta tersebut membolehkan kita menyimpulkan bahawa

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

Perhatikan khususnya bahawa kita tidak semestinya mengetahui $k$ dan $r,$ kita hanya mengetahui $k/r$ dalam sebutan paling mudah.

Sebagai contoh, dan seperti yang sudah kita perhatikan, kita tidak akan mempelajari apa-apa daripada $k=0.$ Tetapi itulah satu-satunya nilai $k$ di mana perkara itu berlaku. Apabila $k$ bukan sifar, ia mungkin mempunyai faktor sepunya dengan $r,$ tetapi nombor $v$ yang kita peroleh daripada algoritma pecahan berterusan sekurang-kurangnya mesti membahagi $r.$

Ia jauh dari jelas, tetapi ia memang benar bahawa jika kita mempunyai kemampuan untuk mengetahui $u$ dan $v$ untuk $u/v = k/r$ bagi $k\in\{0,\ldots,r-1\}$ yang dipilih secara seragam rawak, maka kita berkemungkinan besar dapat memulihkan $r$ selepas beberapa sampel sahaja. Khususnya, jika teka-teki kita untuk $r$ ialah gandaan sepunya terkecil bagi semua nilai penyebut $v$ yang kita perhatikan, kita akan betul dengan kebarangkalian tinggi. Secara intuitif, sesetengah nilai $k$ tidak baik kerana ia mempunyai faktor sepunya dengan $r,$ dan faktor-faktor sepunya itu tersembunyi daripada kita apabila kita mengetahui $u$ dan $v.$ Tetapi pilihan $k$ secara rawak tidak mungkin menyembunyikan faktor $r$ untuk lama, dan kebarangkalian bahawa kita tidak meneka $r$ dengan betul melalui gandaan sepunya terkecil penyebut yang kita perhatikan susut secara eksponen dalam bilangan sampel.

Masalah cara kita mendapatkan eigenvector $\vert\psi_k\rangle$ bagi $M_a$ untuk menjalankan prosedur anggaran fasa masih perlu ditangani. Rupanya, kita sebenarnya tidak perlu menciptanya!

Apa yang akan kita lakukan sebaliknya ialah menjalankan prosedur anggaran fasa ke atas keadaan $\vert 1\rangle,$ yang bermaksud pengekodkan perduaan $n$-bit bagi nombor $1,$ sebagai ganti eigenvector $\vert\psi\rangle$ bagi $M_a.$ Setakat ini, kita hanya bercakap tentang menjalankan prosedur anggaran fasa ke atas eigenvector tertentu, tetapi tiada apa yang menghalang kita daripada menjalankan prosedur ke atas keadaan input yang bukan eigenvector $M_a,$ dan itulah yang kita lakukan di sini dengan keadaan $\vert 1\rangle.$ (Ini bukan eigenvector bagi $M_a$ melainkan $a=1,$ yang bukan pilihan yang kita minati.)

Rasional untuk memilih keadaan $\vert 1\rangle$ sebagai ganti eigenvector $M_a$ ialah persamaan berikut adalah benar.

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

Satu cara untuk mengesahkan persamaan ini ialah dengan membandingkan hasil darab dalaman kedua-dua sisi dengan setiap keadaan asas piawai, menggunakan formula yang disebutkan sebelumnya dalam pelajaran untuk membantu menilai hasil bagi sebelah kanan. Akibatnya, kita akan mendapat tepat-tepat hasil pengukuran yang sama seolah-olah kita telah memilih $k\in\{0,\ldots,r-1\}$ secara seragam rawak dan menggunakan $\vert\psi_k\rangle$ sebagai eigenvector.

Secara lebih terperinci, bayangkan kita menjalankan prosedur anggaran fasa dengan keadaan $\vert 1\rangle$ sebagai ganti salah satu eigenvector $\vert\psi_k\rangle.$ Selepas jelmaan Fourier kuantum songsang 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$ mewakili keadaan $m$ Qubit atas selepas songsangan jelmaan Fourier kuantum dilakukan ke atasnya.

Jadi, berdasarkan fakta bahawa $\{\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle\}$ adalah set ortonormal, kita dapati bahawa pengukuran $m$ Qubit atas menghasilkan anggaran $y/2^m$ kepada nilai $k/r$ di mana $k\in\{0,\ldots,r-1\}$ dipilih secara seragam rawak. Seperti yang sudah kita bincangkan, ini membolehkan kita mengetahui $r$ dengan keyakinan tinggi selepas beberapa larian bebas, yang merupakan matlamat kita.

Jumlah kos

Kos untuk melaksanakan setiap unitari-berkawalan $M_a^k$ ialah $O(n^2).$ Terdapat $m$ operasi unitari-berkawalan, dan kita mempunyai $m = O(n),$ jadi jumlah kos untuk operasi unitari-berkawalan ialah $O(n^3).$ Selain itu, kita mempunyai $m$ Gate Hadamard (yang menyumbang $O(n)$ kepada kos), dan jelmaan Fourier kuantum songsang menyumbang $O(n^2)$ kepada kos. Oleh itu, kos operasi unitari-berkawalan mendominasi kos keseluruhan prosedur — yang oleh itu ialah $O(n^3).$

Selain Circuit kuantum itu sendiri, terdapat beberapa pengiraan klasik yang perlu dilakukan sepanjang jalan. Ini termasuk mengira kuasa $a^k$ dalam $\mathbb{Z}_N$ untuk $k = 2, 4, 8, \ldots, 2^{m-1},$ yang diperlukan untuk mencipta Gate unitari-berkawalan, serta algoritma pecahan berterusan yang menukar anggaran $\theta$ kepada pecahan. Pengiraan-pengiraan ini boleh dilakukan oleh Circuit Boolean dengan jumlah kos $O(n^3).$

Seperti biasa, semua had ini boleh diperbaiki menggunakan algoritma yang cekap secara asimptotik; had ini mengandaikan kita menggunakan algoritma piawai untuk operasi aritmetik asas.

Pemfaktoran melalui pencarian peringkat

Perkara terakhir yang perlu kita bincangkan ialah bagaimana menyelesaikan masalah pencarian peringkat membantu kita untuk memfaktorkan. Bahagian ini sepenuhnya klasik — ia tidak ada kaitan khusus dengan pengkomputeran kuantum.

Begini idea asasnya. Kita ingin memfaktorkan nombor $N,$ dan kita boleh melakukan ini secara rekursif. Khususnya, kita boleh menumpukan pada tugasan memisahkan $N,$ yang bermaksud mencari mana-mana dua integer $b,c\geq 2$ dengan $N = bc.$ Ini tidak mungkin jika $N$ adalah nombor perdana, tetapi kita boleh menguji dengan cekap sama ada $N$ perdana menggunakan algoritma ujian keprerdanaan terlebih dahulu, dan jika $N$ bukan perdana kita akan cuba memisahkannya. Setelah kita memisahkan $N,$ kita boleh secara rekursif berulang ke $b$ dan $c$ sehingga semua faktor kita adalah perdana dan kita mendapat pemfaktoran perdana $N.$

Memisahkan integer genap adalah mudah: kita hanya keluarkan $2$ dan $N/2.$

Mudah juga untuk memisahkan kuasa sempurna, iaitu nombor dalam bentuk $N = s^j$ untuk integer $s,j\geq 2,$ hanya dengan menganggar punca $N^{1/2},$ $N^{1/3},$ $N^{1/4},$ dan seterusnya, dan memeriksa integer berdekatan sebagai suspek untuk $s.$ Kita tidak perlu pergi lebih jauh dari $\log(N)$ langkah dalam jujukan ini, kerana pada ketika itu punca jatuh di bawah $2$ dan tidak akan mendedahkan calon tambahan.

Bagus bahawa kita boleh melakukan kedua-dua perkara ini kerana pencarian peringkat tidak akan membantu kita memfaktorkan nombor genap atau kuasa perdana, di mana nombor $s$ kebetulan adalah perdana. Jika $N$ ganjil dan bukan kuasa perdana, bagaimanapun, pencarian peringkat membolehkan kita memisahkan $N.$

Algoritma kebarangkalian untuk memisahkan integer ganjil, komposit N yang bukan kuasa perdana

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

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

3. Jika $d > 1$ maka keluarkan $b = d$ dan $c = N/d$ dan berhenti. Jika tidak teruskan ke langkah berikutnya dengan mengetahui bahawa $a\in\mathbb{Z}_N^{\ast}.$

4. Biar $r$ ialah peringkat $a$ modulo $N.$ (Di sinilah kita memerlukan pencarian peringkat.)

5. Jika $r$ genap:

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

6. Jika titik ini dicapai, algoritma telah gagal mencari faktor $N.$

Satu larian algoritma ini mungkin gagal mencari faktor $N.$ Khususnya, ini berlaku dalam dua situasi:

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

Menggunakan teori nombor asas boleh dibuktikan bahawa, untuk pilihan rawak $a,$ dengan kebarangkalian sekurang-kurangnya $1/2$ tiada satu pun daripada peristiwa ini berlaku. Malah, kebarangkalian bahawa mana-mana peristiwa berlaku adalah paling banyak $2^{-(m-1)}$ untuk $m$ ialah bilangan faktor perdana berbeza $N,$ itulah sebabnya andaian bahawa $N$ bukan kuasa perdana diperlukan. (Andaian bahawa $N$ ganjil juga diperlukan agar fakta ini benar.)

Ini bermakna setiap larian mempunyai sekurang-kurangnya 50% peluang untuk memisahkan $N.$ Oleh itu, jika kita menjalankan algoritma $t$ kali, memilih $a$ secara rawak setiap kali, kita akan berjaya memisahkan $N$ dengan kebarangkalian sekurang-kurangnya $1 - 2^{-t}.$

Idea asas di sebalik algoritma ini adalah seperti berikut. Jika kita mempunyai pilihan $a$ di mana peringkat $r$ bagi $a$ modulo $N$ adalah genap, maka $r/2$ adalah integer dan kita boleh mempertimbangkan nombor-nombor

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

Menggunakan formula $Z^2 - 1 = (Z+1)(Z-1),$ kita simpulkan bahawa

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

Kini, kita tahu bahawa $a^r \; (\textrm{mod}\; N) = 1$ mengikut definisi peringkat — yang merupakan cara lain untuk mengatakan bahawa $N$ membahagi tepat $a^r - 1.$ Ini bermakna $N$ membahagi tepat hasil darab

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

Agar ini benar, semua faktor perdana $N$ mestilah juga faktor perdana $a^{r/2} - 1$ atau $a^{r/2} + 1$ (atau kedua-duanya) — dan untuk pilihan $a$ secara rawak, ternyata tidak mungkin semua faktor perdana $N$ akan membahagi satu sebutan sahaja tanpa yang lain. Selain itu, selagi sesetengah faktor perdana $N$ membahagi sebutan pertama dan sesetengah membahagi sebutan kedua, kita akan dapat mencari faktor bukan trivial $N$ dengan mengira GCD dengan sebutan pertama.