Algoritma Simon

Algoritma Simon adalah algoritma kueri kuantum untuk masalah yang dikenal sebagai masalah Simon. Ini adalah masalah janji dengan nuansa serupa masalah Deutsch-Jozsa dan Bernstein-Vazirani, tetapi spesifikasinya berbeda.

Algoritma Simon penting karena memberikan keunggulan eksponensial kuantum atas algoritma klasik (termasuk probabilistik), dan teknik yang digunakannya menginspirasi penemuan Peter Shor tentang algoritma kuantum efisien untuk faktorisasi bilangan bulat.

Masalah Simon

Fungsi input untuk masalah Simon berbentuk

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

untuk bilangan bulat positif $n$ dan $m.$ Kita bisa membatasi perhatian pada kasus $m = n$ demi kesederhanaan, tetapi tidak banyak yang didapat dari membuat asumsi ini — algoritma Simon dan analisisnya pada dasarnya sama dengan cara manapun.

Masalah Simon

Input: fungsi $f:\Sigma^n \rightarrow \Sigma^m$
Janji: ada string $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: string $s$

Kita akan mengurai janjinya untuk lebih memahami apa yang dikatakannya sebentar lagi, tetapi pertama-tama mari kita perjelas bahwa itu mengharuskan $f$ memiliki struktur yang sangat khusus — sehingga sebagian besar fungsi tidak akan memenuhi janji ini. Juga tepat untuk mengakui bahwa masalah ini tidak dimaksudkan untuk memiliki kepentingan praktis. Sebaliknya, ini adalah masalah agak buatan yang sengaja dibuat mudah untuk komputer kuantum dan sulit untuk komputer klasik.

Ada dua kasus utama: kasus pertama adalah bahwa $s$ adalah string semua-nol $0^n,$ dan kasus kedua adalah $s$ bukan string semua-nol.

• Kasus 1: $s=0^n.$ Jika $s$ adalah string semua-nol, kita bisa menyederhanakan pernyataan jika-dan-hanya-jika dalam janji sehingga berbunyi $[f(x) = f(y)] \Leftrightarrow [x = y].$ Ini setara dengan $f$ sebagai fungsi satu-ke-satu.

• Kasus 2: $s\neq 0^n.$ Jika $s$ bukan string semua-nol, maka janji yang dipenuhi untuk string ini menyiratkan bahwa $f$ adalah dua-ke-satu, artinya untuk setiap string keluaran yang mungkin dari $f,$ ada tepat dua string masukan yang menyebabkan $f$ mengeluarkan string itu. Selain itu, dua string masukan ini harus berbentuk $w$ dan $w \oplus s$ untuk beberapa string $w.$

Penting untuk disadari bahwa hanya ada satu string $s$ yang bisa cocok jika janji dipenuhi, sehingga selalu ada jawaban yang unik dan benar untuk fungsi yang memenuhi janji.

Berikut adalah contoh fungsi berbentuk $f:\Sigma^3 \rightarrow \Sigma^5$ yang memenuhi janji untuk string $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}$$

Ada $8$ string masukan yang berbeda dan $4$ string keluaran yang berbeda, masing-masing terjadi dua kali — jadi ini adalah fungsi dua-ke-satu. Selain itu, untuk dua string masukan yang berbeda yang menghasilkan string keluaran yang sama, kita melihat bahwa XOR bitwise dari dua string masukan ini sama dengan $011,$ yang setara dengan mengatakan bahwa salah satunya sama dengan yang lain yang di-XOR dengan $s.$

Perhatikan bahwa satu-satunya hal yang penting tentang string keluaran yang sebenarnya adalah apakah mereka sama atau berbeda untuk pilihan string masukan yang berbeda. Misalnya, dalam contoh di atas, ada empat string $(10011,$ $00101,$ $00001,$ dan $11010)$ yang muncul sebagai keluaran $f.$ Kita bisa mengganti empat string ini dengan string yang berbeda, selama semuanya berbeda, dan solusi yang benar $s = 011$ tidak akan berubah.

Deskripsi algoritma

Berikut adalah diagram sirkuit kuantum yang mewakili algoritma Simon.

Untuk lebih jelasnya, ada $n$ qubit di atas yang dikenai gate Hadamard dan $m$ qubit di bawah yang langsung masuk ke gate kueri. Tampilannya sangat mirip dengan algoritma yang sudah kita bahas dalam pelajaran, tetapi kali ini tidak ada phase kickback; semua $m$ qubit bawah masuk ke gate kueri dalam keadaan $\vert 0\rangle.$

Untuk memecahkan masalah Simon menggunakan sirkuit ini sebenarnya memerlukan beberapa jalankan independen diikuti oleh langkah pemrosesan pasca-klasik, yang akan dijelaskan nanti setelah perilaku sirkuit dianalisis.

Analisis

Analisis algoritma Simon dimulai dengan cara yang sama dengan algoritma Deutsch-Jozsa. Setelah lapisan pertama gate Hadamard dilakukan pada $n$ qubit atas, keadaannya menjadi

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

Ketika $U_f$ dilakukan, keluaran fungsi $f$ di-XOR ke keadaan semua-nol dari $m$ qubit bawah, sehingga keadaannya menjadi

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

Ketika lapisan kedua gate Hadamard dilakukan, kita mendapatkan keadaan berikut menggunakan rumus yang sama untuk aksi 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 titik ini, analisis menyimpang dari analisis untuk algoritma-algoritma sebelumnya dalam pelajaran ini.

Kita tertarik pada probabilitas pengukuran menghasilkan setiap string yang mungkin $y\in\Sigma^n.$ Melalui aturan untuk menganalisis pengukuran yang dijelaskan dalam pelajaran Beberapa sistem dari kursus Dasar-dasar informasi kuantum, kita menemukan bahwa probabilitas $p(y)$ untuk mendapatkan string $y$ 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 lebih memahami probabilitas ini, kita memerlukan sedikit lebih banyak notasi dan terminologi. Pertama, jangkauan dari fungsi $f$ adalah himpunan yang berisi semua string keluarannya.

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

Kedua, untuk setiap string $z\in\operatorname{range}(f),$ kita dapat menyatakan himpunan semua string masukan yang menyebabkan fungsi mengevaluasi ke string keluaran $z$ ini sebagai $f^{-1}(\{z\}).$

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

Himpunan $f^{-1}(\{z\})$ dikenal sebagai preimage dari $\{z\}$ di bawah $f.$ Kita bisa mendefinisikan preimage di bawah $f$ dari himpunan manapun sebagai pengganti $\{z\}$ dengan cara yang analog — itu adalah himpunan semua elemen yang dipetakan $f$ ke himpunan tersebut. (Notasi ini tidak boleh dikacaukan dengan invers dari fungsi $f,$ yang mungkin tidak ada. Fakta bahwa argumen di sisi kiri adalah himpunan $\{z\}$ bukan elemen $z$ adalah petunjuk yang memungkinkan kita menghindari kebingungan ini.)

Menggunakan notasi ini, kita bisa memisahkan jumlahan dalam ekspresi kita untuk probabilitas 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 string $x\in\Sigma^n$ direpresentasikan tepat sekali oleh dua penjumlahan — kita pada dasarnya hanya menempatkan string-string ini ke dalam ember terpisah tergantung pada string keluaran mana $z = f(x)$ yang mereka hasilkan saat kita mengevaluasi fungsi $f,$ kemudian menjumlahkan secara terpisah atas semua ember.

Kita sekarang bisa mengevaluasi kuadrat 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 menyederhanakan probabilitas ini lebih lanjut, mari kita lihat nilai

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

untuk pilihan arbitrer dari $z\in\operatorname{range}(f).$

Jika ternyata $s = 0^n,$ maka $f$ adalah fungsi satu-ke-satu dan selalu ada hanya satu elemen $x\in f^{-1}(\{z\}),$ untuk setiap $z\in\operatorname{range}(f).$ Nilai ekspresi $(1)$ adalah $1$ dalam kasus ini.

Jika, di sisi lain, $s\neq 0^n,$ maka ada tepat dua string dalam himpunan $f^{-1}(\{z\}).$ Lebih tepatnya, jika kita memilih $w\in f^{-1}(\{z\})$ sebagai salah satu dari dua string ini, maka string lainnya harus $w \oplus s$ berdasarkan janji dalam masalah Simon. Menggunakan observasi ini kita bisa menyederhanakan $(1)$ sebagai 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)$ tidak bergantung pada pilihan spesifik $z\in\operatorname{range}(f)$ dalam kedua kasus.

Kita sekarang bisa menyelesaikan analisis dengan melihat dua kasus yang sama seperti sebelumnya secara terpisah.

• Kasus 1: $s = 0^n.$ Dalam kasus ini fungsi $f$ adalah satu-ke-satu, sehingga ada $2^n$ string $z\in\operatorname{range}(f),$ dan kita mendapatkan

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

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

• Kasus 2: $s \neq 0^n.$ Dalam kasus ini $f$ adalah dua-ke-satu, sehingga ada $2^{n-1}$ elemen dalam $\operatorname{range}(f).$ Menggunakan rumus dari atas kita menyimpulkan bahwa probabilitas mengukur setiap $y\in\Sigma^n$ adalah

  $$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 mendapatkan string yang dipilih secara seragam acak dari himpunan $\{y\in\Sigma^n : y \cdot s = 0\},$ yang berisi $2^{n-1}$ string. (Karena $s\neq 0^n,$ tepat setengah dari string biner dengan panjang $n$ memiliki hasil kali titik biner $1$ dengan $s$ dan yang lain memiliki hasil kali titik biner $0$ dengan $s,$ seperti yang sudah kita amati dalam analisis algoritma Deutsch-Jozsa untuk masalah Bernstein-Vazirani.)

Pemrosesan pasca-klasik

Kita sekarang tahu apa probabilitas untuk kemungkinan hasil pengukuran ketika kita menjalankan sirkuit kuantum untuk algoritma Simon. Apakah ini cukup informasi untuk menentukan $s$?

Jawabannya ya, asalkan kita bersedia mengulangi prosesnya beberapa kali dan menerima bahwa itu bisa gagal dengan beberapa probabilitas, yang bisa kita buat sangat kecil dengan menjalankan sirkuit cukup banyak kali. Ide dasarnya adalah bahwa setiap eksekusi sirkuit memberi kita bukti statistik tentang $s,$ dan kita bisa menggunakan bukti itu untuk menemukan $s$ dengan probabilitas sangat tinggi jika kita menjalankan sirkuit cukup banyak kali.

Misalkan kita menjalankan sirkuit secara independen $k$ kali, untuk $k = n + 10.$ Tidak ada yang istimewa tentang jumlah iterasi khusus ini — kita bisa mengambil $k$ lebih besar (atau lebih kecil) tergantung pada probabilitas kegagalan yang bersedia kita toleransi, seperti yang akan kita lihat. Memilih $k = n + 10$ akan memastikan bahwa kita memiliki lebih dari $99.9$% kesempatan untuk memulihkan $s.$

Dengan menjalankan sirkuit $k$ kali, kita mendapatkan string $y^1,...,y^{k} \in \Sigma^n.$ Untuk lebih jelasnya, superskrip di sini adalah bagian dari nama string-string ini, bukan eksponen atau indeks ke bit mereka, jadi kita memiliki

$$\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 sekarang membentuk matriks $M$ yang memiliki $k$ baris dan $n$ kolom dengan mengambil bit-bit string ini sebagai entri bernilai biner.

$$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 $s$ pada titik ini — tujuan kita adalah menemukan string ini. Tetapi bayangkan sebentar bahwa kita tahu string $s,$ dan kita membentuk vektor kolom $v$ dari bit-bit string $s = s_{n-1} \cdots s_0$ sebagai berikut.

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

Jika kita melakukan perkalian matriks-vektor $M v$ modulo $2$ — artinya kita melakukan perkalian seperti biasa kemudian mengambil sisa entri hasilnya setelah dibagi $2$ — kita mendapatkan vektor semua-nol.

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

Artinya, diperlakukan sebagai vektor kolom $v$ seperti yang baru saja dijelaskan, string $s$ akan selalu menjadi elemen dari ruang nol matriks $M,$ asalkan kita melakukan aritmetika modulo $2.$ Ini berlaku baik dalam kasus $s = 0^n$ maupun $s\neq 0^n.$ Lebih tepatnya, vektor semua-nol selalu ada dalam ruang nol $M,$ dan bergabung dengan vektor yang entrinya adalah bit-bit $s$ dalam kasus $s\neq 0^n.$

Pertanyaan yang tersisa adalah apakah akan ada vektor lain dalam ruang nol $M$ selain yang bersesuaian dengan $0^n$ dan $s.$ Jawabannya adalah ini menjadi semakin tidak mungkin seiring $k$ meningkat — dan jika kita memilih $k = n + 10,$ ruang nol $M$ tidak akan berisi vektor lain selain yang bersesuaian dengan $0^n$ dan $s$ dengan lebih dari $99.9$% kesempatan. Lebih umum, jika kita mengganti $k = n + 10$ dengan $k = n + r$ untuk pilihan bilangan bulat positif $r$ yang arbitrer, probabilitas bahwa vektor yang bersesuaian dengan $0^n$ dan $s$ sendirian dalam ruang nol $M$ adalah setidaknya $1 - 2^{-r}.$

Menggunakan aljabar linear, memungkinkan untuk secara efisien menghitung deskripsi ruang nol $M$ modulo $2.$ Secara khusus, ini bisa dilakukan menggunakan eliminasi Gaussian, yang bekerja dengan cara yang sama ketika aritmetika dilakukan modulo $2$ seperti halnya dengan bilangan nyata atau kompleks. Selama vektor yang bersesuaian dengan $0^n$ dan $s$ sendirian dalam ruang nol $M,$ yang terjadi dengan probabilitas tinggi, kita dapat menyimpulkan $s$ dari hasil komputasi ini.

Kesulitan klasik

Berapa banyak kueri yang diperlukan algoritma kueri klasik untuk memecahkan masalah Simon? Jawabannya adalah: banyak, pada umumnya.

Ada pernyataan yang berbeda dan tepat yang dapat dibuat tentang kesulitan klasik masalah ini, dan berikut adalah satu di antaranya. Jika kita memiliki algoritma kueri probabilistik manapun, dan algoritma itu membuat kurang dari $2^{n/2 - 1} - 1$ kueri, yang merupakan jumlah kueri yang eksponensial dalam $n,$ maka algoritma itu akan gagal memecahkan masalah Simon dengan probabilitas setidaknya $1/2.$

Kadang-kadang, membuktikan hasil impossibilitas seperti ini bisa sangat menantang, tetapi ini tidak terlalu sulit untuk dibuktikan melalui analisis probabilistik elementer. Di sini, bagaimanapun, kita hanya akan secara singkat memeriksa intuisi dasar di baliknya.

Kita mencoba menemukan string tersembunyi $s,$ tetapi selama kita tidak melakukan kueri ke fungsi pada dua string yang memiliki nilai keluaran yang sama, kita akan mendapatkan informasi yang sangat terbatas tentang $s.$ Secara intuitif, yang akan kita pelajari hanyalah bahwa string tersembunyi $s$ bukan XOR eksklusif dari dua string berbeda yang telah kita kueri. Dan jika kita melakukan kueri kurang dari $2^{n/2 - 1} - 1$ string, masih akan ada banyak pilihan untuk $s$ yang belum kita singkirkan karena tidak ada cukup pasang string untuk melakukannya. Ini bukan bukti formal, ini hanya ide dasarnya.

Jadi, singkatnya, algoritma Simon memberikan kita keunggulan yang mencolok dari kuantum atas algoritma klasik dalam model kueri. Khususnya, algoritma Simon memecahkan masalah Simon dengan jumlah kueri yang linear dalam jumlah bit masukan $n$ dari fungsi kita, sedangkan algoritma klasik manapun, bahkan jika itu probabilistik, perlu membuat jumlah kueri yang eksponensial dalam $n$ untuk memecahkan masalah Simon dengan probabilitas keberhasilan yang wajar.