Membatasi entri operator kesatuan ke bilangan real dan set gerbang universal

10

Dalam makalah seminal Bernstein dan Vazirani "Teori Kompleksitas Kuantum", mereka menunjukkan bahwa transformasi kesatuan dimensi dapat secara efisien didekati dengan produk dari apa yang mereka sebut "rotasi dekat-sepele" dan "pergeseran fase dekat-sepele".d

"Rotasi Near-trivial" adalah matriks kesatuan dimensi yang bertindak sebagai identitas pada semua kecuali 2 dimensi, tetapi bertindak sebagai rotasi pada bidang yang direntang oleh dua dimensi tersebut (yaitu memiliki submatrix 2x2 dalam bentuk:d

(cosθ-dosaθdosaθcosθ)

untuk beberapa ).θ

"Pergeseran fase dekat-sepele" adalah matriks kesatuan dimensi yang bertindak sebagai identitas pada semua kecuali 1 dimensi, tetapi menerapkan faktor untuk beberapa ke dimensi satu itu.e i θ θdesayaθθ

Selain itu, mereka menunjukkan bahwa hanya satu sudut rotasi diperlukan (untuk kedua unit rotasi dan fase pergeseran), mengingat bahwa sudut adalah kelipatan irasional dari (BV mengatur sudut ke .2 π Σ j = 1 2 - 2 j2π2πj=12-2j

Makalah-makalah selanjutnya tentang teori kompleksitas kuantum (seperti itu oleh Adleman et al atau Fortnow dan Rogers) mengklaim bahwa hasil BV menyiratkan bahwa komputasi kuantum universal dapat dicapai dengan operator kesatuan yang entri-entrinya ada di .R

Bagaimana ini? Saya dapat memahami bahwa produk dari matriks rotasi hampir trivial akan memberikan Anda matriks kesatuan dengan entri nyata, tetapi bagaimana dengan matriks pergeseran fase?

Yaitu: jika Anda hanya dapat melakukan rotasi dekat-sepele, dan matriks pergeseran fase di mana entri matriks adalah , dapatkah kita secara efisien memperkirakan semua matriks pergeseran fase lainnya?0,±1

Saya menduga bahwa implikasi ini tidak segera jelas, dan bukti yang tepat untuk itu akan menyerupai bukti bahwa gerbang seperti Toffoli Deutsch bersifat universal - atau apakah saya kehilangan sesuatu yang sangat jelas?

Henry Yuen
sumber

Jawaban:

13

Ada Bukti Sederhana bahwa Toffoli dan Hadamard adalah Quantum Universal oleh Dorit Aharonov yang pertama kali menunjukkan bagaimana amplitudo kompleks dapat disimulasikan oleh amplitudo nyata pada ruang Hilbert yang lebih besar dengan satu qubit lagi.

"Hal ini dilakukan dengan menambahkan satu qubit ekstra untuk sirkuit, negara yang menunjukkan apakah negara sistem adalah di bagian nyata atau imajiner dari ruang Hilbert, dan mengganti setiap pintu gerbang kompleks beroperasi pada k qubit oleh nya versi nyata , dilambangkan ˜ U , yang beroperasi pada k qubit yang sama ditambah qubit tambahan. ˜ U didefinisikan oleh:UkU~kU~

~ U | i| 1=-[Im(U)| i]| 0+[U~|saya|0=[Re(U)|saya]|0+[sayam(U)|saya]|1
"U~|saya|1=-[sayam(U)|saya]|0+[Re(U)|saya]|1

Kedua, ia membuktikan universalitas set gerbang {Hadamard, Toffoli}, yang hanya memiliki amplitudo nyata .{0,1,±12}

Martin Schwarz
sumber
Martin terima kasih! Namun, menurut saya teknik Aharonov untuk mengganti kesatuan yang kompleks dengan kesatuan yang nyata bukanlah cara yang sama seperti yang dipertimbangkan Adleman / BV (karena saya tidak dapat menemukan bukti bahwa mereka berpikir seperti ini). Tapi hasilnya Aharanov menarik dan sangat menyenangkan.
Henry Yuen
1
Saya cukup yakin bahwa Adleman / BV menggunakan konstruksi yang menggandakan jumlah qubit daripada hanya menambahkan satu, tetapi itu bekerja sama.
Peter Shor
@ Peter: Konstruksi Rudolph dan Grover bekerja seperti itu, menggunakan dua rebits untuk menyandikan qubit tunggal: quant-ph / 0210187.
Joe Fitzsimons
9

Selain kertas yang Martin tunjukkan kepada Anda, ada makalah sebelumnya oleh Terry Rudolph dan Lov Grover yang menunjukkan bahwa gerbang 2 rebit bersifat universal untuk komputasi kuantum (lihat quant-ph / 0210187 ). Gerbang memiliki semua enteries nyata, dan jika Anda tidak menyadari bahwa rebits adalah qubit di mana amplitudo dibatasi untuk bilangan real. Ini mungkin sumber klaim. Gerbang yang dimaksud dijelaskan dalam makalah ini adalah rotasi Y yang terkontrol.

G(θ)=Y2(θ2)CZ12Y2(θ2)CZ12

Joe Fitzsimons
sumber