Verifikasi kuantum satu arah

Teori komputasi cluster-state sudah mapan saat ini, menunjukkan bahwa setiap sirkuit BQP dapat dimodifikasi sehingga hanya menggunakan gerbang kuantum qubit tunggal, mungkin dikontrol secara klasik, menyediakan banyak pasokan kondisi yang dikenal sebagai "negara cluster" - yang adalah sederhana untuk menghasilkan keadaan stabil.

Pertanyaan saya adalah: apakah gagasan serupa diketahui untuk verifikasi kuantum - yaitu, bisakah seseorang mengganti sirkuit QMA dengan gerbang 1-qubit yang dikontrol secara klasik, mungkin menggunakan "keadaan khusus"? Setidaknya pada awalnya, saya tidak jelas mengapa negara gugus bahkan dapat bekerja dalam kasus ini.

quantum-computing Lior Eldar
sumber

Jika saya mengerti dengan benar, apakah masalah yang ada di QMA Merlin memberi Anda bukti kuantum yang harus Anda masukkan ke dalam model? Dengan kata lain, jika itu QCMA bukan QMA, di mana Merlin hanya memberikan Anda string klasik, maka kita bisa menggunakan hasil yang diketahui untuk BQP, kan?

Robin Kothari

Ya itu benar. Terima kasih telah membuat perbedaan ini.

Lior Eldar

Untuk memulainya, seseorang dapat mengajukan pertanyaan yang sama untuk BQP: Bisakah kita melakukan perhitungan kuantum apa pun yang diberikan kekuatan untuk melakukan pengukuran 1-qubit, dan diberi pasokan status gugus yang tidak terpercaya (atau kondisi lain yang sesuai)?

Norbert Schuch

Jawaban:

Dimungkinkan untuk membatasi verifier QMA ke pengukuran single-qubit dan klasik pra dan postprocessing (dengan acak) sambil menjaga kelengkapan QMA.

Untuk mengetahui alasannya, ambil kelas mana saja dari Hamiltonian local QMA-complete pada qubit. Dengan menambahkan konstan agar dan rescaling dengan faktor, Hamiltonian dapat dibawa ke dalam bentuk di mana , , dan $k$ $\mathrm{poly}(n)$ $1/\mathrm{poly}(n)$

H = \sum_{saya} w_{saya} h_{saya},

$H=\sum_i w_i h_i\ ,$

w_{i} > 0

$w_i>0$

\sum_{i} w_{i} = 1

$\sum_i w_i=1$

, di mana

adalah produk dari Paulis. Memperkirakan nilai eigen terkecil

hingga akurasi

masih QMA-keras.

h_{i} = \frac{1}{2} (I d \pm P_{i})

$h_i = \tfrac12(\mathrm{Id}\pm P_i)$

P_{i}

$P_i$

H

$H$

1 / p o l y (n)

$1/\mathrm{poly}(n)$

Kita sekarang dapat membangun sirkuit yang hanya menggunakan pengukuran qubit tunggal yang, diberi status , menerima dengan probabilitas (yang oleh konstruksi adalah antara dan ). Untuk tujuan ini, pertama secara acak memilih salah satu dari 's sesuai dengan distribusi . Kemudian, mengukur masing-masing Paulis di , dan mengambil paritas dari hasil, yang sekarang berhubungan dengan $|\psi\rangle$ $1-\langle\psi|H|\psi\rangle$ $0$ $1$ $i$ $w_i$ $P_i$ $\pi$ $\langle\psi|h_i|\psi\rangle$ melalui Sirkuit sekarang output, dan output karena itu didistribusikan sesuai dengan.

⟨ ψ | h_{i} | ψ ⟩ = \frac{1}{2} (1 \pm (- 1)^{π}) \in {0, 1} .

$\langle\psi|h_i|\psi\rangle = \tfrac12(1\pm (-1)^\pi)\in\{0,1\}\ .$

1 - ⟨ ψ | h_{i} | ψ ⟩

$1-\langle\psi|h_i|\psi\rangle$

⟨ ψ | H | ψ ⟩

$\langle\psi|H|\psi\rangle$

Ini, jika kita memilih contoh-ya dari masalah Hamiltonian lokal (lengkap QMA), ada status sehingga verifier ini akan menerima dengan beberapa probabilitas , sementara jika tidak setiap negara akan ditolak dengan probabilitas , dengan . Varian QMA dimana verifier dibatasi untuk pengukuran satu-qubit oleh karena itu QMA-complete untuk beberapa $|\psi\rangle$ $\ge a$ $\le b$ $a-b>1/\mathrm{poly}(n)$ $1/\mathrm{poly}(n)$ celah. Akhirnya, versi QMA ini dapat diamplifikasi hanya dengan menggunakan teknik amplifikasi konvensional untuk QMA, yang akhirnya membuktikan QMA-nya bebas dari celah (dalam kisaran yang sama dengan QMA).

Norbert Schuch
sumber

Bisakah Anda memberikan penjelasan atau referensi singkat mengapa masalah memperkirakan nilai eigen terkecil

masih QMA-keras? Terima kasih!

H

$H$

Henry Yuen

Kita mulai dari Hamiltonian

yang masalah ini [hingga

] selesai QMA, mengubahnya menjadi Hamiltonian

, di mana

dan

, jadi perkirakan energi GS dari

H^{'}

$H'$

ϵ = 1 / p o l y (n)

$\epsilon=1/\mathrm{poly}(n)$

H = x (H^{'} + y)

$H=x(H'+y)$

x = 1 / p o l y (n)

$x=1/\mathrm{poly}(n)$

y = p o l y (n)

$y=\mathrm{poly}(n)$

H

$H$ hingga akurasi

masih QMA-hard.

x ϵ = 1 / p o l y (n)

$x\epsilon=1/\mathrm{poly}(n)$

Norbert Schuch

Dapatkah Anda selalu menganggap bahwa

adalah proyektor ke sebuah ruang eigen dari Pauli Hamiltonian?

h_{i}

$h_i$

Henry Yuen

Nah, setiap istilah

dalam Hamiltonian asli dapat ditulis sebagai jumlah dari

produk Pauli (

untuk

), dan perumus setiap Pauli produk

adalah

h^{'}

$h'$

4^{k}

$4^k$

4^{k} = p o l y (n)

$4^k=\mathrm{poly}(n)$

k = O (\log (n))

$k=O(\log(n))$

P_{i}

$P_i$

t r [P_{i} h^{'}] / 2^{k} \leq ‖ h^{'} ‖_{\infty}

$\mathrm{tr}[P_ih']/2^k\le \|h'\|_\infty$

Norbert Schuch

Interpretasi saya terhadap pertanyaan ini adalah yang Anda tanyakan, dapatkah kita berasumsi bahwa rangkaian verifikasi untuk protokol QMA hanya menggunakan pengukuran qubit tunggal? (Gagasannya adalah bahwa prover mengirimi Anda bukti kuantum dan status gugus kuantum yang diperlukan untuk mengimplementasikan sirkuit verifikasi asli dengan "komputasi kuantum satu arah.")

Masalahnya, tentu saja, adalah bahwa prover mungkin tidak mengirimi Anda status gugus yang valid sama sekali. Jadi verifier harus menguji keadaan yang diterima untuk memastikan bahwa itu benar-benar negara cluster. Verifier melakukan ini dengan melakukan pengukuran qubit tunggal dan memeriksa korelasi memenuhi pemeriksaan stabilizer yang diperlukan. Karena pengujian semacam itu merusak negara, perlu ada prosedur di mana verifier diberikan banyak salinan negara, memeriksa sebagian besar dari mereka, dan menggunakan yang acak untuk perhitungan. Apakah jumlah salinannya cukup?

Saya tidak berpikir ini adalah teorema yang dikenal. Saya tidak melihat contoh tandingan yang jelas (dengan pemikiran satu menit), jadi mungkin bisa dipercaya. Teknologi bukti yang dikenal pada kondisi pengujian sepertinya cukup untuk memeriksa hal ini. Sebagai contoh, lihat makalah Matthew McKague arXiv: 1010.1989 [quant-ph]. Jika bukti Anda berfungsi, kirim kertas ke QIP (tenggat 5 Oktober)!

Anonim
sumber

Mungkin saya salah memahami pertanyaan ini. Jika Anda bertanya apakah Anda dapat menerapkan rangkaian verifier untuk masalah di QMA menggunakan perhitungan berbasis pengukuran, di mana Merlin memasok lapisan input, dan Arthur memasok semua qubit lebih lanjut dalam status sumber daya dan melibatkan kedua set qubit sebelum pengukuran dimulai, kemudian jawabannya sepele ya. Ini mengikuti langsung dari kenyataan bahwa setiap sirkuit kuantum dapat diimplementasikan sebagai perhitungan berbasis pengukuran apakah Anda peduli dengan input klasik atau kuantum.

Anda akan melihat bahwa di sebagian besar makalah pada situs input perhitungan berbasis pengukuran umumnya diidentifikasi secara terpisah dari situs lain, dan inilah sebabnya (yaitu khusus untuk menangani kasus input kuantum).

Joe Fitzsimons
sumber

Sebenarnya saya tidak jelas tentang hal ini. Dalam makalah perhitungan berbasis pengukuran yang saya lihat, transformasi adalah dari setiap sirkuit BQP dengan input klasik, ke sirkuit komputasi satu arah mulai dari keadaan cluster. Artinya, BUKAN digambarkan sebagai transformasi yang mengambil sirkuit kesatuan U yang sewenang-wenang ke sirkuit berbasis pengukuran U_1, terlepas dari inputnya. Sementara pertanyaan kompleksitas yang saya tanyakan, sekarang diselesaikan setelah jawaban Norbert, saya masih ingin memahami hal ini.

Lior Eldar

@LiorEldar: Maka Anda harus melihat kertas Raussendorf dan Briegel asli atau Raussendorf, Browne dan Briegel. Mereka secara eksplisit membangun sirkuit satu gerbang pada suatu waktu, menunjukkan bahwa setiap pola pengukuran mengimplementasikan gerbang yang diberikan pada lapisan input, yang dapat dalam keadaan arbitrer. Anda pasti dapat menerapkan sirkuit arbitrer pada input sewenang-wenang.

Joe Fitzsimons

Lior sebenarnya ada di sekitar sini di Aachen ketika kami membahas hal ini, dan salah satu cara untuk memahami pertanyaan ini didasarkan pada ide ini: Bisakah Merlin memberikan bukti yang dibangun ke dalam keadaan kluster (tidak terpercaya), dan Arthur menggunakan pengukuran satu-qubitnya untuk memverifikasi klaster atau verifikasi buktinya menggunakan MBQC? (Mungkin orang bisa menggunakan ide yang sama seperti di comp buta. Di mana koreksi kesalahan digunakan?) Sayangnya, orang tidak perlu ide bagus ini untuk membuktikan kekerasan QMA. ;-( Namun, saya percaya ini masih merupakan pertanyaan yang menarik untuk dipahami apakah ini akan berhasil, dan Anda akan menjadi ahli untuk menunjukkan ini :-)

Norbert Schuch

@Lior: Jika Anda ingin menggunakan MBQC untuk memverifikasi input, Anda tentu saja juga perlu 2-qubit gates selain pengukuran satu-qubit (karena Anda harus melibatkan input dengan keadaan cluster Anda).

Norbert Schuch

@ Jo: BTW, pertanyaan yang sama untuk BQP (bisakah kita menjalankan BQP menggunakan pengukuran 1-qubit menggunakan keadaan cluster yang tidak dipercaya) tentu saja masih terbuka, dan rasanya bagi saya bahwa ide yang digunakan dalam perhitungan buta mungkin adalah cara untuk pergi .

Norbert Schuch