Algoritma Simon

Algoritma Simon ialah algoritma pertanyaan kuantum untuk masalah yang dikenali sebagai masalah Simon. Ini adalah masalah janji yang mempunyai ciri serupa dengan masalah Deutsch-Jozsa dan Bernstein-Vazirani, tetapi butiran teknikalnya berbeza.

Algoritma Simon penting kerana ia memberikan kelebihan eksponensial kuantum berbanding algoritma klasik (termasuk algoritma berkebarangkalian), dan teknik yang digunakannya mengilhamkan Peter Shor untuk menemui algoritma kuantum cekap bagi pemfaktoran integer.

Masalah Simon

Fungsi input untuk masalah Simon berbentuk

$$f:\Sigma^n \rightarrow \Sigma^m$$

untuk integer positif $n$ dan $m$. Kita boleh mengehadkan perhatian kepada kes $m = n$ demi kesederhanaan, tetapi tiada manfaat besar dalam membuat andaian ini — algoritma Simon dan analisisnya pada dasarnya sama dalam kedua-dua keadaan.

Masalah Simon

Input: fungsi $f:\Sigma^n \rightarrow \Sigma^m$
Janji: wujud suatu rentetan $s\in\Sigma^n$ sedemikian sehingga $[f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)]$ untuk semua $x,y\in\Sigma^n$
Output: rentetan $s$

Kita akan menguraikan janji tersebut untuk memahami maknanya sebentar lagi, tetapi mula-mula kita perlu jelas bahawa janji ini mensyaratkan $f$ mempunyai struktur yang sangat istimewa — jadi kebanyakan fungsi tidak akan memenuhi janji ini. Perlu juga diakui bahawa masalah ini tidak bertujuan untuk mempunyai kepentingan praktikal. Sebaliknya, ia adalah masalah yang agak tiruan, dicipta khas untuk mudah diselesaikan oleh komputer kuantum tetapi sukar bagi komputer klasik.

Terdapat dua kes utama: kes pertama ialah $s$ ialah rentetan semua-sifar $0^n$, dan kes kedua ialah $s$ bukan rentetan semua-sifar.

• Kes 1: $s=0^n.$ Jika $s$ ialah rentetan semua-sifar, kita boleh memudahkan pernyataan jika dan hanya jika dalam janji supaya ia berbunyi $[f(x) = f(y)] \Leftrightarrow [x = y].$ Ini bersamaan dengan $f$ menjadi fungsi satu-ke-satu.

• Kes 2: $s\neq 0^n.$ Jika $s$ bukan rentetan semua-sifar, maka janji yang dipenuhi untuk rentetan ini bermakna $f$ adalah dua-ke-satu, iaitu untuk setiap rentetan output yang mungkin bagi $f,$ terdapat tepat dua rentetan input yang menyebabkan $f$ menghasilkan rentetan itu. Selain itu, kedua-dua rentetan input tersebut mesti berbentuk $w$ dan $w \oplus s$ untuk suatu rentetan $w.$

Penting untuk diketahui bahawa hanya boleh ada satu rentetan $s$ yang berfungsi jika janji dipenuhi, jadi sentiasa ada jawapan yang unik dan betul untuk fungsi yang memenuhi janji.

Berikut ialah contoh fungsi berbentuk $f:\Sigma^3 \rightarrow \Sigma^5$ yang memenuhi janji untuk rentetan $s = 011$.

$$\begin{aligned} f(000) & = 10011 \\ f(001) & = 00101 \\ f(010) & = 00101 \\ f(011) & = 10011 \\ f(100) & = 11010 \\ f(101) & = 00001 \\ f(110) & = 00001 \\ f(111) & = 11010 \end{aligned}$$

Terdapat $8$ rentetan input yang berbeza dan $4$ rentetan output yang berbeza, setiap satunya muncul dua kali — jadi ini adalah fungsi dua-ke-satu. Selain itu, bagi mana-mana dua rentetan input berbeza yang menghasilkan rentetan output yang sama, kita dapati bahawa XOR bitwise bagi kedua-dua rentetan input tersebut adalah sama dengan $011$, yang bersamaan dengan mengatakan bahawa salah satunya adalah sama dengan yang satu lagi di-XOR dengan $s$.

Perhatikan bahawa satu-satunya perkara yang penting tentang rentetan output sebenar ialah sama ada ia sama atau berbeza bagi pilihan rentetan input yang berlainan. Contohnya, dalam contoh di atas, terdapat empat rentetan $(10011,$ $00101,$ $00001,$ dan $11010)$ yang muncul sebagai output $f.$ Kita boleh menggantikan keempat-empat rentetan ini dengan rentetan lain, asalkan semuanya berbeza, dan penyelesaian yang betul $s = 011$ tidak akan berubah.

Penerangan algoritma

Berikut ialah gambar rajah Circuit kuantum yang mewakili algoritma Simon.

Untuk jelasnya, terdapat $n$ qubit di bahagian atas yang dikenakan gate Hadamard dan $m$ qubit di bahagian bawah yang masuk terus ke gate pertanyaan. Ia kelihatan sangat serupa dengan algoritma yang telah kita bincangkan dalam pelajaran ini, tetapi kali ini tiada kickback fasa; $m$ qubit di bahagian bawah semuanya masuk ke dalam gate pertanyaan dalam keadaan $\vert 0\rangle$.

Untuk menyelesaikan masalah Simon menggunakan Circuit ini sebenarnya memerlukan beberapa kali larian bebas diikuti dengan langkah pasca-pemprosesan klasik, yang akan diterangkan kemudian selepas tingkah laku Circuit dianalisis.

Analisis

Analisis algoritma Simon bermula dengan cara yang serupa dengan algoritma Deutsch-Jozsa. Selepas lapisan gate Hadamard pertama dilakukan pada $n$ qubit teratas, keadaan menjadi

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert 0^m \rangle \vert x\rangle.$$

Apabila $U_f$ dilakukan, output fungsi $f$ di-XOR ke keadaan semua-sifar bagi $m$ qubit bahagian bawah, jadi keadaan menjadi

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert f(x) \rangle \vert x\rangle.$$

Apabila lapisan gate Hadamard kedua dilakukan, kita memperoleh keadaan berikut dengan menggunakan formula yang sama untuk tindakan lapisan gate Hadamard seperti sebelumnya.

$$\frac{1}{2^n} \sum_{x\in\Sigma^n} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \vert y\rangle$$

Pada ketika ini, analisis menyimpang daripada analisis algoritma-algoritma sebelumnya dalam pelajaran ini.

Kita berminat dengan kebarangkalian untuk pengukuran menghasilkan setiap rentetan yang mungkin $y\in\Sigma^n$. Melalui peraturan untuk menganalisis pengukuran yang diterangkan dalam pelajaran Sistem berganda dalam kursus Asas maklumat kuantum, kita dapati bahawa kebarangkalian $p(y)$ untuk mendapatkan rentetan $y$ adalah sama dengan

$$p(y) = \left\|\frac{1}{2^n} \sum_{x\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \right\|^2.$$

Untuk memahami kebarangkalian ini dengan lebih baik, kita perlukan sedikit lagi notasi dan terminologi. Pertama, julat fungsi $f$ ialah set yang mengandungi semua rentetan outputnya.

$$\operatorname{range}(f) = \{ f(x) : x\in \Sigma^n \}$$

Kedua, untuk setiap rentetan $z\in\operatorname{range}(f)$, kita boleh menyatakan set semua rentetan input yang dipetakan oleh fungsi kepada rentetan output $z$ ini sebagai $f^{-1}(\{z\})$.

$$f^{-1}(\{z\}) = \{ x\in\Sigma^n : f(x) = z \}$$

Set $f^{-1}(\{z\})$ dikenali sebagai praimej bagi $\{z\}$ di bawah $f$. Kita boleh mentakrifkan praimej di bawah $f$ bagi mana-mana set sebagai ganti $\{z\}$ dengan cara yang serupa — ia adalah set semua unsur yang dipetakan oleh $f$ ke set tersebut. (Notasi ini tidak boleh dikelirukan dengan songsangan fungsi $f$, yang mungkin tidak wujud. Fakta bahawa argumen di sebelah kiri ialah set $\{z\}$ dan bukan unsur $z$ adalah petanda yang membolehkan kita mengelakkan kekeliruan ini.)

Menggunakan notasi ini, kita boleh memisahkan jumlah dalam ungkapan kebarangkalian di atas untuk mendapatkan

$$p(y) = \left\| \frac{1}{2^n} \sum_{z\in\operatorname{range}(f)} \Biggl(\sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y}\Biggr) \vert z \rangle \right\|^2.$$

Setiap rentetan $x\in\Sigma^n$ diwakili tepat sekali oleh dua penjumlahan — pada dasarnya kita hanya memasukkan rentetan-rentetan ini ke dalam baldi berasingan bergantung pada rentetan output $z = f(x)$ yang dihasilkan apabila kita menilai fungsi $f$, kemudian menjumlahkan secara berasingan ke atas semua baldi.

Kita kini boleh menilai kuasa dua norma Euclidean untuk mendapatkan

$$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2.$$

Untuk memudahkan lagi kebarangkalian ini, mari kita lihat nilai

$$\left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 \tag{1}$$

untuk pemilihan sewenang-wenangnya bagi $z\in\operatorname{range}(f)$.

Sekiranya $s = 0^n$, maka $f$ adalah fungsi satu-ke-satu dan sentiasa hanya ada satu unsur $x\in f^{-1}(\{z\})$, untuk setiap $z\in\operatorname{range}(f)$. Nilai ungkapan $(1)$ adalah $1$ dalam kes ini.

Sebaliknya, jika $s\neq 0^n,$ maka terdapat tepat dua rentetan dalam set $f^{-1}(\{z\}).$ Secara tepat, jika kita memilih $w\in f^{-1}(\{z\})$ sebagai salah satu daripada dua rentetan ini, maka rentetan yang satu lagi mesti adalah $w \oplus s$ mengikut janji dalam masalah Simon. Menggunakan pemerhatian ini kita boleh memudahkan $(1)$ seperti berikut.

$$\begin{aligned} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 & = \Bigl\vert (-1)^{w\cdot y} + (-1)^{(w\oplus s)\cdot y} \Bigr\vert^2 \\ & = \Bigl\vert (-1)^{w\cdot y} \Bigl(1 + (-1)^{s\cdot y}\Bigr) \Bigr\vert^2 \\ & = \Bigl\vert 1 + (-1)^{y\cdot s} \Bigr\vert^2 \\ & = \begin{cases} 4 & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases} \end{aligned}$$

Jadi, ternyata nilai $(1)$ adalah bebas daripada pilihan $z\in\operatorname{range}(f)$ yang spesifik dalam kedua-dua kes.

Kita kini boleh menyelesaikan analisis dengan melihat dua kes yang sama seperti sebelumnya secara berasingan.

• Kes 1: $s = 0^n.$ Dalam kes ini fungsi $f$ adalah satu-ke-satu, jadi terdapat $2^n$ rentetan $z\in\operatorname{range}(f),$ dan kita mendapat

  $$p(y) = \frac{1}{2^{2n}} \cdot 2^n = \frac{1}{2^n}.$$

  Dengan kata lain, pengukuran menghasilkan rentetan $y\in\Sigma^n$ yang dipilih secara rawak seragam.

• Kes 2: $s \neq 0^n.$ Dalam kes ini $f$ adalah dua-ke-satu, jadi terdapat $2^{n-1}$ unsur dalam $\operatorname{range}(f).$ Menggunakan formula di atas kita simpulkan bahawa kebarangkalian untuk mengukur setiap $y\in\Sigma^n$ ialah

  $$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \Biggl\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \Biggr\vert^2 = \begin{cases} \frac{1}{2^{n-1}} & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases}$$

  Dengan kata lain, kita mendapat rentetan yang dipilih secara rawak seragam daripada set $\{y\in\Sigma^n : y \cdot s = 0\}$, yang mengandungi $2^{n-1}$ rentetan. (Kerana $s\neq 0^n$, tepat separuh daripada rentetan binari panjang $n$ mempunyai hasil darab titik binari $1$ dengan $s$ dan separuh lagi mempunyai hasil darab titik binari $0$ dengan $s$, seperti yang sudah kita perhatikan dalam analisis algoritma Deutsch-Jozsa untuk masalah Bernstein-Vazirani.)

Pasca-pemprosesan klasik

Kita kini tahu apakah kebarangkalian bagi hasil pengukuran yang mungkin apabila kita menjalankan Circuit kuantum untuk algoritma Simon. Adakah maklumat ini cukup untuk menentukan $s$?

Jawapannya ya, dengan syarat kita sanggup mengulangi proses beberapa kali dan menerima bahawa ia boleh gagal dengan suatu kebarangkalian, yang boleh kita jadikan sangat kecil dengan menjalankan Circuit cukup banyak kali. Idea pokoknya ialah setiap pelaksanaan Circuit memberikan kita bukti statistik tentang $s$, dan kita boleh menggunakan bukti itu untuk mencari $s$ dengan kebarangkalian yang sangat tinggi jika kita menjalankan Circuit cukup banyak kali.

Katakan kita menjalankan Circuit secara bebas $k$ kali, untuk $k = n + 10$. Tiada yang istimewa tentang bilangan iterasi tertentu ini — kita boleh menjadikan $k$ lebih besar (atau lebih kecil) bergantung pada kebarangkalian kegagalan yang sanggup kita terima, seperti yang akan kita lihat. Memilih $k = n + 10$ akan memastikan kita mempunyai lebih daripada $99.9$% peluang untuk memulihkan $s$.

Dengan menjalankan Circuit $k$ kali, kita mendapat rentetan $y^1,...,y^{k} \in \Sigma^n$. Untuk jelasnya, superskrip di sini adalah sebahagian daripada nama rentetan-rentetan ini, bukan eksponen atau indeks kepada bit mereka, jadi kita ada

$$\begin{aligned} y^1 & = y^1_{n-1} \cdots y^1_{0}\\[1mm] y^2 & = y^2_{n-1} \cdots y^2_{0}\\[1mm] & \;\; \vdots\\[1mm] y^{k} & = y^{k}_{n-1} \cdots y^{k}_{0} \end{aligned}$$

Kita kini membentuk matriks $M$ yang mempunyai $k$ baris dan $n$ lajur dengan mengambil bit rentetan-rentetan ini sebagai entri bernilai binari.

$$M = \begin{pmatrix} y^1_{n-1} & \cdots & y^1_{0}\\[1mm] y^2_{n-1} & \cdots & y^2_{0}\\[1mm] \vdots & \ddots & \vdots \\[1mm] y^{k}_{n-1} & \cdots & y^{k}_{0} \end{pmatrix}$$

Sekarang, kita tidak tahu apa itu $s$ pada ketika ini — matlamat kita adalah untuk mencari rentetan ini. Tetapi bayangkan sebentar bahawa kita memang tahu rentetan $s$, dan kita membentuk vektor lajur $v$ daripada bit rentetan $s = s_{n-1} \cdots s_0$ seperti berikut.

$$v = \begin{pmatrix} s_{n-1}\\ \vdots\\ s_0 \end{pmatrix}$$

Jika kita melakukan pendaraban matriks-vektor $M v$ modulo $2$ — bermakna kita melakukan pendaraban seperti biasa dan kemudian mengambil baki entri keputusan selepas dibahagi dengan $2$ — kita mendapat vektor semua-sifar.

$$M v = \begin{pmatrix} y^1 \cdot s\\ y^2 \cdot s\\ \vdots\\[1mm] y^{k} \cdot s \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ \vdots\\[1mm] 0 \end{pmatrix}$$

Iaitu, diperlakukan sebagai vektor lajur $v$ seperti yang baru diterangkan, rentetan $s$ akan sentiasa menjadi unsur dalam ruang nol matriks $M$, dengan syarat kita melakukan aritmetik modulo $2$. Ini benar dalam kedua-dua kes $s = 0^n$ dan $s\neq 0^n$. Lebih tepat lagi, vektor semua-sifar sentiasa berada dalam ruang nol $M$, dan ia disertai oleh vektor yang entri-entrinya adalah bit $s$ sekiranya $s\neq 0^n$.

Persoalan yang masih ada ialah sama ada akan ada vektor lain dalam ruang nol $M$ selain daripada yang sepadan dengan $0^n$ dan $s$. Jawapannya ialah ini menjadi semakin tidak mungkin apabila $k$ bertambah — dan jika kita memilih $k = n + 10$, ruang nol $M$ tidak akan mengandungi vektor lain selain daripada yang sepadan dengan $0^n$ dan $s$ dengan lebih daripada $99.9$% peluang. Secara lebih umum, jika kita menggantikan $k = n + 10$ dengan $k = n + r$ untuk pilihan integer positif $r$ yang sewenang-wenangnya, kebarangkalian bahawa vektor yang sepadan dengan $0^n$ dan $s$ bersendirian dalam ruang nol $M$ adalah sekurang-kurangnya $1 - 2^{-r}$.

Menggunakan aljabar linear, adalah mungkin untuk mengira secara cekap penerangan ruang nol $M$ modulo $2$. Khususnya, ia boleh dilakukan menggunakan penghapusan Gaussian, yang berfungsi dengan cara yang sama apabila aritmetik dilakukan modulo $2$ seperti dengan nombor nyata atau kompleks. Selagi vektor yang sepadan dengan $0^n$ dan $s$ bersendirian dalam ruang nol $M$, yang berlaku dengan kebarangkalian tinggi, kita boleh mengenal pasti $s$ daripada hasil pengiraan ini.

Kesukaran klasik

Berapa banyak pertanyaan yang diperlukan oleh algoritma pertanyaan klasik untuk menyelesaikan masalah Simon? Jawapannya: banyak, secara amnya.

Terdapat pelbagai pernyataan tepat yang boleh dibuat tentang kesukaran klasik masalah ini, dan berikut adalah salah satunya. Jika kita mempunyai mana-mana algoritma pertanyaan berkebarangkalian, dan algoritma itu membuat kurang daripada $2^{n/2 - 1} - 1$ pertanyaan, iaitu bilangan pertanyaan yang eksponensial dalam $n$, maka algoritma itu akan gagal menyelesaikan masalah Simon dengan kebarangkalian sekurang-kurangnya $1/2$.

Kadangkala, membuktikan hasil ketidakmungkinan seperti ini boleh menjadi sangat mencabar, tetapi yang ini tidak terlalu sukar untuk dibuktikan melalui analisis kebarangkalian asas. Di sini, walau bagaimanapun, kita hanya akan mengkaji secara ringkas intuisi asas di sebaliknya.

Kita cuba mencari rentetan tersembunyi $s$, tetapi selagi kita tidak membuat pertanyaan fungsi pada dua rentetan yang mempunyai nilai output yang sama, kita akan mendapat maklumat yang sangat terhad tentang $s$. Secara intuitif, yang kita pelajari hanyalah bahawa rentetan tersembunyi $s$ bukan XOR bagi mana-mana dua rentetan berbeza yang telah kita tanya. Dan jika kita membuat pertanyaan kurang daripada $2^{n/2 - 1} - 1$ rentetan, masih akan ada banyak pilihan untuk $s$ yang belum kita singkirkan kerana tidak ada cukup pasangan rentetan untuk melakukannya. Ini bukan bukti formal, ia hanya idea asasnya.

Jadi, kesimpulannya, algoritma Simon memberikan kita kelebihan yang ketara bagi kuantum berbanding algoritma klasik dalam model pertanyaan. Khususnya, algoritma Simon menyelesaikan masalah Simon dengan bilangan pertanyaan yang linear dalam bilangan bit input $n$ fungsi kita, manakala mana-mana algoritma klasik, walaupun ia berkebarangkalian, perlu membuat bilangan pertanyaan yang eksponensial dalam $n$ untuk menyelesaikan masalah Simon dengan kebarangkalian kejayaan yang munasabah.