Apa pembenaran matematis untuk "universalitas" dari set universal gerbang kuantum (CNOT, H, Z, X dan π / 8)?

Dalam jawaban ini saya sebutkan bahwa gerbang CNOT, H, X, Z dan membentuk satu set gerbang universal, yang diberikan dalam jumlah yang cukup dari gerbang dapat secara sewenang-wenang mendekati replikasi setiap gerbang kuantum kesatuan (saya jadi tahu tentang fakta ini dari kuliah EdX Profesor Umesh Vazirani). Tapi, adakah pembenaran matematis untuk ini? Seharusnya ada! Saya mencoba mencari makalah yang relevan tetapi tidak menemukan banyak.$\pi/8$

Jawaban yang Anda sebutkan merujuk pada buku Michael Nielsen dan Isaac Chuang, Komputasi Quantum dan Informasi Quantum (Cambridge University Press), yang memang berisi bukti universalitas gerbang-gerbang ini. (Dalam edisi 2000 saya, ini dapat ditemukan pada hal. 194.) Wawasan utama adalah bahwa gerbang (atau gerbang), bersama dengan gerbang , menghasilkan dua rotasi berbeda pada bola Bloch dengan sudut yang adalah kelipatan irasional . Ini memungkinkan kombinasi dan$T$$\pi/8$$H$$2\pi$$T$$H$ gerbang untuk secara padat mengisi permukaan bola Bloch dan dengan demikian mendekati operator kesatuan satu-qubit.

Bahwa ini dapat dilakukan secara efisien ditunjukkan oleh teorema Solovay-Kitaev . Di sini, "efisien" berarti polinomial dalam , di mana adalah akurasi yang diinginkan. Ini juga terbukti dalam buku Nielsen dan Chuang (Lampiran 3 dalam edisi 2000). Konstruksi eksplisit dapat ditemukan di https://arxiv.org/abs/quant-ph/0505030$\log(1/\epsilon)$$\epsilon$ .

Menggabungkan gerbang CNOT memungkinkan seseorang untuk mendekati unitari multi-qubit yang sewenang-wenang, seperti yang ditunjukkan oleh Barenco et al. dalam Phys. Pendeta A 52 3457 (1995). (Cetakan awal makalah ini dapat ditemukan di https://arxiv.org/abs/quant-ph/9503016 .) Ini juga dibahas dalam Nielsen dan Chuang (hlm. 191 dalam edisi 2000).

Anda bahkan tidak perlu dan X . C N O T , H , dan T = π / 8 sudah cukup.$Z$$X$
$\rm{CNOT}$$H$$T=\pi/8$

$H$$T$
$\rm{CNOT}$$\epsilon>0$$\mathcal{O}(\log^2(1/\epsilon))$

$\epsilon=0$$\pi/2$$\frac{a+ib}{2^n} + \frac{c+id}{2^{n+1/2}}$ , di mana semua variabel adalah bilangan bulat. Hebatnya, paling banyak 1 qubit tambahan diperlukan untuk sintesis yang tepat ini.

Gerbang universal lainnya adalah , dan pada kenyataannya ada satu gerbang yang uniersal: gerbang Deutsch 3-qubit D ( θ ) .$\{{\rm{CCNOT}},H\}$ ${D(\theta)}$