Universalitas gerbang Toffoli

Mengenai gerbang Toffoli kuantum :

1. apakah itu klasik dan universal, dan jika demikian, mengapa?
2. itu quantumly universal, dan mengapa?

Toffoli bersifat universal untuk komputasi klasik (seperti yang ditunjukkan oleh @Victor). Namun, Toffoli TIDAK universal untuk perhitungan kuantum (kecuali kita memiliki sesuatu yang gila seperti ).$P = BQP$

Agar universal untuk perhitungan kuantum (di bawah definisi biasa), grup yang dihasilkan oleh gerbang Anda harus padat di unitari. Dengan kata lain, diberi sewenang-wenang dan sasaran kesatuan U ada beberapa cara untuk menerapkan jumlah terbatas Anda gerbang kuantum untuk mendapatkan kesatuan U ' sehingga | | U - U ′ | | < ϵ .$\epsilon$$U$$U'$$||U - U'|| < \epsilon$

Toffoli dengan sendirinya jelas tidak universal dalam definisi ini karena selalu mengambil negara dasar ke negara dasar, dan dengan demikian tidak dapat mengimplementasikan sesuatu yang mengambil misalnya. Dengan kata lain, itu tidak dapat membuat superposisi.$|0\rangle \rightarrow \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

Dari artikel wikipedia yang Anda kutip :

Gerbang Toffoli bersifat universal; ini berarti bahwa untuk setiap fungsi boolean f (x1, x2, ..., xm), ada sirkuit yang terdiri dari gerbang Toffoli yang mengambil x1, x2, ..., xm dan beberapa bit tambahan diatur ke 0 atau 1 dan output x1, x2, ..., xm, f (x1, x2, ..., xm), dan beberapa bit tambahan (disebut sampah). Pada dasarnya, ini berarti bahwa seseorang dapat menggunakan gerbang Toffoli untuk membangun sistem yang akan melakukan perhitungan fungsi boolean yang diinginkan dengan cara yang dapat dibalik.

Yang berarti secara sederhana bahwa fungsi boolean apa pun dapat dibangun hanya dengan gerbang Toffoli.

Fungsi Boolean biasanya dibangun dari gerbang OR, AND dan NOT, yang dapat digabungkan untuk membentuk fungsi boolean apa pun. Secara luas diketahui bahwa hal yang sama hanya mungkin dilakukan dengan gerbang NOR atau hanya dengan gerbang NAND.

Gerbang Toffoli dapat diringkas sebagai:

$\rm{Toffoli}(a, b, c) = \begin{cases} (a, b, ¬c) & \mbox{when }a=b=1 \\ (a, b, c) & \mbox{otherwise.}\end{cases}$

Karena output pertama dan kedua selalu sama dengan input pertama dan kedua, kami dapat mempertimbangkannya. Jadi kita punya:

$\rm{Toffoli}'(a, b, c) = \begin{cases} ¬c & \mbox{when }a=b=1 \\ c & \mbox{otherwise.}\end{cases}$

Dengan itu, dimungkinkan untuk mendefinisikan gerbang NAND sebagai:

$\operatorname{NAND}(a, b) = \rm{Toffoli}'(a, b, 1)$

Karena gerbang NAND bersifat universal dan gerbang NAND dapat didefinisikan sebagai gerbang Toffoli, maka gerbang TANDING bersifat universal.

Ada cara lain untuk membuktikan bahwa Toffoli bersifat universal, dengan membangun langsung gerbang AND dan NOT:

$\operatorname{NOT}(x) = \rm{Toffoli}'(1, 1, x)$

$\operatorname{AND}(a, b) = \rm{Toffoli}'(a, b, 0)$

Kemudian, kita dapat membangun gerbang OR menggunakan hukum De Morgan :

$\operatorname{OR}(a, b) = \operatorname{NOT}(\operatorname{AND}(\operatorname{NOT}(a), \operatorname{NOT}(b)) = \rm{Toffoli}'(1, 1, \rm{Toffoli}'(\rm{Toffoli}'(1, 1, a), \rm{Toffoli}'(1, 1, b), 0))$

EDIT, karena pertanyaannya diedit dan cakupannya berubah:

Pertama, saya tidak mengerti komputasi kuantitatif, jadi jika ada yang salah, silakan tambahkan komentar. Saya melakukan sedikit riset untuk mencoba membuat jawaban ini lengkap dan diakhiri dengan ini:

Gerbang Toffoli dapat dibalik (tetapi Toffoli yang digunakan di atas tidak). Ini berarti bahwa perhitungan yang dilakukan dengan itu dapat dibatalkan. Ini adalah:

$(a, b, c) = \rm{Toffoli}(\rm{Toffoli}(a, b, c))$

Yang berarti bahwa untuk setiap tripel (a, b, c) jika Toffoli diterapkan dua kali, input asli didapat sebagai output.

Reversibilitas penting karena gerbang kuantum harus dapat dibalik, sehingga gerbang Toffoli (klasik) dapat digunakan sebagai gerbang kuantum karena hal ini.

Seperti yang diperlihatkan di sini , gerbang Deutsch didefinisikan dengan cara yang sama dengan gerbang Toffoli, tetapi bukannya gerbang klasik, itu adalah gerbang yang kuantitatif:

$\operatorname{Deutsch}(a, b, c) = |a,b,c\rangle \mapsto \begin{cases} i \cos(\theta) |a,b,c\rangle + \sin(\theta) |a,b,1-c\rangle & \mbox{for }a=b=1 \\ |a,b,c\rangle & \mbox{otherwise.}\end{cases}$

Dengan cara ini, gerbang Toffoli adalah kasus khusus dari gerbang Deutsch di mana:

$\rm{Toffoli}(a, b, c) = \operatorname{Deutsch}(\frac{\pi}{2})(a, b, c)$

$\frac{\pi}{2}$

Satu set Tgate kuantum universal dapat diperoleh, jika kita menggabungkan gerbang Toffoli dengan gerbang Hadamard. Inilah yang dilakukan gerbang Deutsch.

Referensi yang menarik dapat ditemukan di sini , di sini dan di sini . Referensi yang mungkin berharga, yang menunjukkan dasar-dasar transformasi Deutsch harus ada di sini , namun tautannya dilindungi kata sandi.