Latihan 4.29 dari Komputasi Quantum dan Informasi Quantum oleh Nielsen dan Chuang membuat saya bingung.

Temukan sirkuit yang berisi Toffoli, CNOT dan gerbang qubit tunggal yang mengimplementasikan gerbang (untuk ), tanpa menggunakan qubit kerja.$O(n^2)$$C^n(X)$$n > 3$

Saya sudah menemukan bahwa ini tidak dapat dilakukan secara klasik .

Saya telah menemukan cara untuk melakukannya dengan gerbang yang tepat secara eksponensial (sarang konstruksi kontrol-ganda-dari-kontrol-tunggal-dan-kuadrat-dalam-operasi dalam dirinya sendiri kali).$O(2^n)$$n-2$

Saya sudah mencoba menyamaratakan konstruksi di atas menjadi akumulasi kombinasi linear dari operasi yang dikendalikan. Misalnya, jika saya memiliki 3 kontrol yang disebut A dan B dan C dan membuat vektor dari berbagai kasus [0, A, B, C, AB, BC, AC, ABC] maka:

• Menerapkan operasi tanpa syarat menambahkan [1, 1, 1, 1, 1, 1, 1, 1]
• Mengontrol operasi pada A menambahkan [0, 1, 0, 0, 1, 1, 0, 1]
• Xoring A ke C kemudian mengendalikan operasi pada C (kemudian membatalkan xor) akan menambahkan [0, 1, 0, 1, 1, 1, 0, 0]
• Xoring (A dan B) ke C melalui gerbang toffoli kemudian mengendalikan operasi pada C akan menambahkan [0, 0, 0, 1, 1, 1, 1, 0]

Kemudian saya akan mencoba menambahkan (menerapkan root X) dan mengurangi (menerapkan root kuadrat terbalik) berbagai vektor yang dapat saya buat sampai hasilnya keluar sebagai [0, 0, 0, 0, 0, 0, 0, 0, N] .

Tapi saya terus menabrak berbagai dinding, seperti solusi berakhir dengan kelipatan besar (yaitu gerbang yang saya gunakan menjadi tepat secara eksponensial, yang saya pikir adalah tidak-tidak) atau hanya tidak bisa menyelesaikan sistem karena interaksi antara menghasilkan elemen dengan AND / XOR kemudian menyelesaikan dengan + / * menjadi non-standar atau membuat nomor gerbang eksponensial.

Apa saja pendekatan lain untuk dicoba?

Akhirnya saya akhirnya memecahkan ini $O(n)$gerbang. Saya menulis trilogi posting blog di atasnya.

1. Membangun Notar Terkendali Besar (klasik, dengan ancilla)

2. Membangun Peningkatan Besar (klasik, dengan ancilla)

3. Menggunakan Quantum Gates, bukannya Ancilla Bits

Tentu saja akan payah jika Anda menemukan ini dua puluh tahun dari sekarang dan situs web saya sudah lama hilang, jadi langkah-langkah dasarnya mengikuti bentuk gambar yang dijelaskan dengan cepat.

1. Bootstrap Bit Ancilla yang Dapat Dipinjam

Gunakan akar kuadrat dan kebalikannya untuk mengurangi jumlah kontrol maksimum satu, menciptakan kabel yang tidak terlibat untuk setiap operasi. Kemudian secara iteratif pindahkan kontrol dari operasi non-Tidak, dan atur kembali cruft yang menghasilkan gerbang kenaikan besar dan gerbang fase single-qubit.

2. Gunakan Bit Ancilla Tunggal untuk Memotong Operasi menjadi Setengah

Untuk setiap operasi besar, gunakan kabel yang tidak terlibat sebagai bit ancilla yang dipinjam. Gunakan untuk mengubah kenaikan besar dan gerbang yang tidak dikontrol menjadi operasi yang lebih kecil yang masing-masing memiliki sekitar setengah dari kabel yang tidak terlibat. Ulangi dua kali, jika diperlukan agar langkah selanjutnya memiliki ruang kerja yang cukup.

3. Gunakan Banyak Bit Ancilla untuk Menyelesaikan

Untuk setiap operasi yang masih terlalu besar, pinjam banyak kabel yang tidak terlibat sebagai bit ancilla. Gunakan mereka untuk sampai ke gerbang Toffoli atau lebih kecil.

Ketiga langkah itu akan membuat Anda jauh dari gerbang Toffoli, CNOT, dan gerbang qubit tunggal yang sepenuhnya terkendali-tidak-linier. Ada beberapa bagian yang tersirat, seperti cara menggabungkan kontrol ke gerbang kenaikan, tapi itu cukup sederhana.

(Maaf untuk gaya diagram yang tidak konsisten.)