Menerapkan gerbang CCCNOT hanya menggunakan gerbang Toffoli

Gerbang CCCNOT adalah gerbang empat bit yang dapat dibalik yang membalik bit keempatnya jika dan hanya jika tiga bit pertama semuanya dalam keadaan .$1$

Bagaimana saya menerapkan gerbang CCCNOT menggunakan gerbang Toffoli? Asumsikan bit dalam ruang kerja dimulai dengan nilai tertentu, 0 atau 1, asalkan Anda mengembalikannya ke nilai itu.

Saya kira apa yang Anda cari adalah sirkuit berikut. Di sini, $b_1,b_2,b_3,b_4 \in \{0,1\}$ , dan $\oplus$ adalah modulo $2$ tambahan .

Di sini, qubit kelima digunakan sebagai pelengkap , atau ancilla qubit . Dimulai pada $|0\rangle$ dan berakhir di $|0\rangle$ ketika sirkuit diterapkan.

Biarkan saya menguraikan bagaimana sirkuit ini bekerja. Idenya adalah untuk pertama-tama memeriksa apakah dua qubit pertama dalam keadaan $|1\rangle$ . Ini dapat dilakukan dengan menggunakan gerbang Toffoli tunggal, dan hasilnya disimpan dalam qubit tambahan. Sekarang, masalahnya berkurang menjadi membalik qubit $4$ , setiap kali qubit $3$ dan qubit tambahan berada di $|1\rangle$ . Ini juga dapat dicapai dengan menggunakan satu aplikasi gerbang Toffoli, yaitu yang tengah di sirkuit yang ditunjukkan di atas. Akhirnya, gerbang Toffoli terakhir berfungsi untuk menghitung hasil sementara yang kami simpan di qubit tambahan, sehingga status qubit ini kembali ke $|0\rangle$ setelah rangkaian diterapkan.

---

Di bagian komentar, muncul pertanyaan apakah mungkin untuk menerapkan sirkuit seperti itu hanya menggunakan gerbang Toffoli, tanpa menggunakan qubit tambahan. Pertanyaan ini bisa dijawab secara negatif, seperti yang akan saya tunjukkan di sini.

Kami ingin menerapkan $\mathrm{CCCNOT}$ -gate, yang bekerja pada empat qubit. Kita dapat menentukan matriks berikut (representasi matriks dari Pauli- $X$ -gate):

$$X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$$ Selain itu, kami menyatakan $N$ berdimensi identitas matriks dengan $I_N$ . Sekarang, kami mengamati bahwa representasi matriks dari $\mathrm{CCCNOT}$ gateway, yang bekerja pada empat qubit, diberikan oleh matriks 16 × $16 \times 16$ berikut : $$\mathrm{CCCNOT} = \begin{bmatrix} I_{14} & 0 \\ 0 & X \end{bmatrix}$$ Oleh karena itu, kita dapat menentukan determinannya: $$\det(\mathrm{CCCNOT}) = -1$$ Sekarang perhatikan representasi matriks dari gerbang Toffoli, yang bekerja pada tiga qubit pertama dari$4$ sistem -qubit. Representasi matriksnya ditulis sebagai (di mana kami menggunakan produk Kronecker dari matriks): $$\mathrm{Toffoli} \otimes I_2 = \begin{bmatrix} I_6 & 0 \\ 0 & X \end{bmatrix} \otimes I_2 = \begin{bmatrix} I_{12} & 0 \\ 0 & X \otimes I_2 \end{bmatrix} = \begin{bmatrix} I_{12} & 0 & 0 \\ 0 & 0 & I_2 \\ 0 & I_2 & 0 \end{bmatrix}$$ Menghitung hasil determinannya: $$\det(\mathrm{Toffoli} \otimes I_2) = 1$$ Gerbang Toffoli juga dapat bertindak pada qubit yang berbeda tentu saja. Misalkan kita membiarkan gerbang Toffoli bertindak pada qubit pertama, kedua dan keempat, di mana qubit keempat adalah target qubit. Kemudian kita mendapatkan representasi matriks baru dari yang ditampilkan di atas dengan menukar kolom yang sesuai dengan keadaan yang hanya berbeda dalam qubit ketiga dan keempat, yaitu, $|0001\rangle$ dengan $|0010\rangle$ , $|0101\rangle$ dengan $|0110\rangle$ , dll Yang penting untuk dicatat di sini, adalah bahwa jumlah swap kolom bahkan, dan karenanya bahwa determinan tetap tidak berubah. Seperti yang kita dapat menulis setiap permutasi qubit sebagai urutan permutasi berturut-turut dari adil$2$ qubit (yaitu,$S_4$ dihasilkan oleh transposisi di$S_4$ ), kami menemukan bahwa untuk semua gerbang Toffoli, diterapkan pada kombinasi kontrol dan target qubit, representasi matriksnya memiliki determinan$1$ .

Hal terakhir yang perlu diperhatikan adalah bahwa determinan bolak-balik dengan perkalian matriks, yaitu, $\det(AB) = \det(A)\det(B)$ , untuk dua matriks $A$ dan $B$ kompatibel dengan perkalian matriks. Oleh karena itu, sekarang menjadi jelas bahwa menerapkan beberapa gerbang Toffoli dalam urutan tidak pernah menciptakan sirkuit yang representasi matriks memiliki yang berbeda penentu dari $1$ , yang khususnya menyiratkan bahwa $\mathrm{CCCNOT}$ -gate tidak dapat diimplementasikan hanya menggunakan gerbang Toffoli pada $4$ qubits.

Pertanyaan yang jelas, sekarang, adalah apa yang berubah ketika kita mengizinkan qubit tambahan. Kami menemukan jawabannya ketika kami menuliskan tindakan $\mathrm{CCCNOT}$ -gate pada sistem $5$ qubit:

$$\mathrm{CCCNOT} \otimes I_2 = \begin{bmatrix} I_{14} & 0 \\ 0 & X \end{bmatrix} \otimes I_2 = \begin{bmatrix} I_{28} & 0 & 0 \\ 0 & 0 & I_2 \\ 0 & I_2 & 0 \end{bmatrix}$$ Jika kita menghitung determinan ini, kita menemukan: $$\det(\mathrm{CCCNOT} \otimes I_2) = 1$$ Oleh karena itu, penentu$\mathrm{CCCNOT}$ -gerbang yang bekerja pada$5$ qubit adalah$1$ , bukannya$-1$ . Inilah sebabnya mengapa argumen sebelumnya tidak valid untuk$5$ qubit, seperti yang telah kita ketahui karena sirkuit yang dibangun secara eksplisit yang diminta OP.