Jumlah minimum CNOT untuk kenaikan 4-qubit pada kisi planar

Baru-baru ini saya bertanya-tanya seberapa tinggi mesin NISQ akan dapat "menghitung". Yang saya maksudkan adalah, mengingat sirkuit kenaikan paling optimal yang dapat Anda buat, berapa kali Anda dapat secara fisik menerapkan sirkuit itu ke qubit dalam keadaan awal rahasia sebelum ada lebih dari 50% peluang bahwa outputnya adalah nilai yang salah.

Untuk itu, saya membutuhkan rangkaian kenaikan yang baik yang benar-benar akan berjalan pada mesin NISQ! Misalnya ini berarti menghormati batasan lokalitas, dan menghitung biaya berdasarkan berapa banyak operasi 2-qubit yang dilakukan (karena itu adalah yang paling berisik). Untuk kesederhanaan, saya akan mengatakan bahwa set gerbang adalah "operasi qubit tunggal + CNOT lokal di grid".

Tampak jelas bagi saya bahwa mesin NISQ harus dapat menerapkan incrementer 3-qubit setidaknya 8 kali (jadi itu kembali ke 0 dan kehilangan hitungan), tapi saya pikir membungkus counter 4-qubit jauh lebih menantang. Jadi fokus pertanyaan ini pada ukuran itu secara khusus.

Incrementer 4-qubit adalah sirkuit yang mempengaruhi permutasi negara $|k\rangle \rightarrow |k + 1\pmod{16}\rangle$ . Nilai $k$ harus disimpan sebagai bilangan bulat biner pelengkap 2s dalam empat qubit. Jika nilainya di bawah superposisi, itu harus tetap koheren setelah menerapkan incrementer (yaitu tidak melibatkan dengan qubit lain kecuali sebagai ruang kerja sementara). Anda dapat menempatkan qubit di mana pun Anda inginkan di grid.

Inilah sirkuit terbaik yang saya temukan. Ini menggunakan 14 CNOT.

Perhatikan bahwa sirkuit ini tidak menggunakan tata letak linier! Itu ditempatkan di grid seperti ini:

0-A-1
  |
  3
  |
  2

Di mana 'A' adalah ancilla yang diinisialisasi dalam kondisi | 0> dan '0', '1', '2', '3' adalah qubit yang menyusun register (dengan '0' adalah bit yang paling tidak signifikan).

Saya memverifikasi sirkuit ini di Quirk menggunakan dualitas saluran-negara dan invers yang dikenal baik .

Jika seseorang memiliki akses ke operasi sqrt-of-CNOT, jumlah operasi 2-qubit dapat diturunkan menjadi 13 dengan menggabungkan dua CNOT dan tiga Ts di area bawah menjadi S-terkontrol.

Jika CNOT memiliki tingkat kesalahan 0,5%, dan semua sumber kesalahan lainnya dapat diabaikan, Anda dapat menerapkan sirkuit ini hampir sepuluh kali sebelum mencapai tingkat kegagalan 50%. Menyiratkan mesin NISQ masuk akal bisa "hampir menghitung sampai sepuluh".