Pengiraan klasik pada komputer kuantum

Sekarang kita akan menumpukan perhatian kepada pelaksanaan algoritma klasik pada komputer kuantum. Kita akan lihat bahawa mana-mana pengiraan yang boleh dilakukan dengan litar Boolean klasik boleh juga dilakukan oleh litar kuantum dengan kos pengiraan asimptotik yang serupa. Tambahan pula, ini boleh dilakukan dengan cara yang "bersih" yang akan dihuraikan tidak lama lagi, yang merupakan keperluan penting untuk menggunakan pengiraan-pengiraan ini sebagai subrutin dalam pengiraan kuantum yang lebih besar.

Mensimulasikan litar Boolean dengan litar kuantum

Litar Boolean terdiri daripada Gate AND, OR, NOT, dan FANOUT. Untuk mensimulasikan litar Boolean dengan litar kuantum, kita akan mulakan dengan menunjukkan bagaimana setiap empat Gate ini boleh disimulasikan oleh Gate kuantum. Setelah itu selesai, menukar litar Boolean yang diberikan kepada litar kuantum adalah perkara mudah untuk mensimulasikan satu Gate pada satu masa. Kita hanya memerlukan Gate NOT, Gate controlled-NOT, dan Gate Toffoli untuk melakukan ini, yang semuanya adalah operasi deterministik di samping menjadi unitari.

Gate Toffoli

Gate Toffoli boleh dihuraikan secara alternatif sebagai Gate controlled-controlled-NOT, yang tindakannya ke atas keadaan asas piawai adalah seperti yang ditunjukkan dalam rajah berikut.

Dengan mengingat bahawa kita menggunakan konvensyen pengurutan Qiskit, di mana Qubit diurutkan mengikut kepentingan yang meningkat dari atas ke bawah, representasi matriks Gate ini adalah seperti berikut.

$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}$$

Cara lain untuk memikirkan Gate Toffoli ialah ia pada dasarnya adalah Gate pertanyaan untuk fungsi AND, dalam erti kata bahawa ia mengikuti corak yang kita lihat dalam pelajaran sebelumnya untuk implementasi Gate pertanyaan unitari bagi fungsi sewenang-wenang yang mempunyai input dan output rentetan perduaan.

Gate Toffoli tidak termasuk dalam set Gate lalai yang dibincangkan sebelum ini dalam pelajaran, tetapi ia mungkin untuk membina Gate Toffoli daripada Gate $H,$ $T,$ $T^{\dagger},$ dan CNOT seperti berikut.

Mensimulasikan Gate Boolean dengan Gate Toffoli, controlled-NOT, dan NOT

Satu Gate Toffoli tunggal, yang digunakan bersama-sama dengan beberapa Gate NOT, boleh melaksanakan Gate AND dan OR, dan Gate FANOUT boleh dilaksanakan dengan mudah menggunakan Gate controlled-NOT, seperti yang dicadangkan oleh gambar rajah berikut.

Dalam ketiga-tiga kes, Qubit yang Gate AND, OR, dan FANOUT bertindak ke atasnya masuk dari kiri sebagai input, dan kita juga memerlukan satu Qubit ruang kerja yang diinisialisasi kepada keadaan sifar untuk setiap satu daripadanya. Qubit ruang kerja ini muncul di dalam kotak yang mewakili implementasi Gate untuk mencadangkan bahawa ia adalah baharu, dan oleh itu merupakan sebahagian daripada kos implementasi ini.

Untuk Gate AND dan OR kita juga mempunyai dua Qubit yang tersisa, selain daripada Qubit output. Sebagai contoh, di dalam kotak dalam gambar rajah yang mewakili simulasi Gate AND, dua Qubit teratas ditinggalkan dalam keadaan $\vert a\rangle$ dan $\vert b\rangle.$ Qubit-qubit ini digambarkan sebagai kekal di dalam kotak kerana ia tidak lagi diperlukan dan bukan sebahagian daripada output. Ia boleh diabaikan buat masa ini, walaupun kita akan kembali memberi perhatian kepada ia tidak lama lagi.

Gate Boolean yang tinggal, iaitu Gate NOT, termasuk dalam set lalai Gate kuantum kita, jadi kita tidak memerlukan simulasi untuk Gate ini.

Simulasi Gate demi Gate litar Boolean

Sekarang andaikan kita mempunyai litar Boolean biasa bernama $C,$ terdiri daripada Gate AND, OR, NOT, dan FANOUT, dan mempunyai $n$ bit input dan $m$ bit output. Biarkan $t = \operatorname{size}(C)$ ialah bilangan Gate dalam $C,$ dan mari kita beri nama $f$ kepada fungsi yang $C$ kira, yang mengambil bentuk

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

untuk $\Sigma = \{0,1\}.$

Sekarang pertimbangkan apa yang berlaku apabila kita melalui Gate AND, OR, dan FANOUT bagi $C$ satu persatu, menggantikan setiap satu dengan simulasi yang sepadan yang dihuraikan di atas, termasuk penambahan Qubit ruang kerja yang diperlukan. Mari kita namakan litar yang dihasilkan $R,$ dan mari kita urutkan Qubit $R$ supaya $n$ bit input $C$ berkaitan dengan $n$ Qubit teratas $R$ dan Qubit ruang kerja berada di bawah.

Di sini, $k$ adalah bilangan Qubit ruang kerja yang diperlukan — satu untuk setiap Gate AND, OR, dan FANOUT bagi $C$ — dan $g$ adalah fungsi berbentuk $g:\Sigma^n \rightarrow \Sigma^{n+k-m}$ yang menggambarkan keadaan Qubit yang tersisa yang dicipta oleh simulasi Gate selepas $R$ dijalankan. Dalam rajah, Qubit yang berkaitan dengan output $f(x)$ berada di atas dan Qubit yang tersisa yang menyimpan $g(x)$ berada di bawah. Kita boleh memaksa ini berlaku jika kita mahu dengan menyusun semula Qubit menggunakan Gate SWAP, yang boleh dilaksanakan dengan tiga Gate controlled-NOT seperti ini:

Seperti yang akan kita lihat dalam bahagian seterusnya, sebenarnya tidak penting untuk menyusun semula Qubit output seperti ini, tetapi ia cukup mudah untuk dilakukan jika kita memilih.

Fungsi $g$ yang menggambarkan keadaan klasik Qubit yang tersisa ditentukan oleh litar $C,$ tetapi kita sebenarnya tidak perlu terlalu risau tentangnya; kita tidak peduli secara khusus keadaan Qubit ini apabila pengiraan selesai. Huruf $g$ datang selepas $f,$ jadi ia adalah nama yang munasabah untuk fungsi ini atas alasan itu, tetapi ada sebab yang lebih baik untuk memilih nama $g$ — ia singkatan untuk sampah.

Membersihkan sampah

Jika satu-satunya minat kita adalah menilai fungsi $f$ yang dikira oleh litar Boolean $C$ yang diberikan dengan litar kuantum, kita tidak perlu pergi lebih jauh daripada simulasi Gate demi Gate yang baru dihuraikan. Ini bermakna, selain output fungsi, kita akan mempunyai banyak sampah yang tertinggal.

Namun, ini tidak mencukupi jika kita ingin melaksanakan pengiraan klasik sebagai subrutin dalam pengiraan kuantum yang lebih besar, kerana Qubit sampah tersebut akan menimbulkan masalah. Fenomena gangguan adalah sangat penting dalam algoritma kuantum, dan Qubit sampah boleh merosakkan corak gangguan yang diperlukan untuk menjadikan algoritma kuantum berfungsi.

Nasib baik, tidak sukar untuk membersihkan sampah, begitu kata orang. Kuncinya adalah menggunakan fakta bahawa kerana $R$ adalah litar kuantum, kita boleh menjalankannya secara songsang, dengan hanya menggantikan setiap Gate dengan inversnya dan menggunakannya dalam urutan terbalik, dengan itu memperoleh litar kuantum untuk operasi $R^{\dagger}.$ Gate Toffoli, Gate CNOT, dan Gate NOT sebenarnya merupakan inversnya sendiri, jadi menjalankan $R$ secara songsang hanyalah perkara menggunakan Gate dalam urutan terbalik — tetapi secara lebih umum mana-mana litar kuantum boleh dibalikkan seperti yang baru dihuraikan.

Khususnya, apa yang boleh kita lakukan adalah menambah $m$ Qubit lagi (mengingat bahawa fungsi $f$ mempunyai $m$ bit output), menggunakan Gate CNOT untuk menyalin output $R$ ke atas Qubit ini, dan membalikkan $R$ untuk membersihkan sampah. Rajah berikut menggambarkan litar yang dihasilkan dan menghuraikan tindakannya ke atas keadaan asas piawai.

Jika kita meletakkan kotak di sekeliling keseluruhan litar dan menamakannya $Q,$ ia kelihatan seperti ini:

Memandangkan $C$ mempunyai $t$ Gate, litar $Q$ akan mempunyai $O(t)$ Gate.

Jika kita mengabaikan $k$ Qubit ruang kerja tambahan, apa yang kita ada adalah litar $Q$ yang berfungsi persis seperti Gate pertanyaan untuk fungsi $f.$ Jika kita hanya ingin mengira fungsi $f$ pada sesetengah rentetan $x,$ kita boleh menetapkan $y = 0^m$ dan nilai yang dihasilkan $f(x)$ akan muncul pada $m$ Qubit bawah — atau kita boleh memasukkan keadaan yang berbeza ke dalam $m$ Qubit bawah jika kita mahu (mungkin untuk memanfaatkan kickback fasa, seperti dalam algoritma Deutsch atau Deutsch-Jozsa).

Ini bermakna bahawa untuk mana-mana algoritma pertanyaan, jika kita mempunyai litar Boolean yang mengira fungsi input, kita boleh menggantikan setiap Gate pertanyaan dengan implementasi litar untuknya, dan algoritma pertanyaan akan berfungsi dengan betul.

Perhatikan bahawa Qubit ruang kerja diperlukan untuk menjadikan proses ini berfungsi, tetapi ia dikembalikan ke keadaan awalnya setelah litar gabungan dilaksanakan. Ini membolehkan Qubit ini digunakan semula sebagai Qubit ruang kerja untuk tujuan lain. Terdapat juga strategi yang diketahui untuk mengurangkan bilangan Qubit ruang kerja yang diperlukan (yang datang dengan kos menjadikan litar lebih besar), tetapi kita tidak akan membincangkan strategi-strategi tersebut di sini.

Melaksanakan fungsi boleh songsang

Pembinaan yang baru dihuraikan membolehkan kita mensimulasikan mana-mana litar Boolean dengan litar kuantum dengan cara yang bebas sampah. Jika $C$ adalah litar Boolean yang melaksanakan fungsi $f:\Sigma^n \rightarrow \Sigma^m,$ maka kita memperoleh litar kuantum $Q$ yang beroperasi seperti berikut ke atas keadaan asas piawai.

$$Q \bigl( \vert y \rangle \vert 0^k \rangle \vert x\rangle\bigr) = \vert y \oplus f(x) \rangle \vert 0^k \rangle \vert x\rangle$$

Nombor $k$ menunjukkan berapa banyak Qubit ruang kerja yang diperlukan secara keseluruhan. Ini mencukupi untuk tujuan kursus ini, tetapi adalah mungkin untuk mengambil metodologi ini selangkah lebih jauh apabila fungsi $f$ itu sendiri boleh disongsangkan.

Untuk lebih tepat, andaikan fungsi $f$ mengambil bentuk $f:\Sigma^n \rightarrow \Sigma^n,$ dan andaikan juga terdapat fungsi $f^{-1}$ sedemikian rupa sehingga $f^{-1}(f(x)) = x$ untuk setiap $x\in\Sigma^n$ (yang semestinya unik apabila wujud). Ini bermakna operasi yang mengubah $\vert x \rangle$ menjadi $\vert f(x) \rangle$ untuk setiap $x\in\Sigma^n$ adalah unitari, jadi kita mungkin berharap untuk membina litar kuantum yang melaksanakan operasi unitari yang ditakrifkan oleh

$$U \vert x \rangle = \vert f(x) \rangle$$

untuk setiap $x\in\Sigma^n.$

Untuk lebih jelas, fakta bahawa ini adalah operasi unitari bergantung kepada $f$ yang boleh disongsangkan — ia bukan unitari apabila $f$ tidak boleh disongsangkan. Mengabaikan Qubit ruang kerja, $U$ berbeza daripada operasi yang litar $Q$ laksanakan kerana kita tidak menyimpan salinan input dan menXOR-kannya kepada rentetan sewenang-wenang, kita menggantikan $x$ dengan $f(x).$

Soalannya ialah: apabila $f$ boleh disongsangkan, bolehkah kita melakukan ini?

Jawapannya adalah ya, dengan syarat kita dibenarkan menggunakan Qubit ruang kerja dan, selain daripada mempunyai litar Boolean yang mengira $f,$ kita juga mempunyai satu yang mengira $f^{-1}.$ Jadi, ini bukan jalan pintas untuk menyongsangkan fungsi secara pengiraan apabila kita belum tahu cara melakukan itu! Gambar rajah berikut menggambarkan bagaimana ia boleh dilakukan dengan menggabungkan dua litar kuantum, $Q_f$ dan $Q_{f^{-1}},$ yang diperoleh secara individu untuk fungsi $f$ dan $f^{-1}$ melalui kaedah yang dihuraikan di atas, bersama-sama dengan $n$ Gate swap, mengambil $k$ sebagai maksimum bilangan Qubit ruang kerja yang diperlukan oleh $Q_f$ dan $Q_{f^{-1}}.$