Komputasi klasik di komputer kuantum

Sekarang kita akan beralih ke implementasi algoritma klasik di komputer kuantum. Kita akan lihat bahwa komputasi apa pun yang bisa dilakukan dengan sirkuit Boolean klasik juga bisa dilakukan oleh sirkuit kuantum dengan biaya komputasi asimtotik yang serupa. Selain itu, ini bisa dilakukan dengan cara yang "bersih" seperti yang akan dijelaskan segera, yang merupakan syarat penting agar komputasi ini bisa digunakan sebagai subrutin dalam komputasi kuantum yang lebih besar.

Mensimulasikan sirkuit Boolean dengan sirkuit kuantum

Sirkuit Boolean terdiri dari gate AND, OR, NOT, dan FANOUT. Untuk mensimulasikan sirkuit Boolean dengan sirkuit kuantum, kita mulai dengan menunjukkan cara setiap dari keempat gate ini bisa disimulasikan oleh gate kuantum. Setelah itu selesai, mengonversi sirkuit Boolean tertentu ke sirkuit kuantum tinggal mensimulasikan satu gate dalam satu waktu. Kita hanya perlu gate NOT, gate controlled-NOT, dan gate Toffoli untuk melakukan ini, yang semuanya adalah operasi deterministik sekaligus operasi uniter.

Gate Toffoli

Gate Toffoli bisa juga dideskripsikan sebagai gate controlled-controlled-NOT, yang aksinya pada status basis standar ditunjukkan pada gambar berikut.

Mengingat bahwa kita menggunakan konvensi pengurutan Qiskit, di mana qubit diurutkan dengan signifikansi yang meningkat dari atas ke bawah, representasi matriks gate ini adalah sebagai 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 adalah bahwa gate ini pada dasarnya merupakan query gate untuk fungsi AND, dalam arti bahwa gate ini mengikuti pola yang kita lihat di pelajaran sebelumnya untuk implementasi query gate uniter dari fungsi sembarang yang memiliki input dan output berupa string biner.

Gate Toffoli tidak termasuk dalam set gate default yang dibahas sebelumnya di pelajaran ini, tetapi memungkinkan untuk membangun gate Toffoli dari gate $H,$ $T,$ $T^{\dagger},$ dan CNOT sebagai berikut.

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

Satu gate Toffoli, yang digunakan bersama dengan beberapa gate NOT, bisa mengimplementasikan gate AND dan OR, dan gate FANOUT bisa dengan mudah diimplementasikan menggunakan gate controlled-NOT, seperti yang disarankan oleh diagram berikut.

Dalam ketiga kasus tersebut, qubit tempat gate AND, OR, dan FANOUT bekerja masuk dari kiri sebagai input, dan kita juga memerlukan satu qubit workspace yang diinisialisasi ke status nol untuk masing-masing gate. Qubit workspace ini muncul di dalam kotak yang mewakili implementasi gate untuk menunjukkan bahwa qubit ini baru, dan oleh karena itu merupakan bagian dari biaya implementasi ini.

Untuk gate AND dan OR, kita juga memiliki dua qubit yang tersisa, selain qubit output. Misalnya, di dalam kotak dalam diagram yang mewakili simulasi gate AND, dua qubit teratas dibiarkan dalam status $\vert a\rangle$ dan $\vert b\rangle.$ Qubit ini diilustrasikan sebagai tetap berada di dalam kotak karena tidak lagi dibutuhkan dan bukan bagian dari output. Qubit ini bisa diabaikan untuk sementara, meskipun kita akan memperhatikannya kembali sebentar lagi.

Gate Boolean yang tersisa, gate NOT, sudah termasuk dalam set gate kuantum default kita, jadi kita tidak memerlukan simulasi untuk yang satu ini.

Simulasi gate demi gate dari sirkuit Boolean

Sekarang misalkan kita memiliki sirkuit Boolean biasa bernama $C,$ yang terdiri dari gate AND, OR, NOT, dan FANOUT, dan memiliki $n$ bit input dan $m$ bit output. Misalkan $t = \operatorname{size}(C)$ adalah jumlah gate dalam $C,$ dan kita beri nama $f$ pada fungsi yang dihitung oleh $C,$ yang berbentuk

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

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

Sekarang pertimbangkan apa yang terjadi ketika kita melewati gate AND, OR, dan FANOUT dari $C$ satu per satu, mengganti masing-masing dengan simulasi yang sesuai yang dijelaskan di atas, termasuk penambahan qubit workspace yang diperlukan. Kita beri nama sirkuit yang dihasilkan $R,$ dan kita urutkan qubit dari $R$ sehingga $n$ bit input dari $C$ bersesuaian dengan $n$ qubit teratas dari $R$ dan qubit workspace ada di bawah.

Di sini, $k$ adalah jumlah qubit workspace yang diperlukan — satu untuk setiap gate AND, OR, dan FANOUT dari $C$ — dan $g$ adalah fungsi berbentuk $g:\Sigma^n \rightarrow \Sigma^{n+k-m}$ yang mendeskripsikan status qubit sisa yang dibuat oleh simulasi gate setelah $R$ dijalankan. Dalam gambar, qubit yang bersesuaian dengan output $f(x)$ ada di atas dan qubit sisa yang tersimpan $g(x)$ ada di bawah. Kita bisa memaksanya terjadi seperti ini jika mau dengan mengatur ulang qubit menggunakan gate SWAP, yang bisa diimplementasikan dengan tiga gate controlled-NOT seperti ini:

Seperti yang akan kita lihat di bagian berikutnya, sebenarnya tidak terlalu penting untuk mengatur ulang qubit output seperti ini, tetapi cukup mudah dilakukan jika kita mau.

Fungsi $g$ yang mendeskripsikan status klasik qubit sisa ditentukan oleh sirkuit $C,$ tetapi kita sebenarnya tidak perlu terlalu khawatir tentangnya; kita tidak peduli secara spesifik tentang status qubit ini saat komputasi selesai. Huruf $g$ datang setelah $f,$ jadi ini adalah nama yang masuk akal untuk fungsi ini karena alasan itu, tetapi ada alasan yang lebih baik untuk memilih nama $g$ — singkatan dari garbage (sampah).

Membersihkan sampah

Jika satu-satunya minat kita adalah mengevaluasi fungsi $f$ yang dihitung oleh sirkuit Boolean $C$ tertentu dengan sirkuit kuantum, kita tidak perlu melanjutkan lebih jauh dari simulasi gate demi gate yang baru saja dijelaskan. Ini berarti bahwa, selain output fungsi, kita akan memiliki banyak sampah yang tersisa.

Namun, ini tidak cukup baik jika kita ingin melakukan komputasi klasik sebagai subrutin dalam komputasi kuantum yang lebih besar, karena qubit sampah tersebut akan menimbulkan masalah. Fenomena interferensi sangat penting bagi algoritma kuantum, dan qubit sampah bisa merusak pola interferensi yang dibutuhkan agar algoritma kuantum bekerja.

Untungnya, membersihkan sampah tidak sulit. Kuncinya adalah memanfaatkan fakta bahwa karena $R$ adalah sirkuit kuantum, kita bisa menjalankannya secara terbalik, cukup dengan mengganti setiap gate dengan inversnya dan menerapkannya dalam urutan terbalik, sehingga mendapatkan sirkuit kuantum untuk operasi $R^{\dagger}.$ Gate Toffoli, gate CNOT, dan gate NOT sebenarnya merupakan invers dari dirinya sendiri, sehingga menjalankan $R$ secara terbalik sebenarnya hanya soal menerapkan gate dalam urutan terbalik — tetapi secara lebih umum sirkuit kuantum mana pun bisa dibalik seperti yang baru saja dijelaskan.

Secara khusus, yang bisa kita lakukan adalah menambahkan $m$ qubit lagi (mengingat bahwa fungsi $f$ memiliki $m$ bit output), menggunakan gate CNOT untuk menyalin output dari $R$ ke qubit ini, dan membalik $R$ untuk membersihkan sampah. Gambar berikut mengilustrasikan sirkuit yang dihasilkan dan mendeskripsikan aksinya pada status basis standar.

Jika kita menaruh kotak di seluruh sirkuit dan menyebutnya $Q,$ tampilannya seperti ini:

Mengingat bahwa $C$ memiliki $t$ gate, sirkuit $Q$ akan memiliki $O(t)$ gate.

Jika kita mengabaikan $k$ qubit workspace tambahan, yang kita miliki adalah sirkuit $Q$ yang berfungsi persis seperti query gate untuk fungsi $f.$ Jika kita hanya ingin menghitung fungsi $f$ pada string $x$ tertentu, kita bisa mengatur $y = 0^m$ dan nilai $f(x)$ yang dihasilkan akan muncul pada $m$ qubit terbawah — atau kita bisa memasukkan status yang berbeda ke $m$ qubit terbawah jika mau (mungkin untuk memanfaatkan phase kickback, seperti dalam algoritma Deutsch atau Deutsch-Jozsa).

Ini berarti bahwa untuk algoritma query mana pun, jika kita memiliki sirkuit Boolean yang menghitung fungsi input, kita bisa mengganti setiap query gate dengan implementasi sirkuitnya, dan algoritma query akan berfungsi dengan benar.

Perlu dicatat bahwa qubit workspace diperlukan untuk membuat proses ini berjalan, tetapi qubit tersebut dikembalikan ke status awalnya setelah sirkuit gabungan dieksekusi. Ini memungkinkan qubit ini digunakan kembali sebagai qubit workspace untuk tujuan lain. Ada juga strategi yang diketahui untuk mengurangi jumlah qubit workspace yang diperlukan (yang memerlukan biaya membuat sirkuit lebih besar), tetapi kita tidak akan membahas strategi tersebut di sini.

Mengimplementasikan fungsi invertibel

Konstruksi yang baru saja dijelaskan memungkinkan kita mensimulasikan sirkuit Boolean mana pun dengan sirkuit kuantum secara bebas sampah. Jika $C$ adalah sirkuit Boolean yang mengimplementasikan fungsi $f:\Sigma^n \rightarrow \Sigma^m,$ maka kita mendapatkan sirkuit kuantum $Q$ yang beroperasi sebagai berikut pada status basis standar.

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

Angka $k$ menunjukkan berapa banyak qubit workspace yang diperlukan secara total. Ini cukup untuk tujuan kursus ini, tetapi memungkinkan untuk mengambil metodologi ini satu langkah lebih jauh ketika fungsi $f$ itu sendiri invertibel.

Lebih tepatnya, misalkan fungsi $f$ berbentuk $f:\Sigma^n \rightarrow \Sigma^n,$ dan juga misalkan ada fungsi $f^{-1}$ sedemikian sehingga $f^{-1}(f(x)) = x$ untuk setiap $x\in\Sigma^n$ (yang pasti unik ketika ada). Ini berarti bahwa operasi yang mentransformasi $\vert x \rangle$ menjadi $\vert f(x) \rangle$ untuk setiap $x\in\Sigma^n$ adalah uniter, jadi kita mungkin berharap bisa membangun sirkuit kuantum yang mengimplementasikan operasi uniter yang didefinisikan oleh

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

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

Untuk memperjelas, fakta bahwa ini adalah operasi uniter bergantung pada $f$ yang invertibel — ini bukan uniter ketika $f$ tidak invertibel. Mengabaikan qubit workspace, $U$ berbeda dari operasi yang diimplementasikan sirkuit $Q$ karena kita tidak menyimpan salinan input dan meng-XOR-nya ke string sembarang, kita mengganti $x$ dengan $f(x).$

Pertanyaannya adalah: ketika $f$ invertibel, bisakah kita melakukan ini?

Jawabannya ya, asalkan kita diizinkan menggunakan qubit workspace dan, selain memiliki sirkuit Boolean yang menghitung $f,$ kita juga memiliki satu yang menghitung $f^{-1}.$ Jadi, ini bukan jalan pintas untuk menginversi fungsi secara komputasional ketika kita belum tahu cara melakukannya! Diagram berikut mengilustrasikan cara melakukannya dengan menggabungkan dua sirkuit kuantum, $Q_f$ dan $Q_{f^{-1}},$ yang diperoleh secara individual untuk fungsi $f$ dan $f^{-1}$ melalui metode yang dijelaskan di atas, bersama dengan $n$ gate swap, dengan mengambil $k$ sebagai maksimum dari jumlah qubit workspace yang diperlukan oleh $Q_f$ dan $Q_{f^{-1}}.$