Bagaimana cara membuktikan / menyangkal universalitas untuk satu set gerbang?

Satu set gerbang universal mampu meniru operasi dari jenis gerbang lainnya, diberikan cukup gerbang. Sebagai contoh, satu set universal gerbang kuantum adalah Hadamard (  $H$  ), pergeseran fase $\pi/8$ (  $T$  ), dan gerbang $\mathrm{CNOT}$Bagaimana seseorang menyangkal atau membuktikan universalitas dari serangkaian gerbang seperti $\{H,T\}$ , $\{\mathrm{CNOT},T\}$ , atau $\{\mathrm{CNOT}, H\}$ ?

Universalitas bisa menjadi hal yang sangat halus yang cukup sulit untuk dibuktikan. Biasanya ada dua opsi untuk membuktikannya:

• tunjukkan secara langsung, dengan menggunakan gerbang yang Anda pilih, bagaimana membangun kesatuan sewenang-wenang dengan ukuran sewenang-wenang (tidak ada batasan pada ukuran konstruksi, hanya saja hal itu dapat dilakukan) untuk akurasi sewenang-wenang (pada beberapa ruang sub non-sepele dari Hilbert penuh) ruang).

• tunjukkan bagaimana set gerbang pilihan Anda dapat digunakan untuk membuat ulang (dengan akurasi sewenang-wenang) set universal yang ada.

Sebaliknya, jika Anda ingin menyanggahnya, Anda menunjukkan bahwa efek dari set gerbang Anda selalu dapat disimulasikan oleh model perhitungan yang dianggap lebih rendah, biasanya perhitungan klasik.

Ada beberapa heuristik yang dapat Anda gunakan untuk panduan:

• Anda harus memiliki gerbang multi-qubit di set Anda. Jika semua yang Anda miliki adalah gerbang qubit tunggal, Anda dapat mensimulasikan setiap qubit secara independen di komputer klasik. Jadi, jika kita percaya bahwa komputer kuantum lebih kuat daripada klasik, gerbang qubit tunggal saja tidak universal untuk perhitungan kuantum. Ini mengesampingkan {H, T}.

• Anda harus memiliki gerbang yang menciptakan superposisi. Ini mengesampingkan {CNOT, T}. Sekali lagi, ini adalah perhitungan klasik dengan penambahan fase global yang tidak relevan.

Tentu saja, ini bukan kondisi yang memadai: himpunan {H, S, CNOT} dapat disimulasikan secara efisien juga (lihat teorema Gottesman-Knill). Ini juga harus benar dari {H, CNOT} karena mereka adalah himpunan bagian dan sehingga operasi yang dapat mereka buat tidak lebih dari orang-orang dari himpunan asli.

Salah satu set universal yang menurut saya paling menarik adalah {Toffoli, H} . Selalu terasa mengejutkan bagi saya bahwa ini sudah cukup (terutama jika Anda membandingkan dengan set sebelumnya). Perhatikan bahwa itu tidak melibatkan bilangan kompleks.

$$\left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\ 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{array}\right)$$

Nielsen dan Chuang, hal 191 dari edisi peringatan 10 tahun:

Kami baru saja menunjukkan bahwa matriks kesatuan yang arbitrer pada a $d$-dimensi Hilbert ruang dapat ditulis sebagai produk dari matriks kesatuan dua tingkat. Sekarang kami menunjukkan bahwa gerbang qubit tunggal dan CNOT bersama-sama dapat digunakan untuk mengimplementasikan operasi kesatuan dua tingkat yang sewenang-wenang pada ruang keadaan$n$qubits. Menggabungkan hasil ini kita melihat bahwa gerbang qubit dan CNOT tunggal dapat digunakan untuk mengimplementasikan operasi kesatuan yang sewenang-wenang$n$ qubit dan karenanya bersifat universal untuk perhitungan kuantum.

Kalimat pertama ada hasil yang diterima, jadi Anda harus menunjukkan bahwa kombinasi dari set gerbang Anda dapat menerapkan "operasi kesatuan dua tingkat yang sewenang-wenang". Mengutip Wikipedia:

Secara teknis, ini tidak mungkin karena jumlah kemungkinan gerbang kuantum tidak terhitung, sedangkan jumlah urutan terbatas dari himpunan terbatas dapat dihitung. Untuk mengatasi masalah ini, kami hanya mengharuskan operasi kuantum apa pun dapat didekati dengan urutan gerbang dari himpunan terbatas ini.

Lihat juga tulisan ini .