Kompleksitas komputasi optik kuantum

Dalam "Persyaratan untuk perhitungan kuantum" , Bartlett dan Sanders merangkum beberapa hasil yang diketahui untuk perhitungan kuantum variabel kontinu dalam tabel berikut:

Tabel dari Bartlett dan Sanders, 2003

Pertanyaan saya tiga kali lipat:

Sembilan tahun kemudian, bisakah sel terakhir diisi?
Jika kolom ditambahkan dengan judul "Universal for BQP", bagaimana tampilan kolom lainnya?
Bisakah Aaronson dan 95 halaman karya Arkhipov diringkas menjadi baris baru?

quantum-computing Chris Ferrie
sumber

Jawaban Chris Granade menunjukkan bahwa baris KLM pada kolom pengukuran harus "penghitungan foton, pasca pemilihan". Apakah ada yang tahu dari atas kepala mereka apakah skema lain memerlukan pemilihan juga?

Chris Ferrie

Mungkin pertanyaan bodoh, tetapi bukankah fakta bahwa Anda dapat melanggar ketimpangan Bell dengan foton tunggal dan deteksi homodyne bukti bahwa entri terakhir dari tabel tidak dapat disimulasikan secara efisien?

@ MateusAraújo - Bukti paling meyakinkan bahwa kompleksitas komputasi tidak ada hubungannya dengan lokalitas berasal dari dua fakta: (1) bahwa formalisme stabilisator qubit secara klasik dapat disimulasi secara efisien melalui teorema Gottesman-Knill tetapi seseorang dapat melanggar ketidaksetaraan Bell dengan status stabilizer; (2) formalisme stabilisator qutrit juga klasik yang dapat disimulasikan secara efisien tetapi orang juga dapat menemukan variabel tersembunyi lokal yang mereproduksinya.

Chris Ferrie

Beresiko untuk mengurangi lebih jauh dari pertanyaan Anda, tetapi: apakah ia diketahui sistem yang memiliki model variabel-tersembunyi lokal tetapi yang tidak dapat disimulasikan secara efisien? Itu benar-benar akan mengejutkan saya.

@ MateusAraújo - Saya pikir sistem klasik yang kacau akan berhasil, bukan?

Chris Ferrie

Jawaban:

$n$ $\text{poly}(n) \ge m \ge n$

| 1_{n} ⟩ = | 1, \dots, 1, 0, \dots, 0 ⟩ (n 1s) .

$\left|1_n\right>=\left|1,\dots,1,\ 0,\dots,0\right>\quad (n\text{ 1s}).$

m \times m

$m\times m$

(s_{1}, s_{2}, \dots, s_{m})

$(s_1, s_2, \dots, s_m)$

\sum_{i} s_{i} = n

$\sum_i s_i = n$

s_{i} \geq 0

$s_i \ge 0$

i

$i$ . (Sebagian besar definisi ini dapat ditemukan di halaman 18-20 A&A.)

$n$

$1/16^\Gamma$ $\Gamma$

Aaronson mengeksplorasi lebih lanjut kasus optik linear postselected dalam makalah lanjutannya pada # P-hardness of the permanen. Hasil ini sebelumnya dibuktikan oleh Valiant, tetapi Aaronson menyajikan bukti baru berdasarkan teorema KLM. Sebagai catatan, saya menemukan bahwa makalah ini membuat pengenalan yang sangat bagus untuk banyak konsep yang digunakan A&A dalam karya BosonSampling mereka.

Chris Granade
sumber

Jawaban bagus! Jadi tanda x pada kolom terakhir juga harus memiliki catatan kaki atau, lebih tepatnya, menjadi tanda tanya karena kita tidak tahu apakah P = BQP atau tidak?

Chris Ferrie

Terima kasih! Kolom terakhir adalah yang terbaik secara hipotesis, karena kami tidak memiliki bukti bahwa P ≠ BQP. Hasil A&A adalah salah satu hasil terkuat yang pernah saya lihat untuk memisahkan perhitungan klasik dan kuantum, meskipun, dalam hal ini memberikan konsekuensi konkret-teoretis kompleksitas dari keberadaan sebuah simulator klasik yang efisien. Mungkin kolom yang lebih deskriptif akan menjadi "konsekuensi dari simulasi klasik yang efisien?"

Chris Granade

Pertanyaan tindak lanjut yang mungkin pantas mendapatkan pertanyaan sendiri: apakah Anda tahu jika ada cara alami untuk membuktikan bahwa optik linear dengan sendirinya tidak universal untuk BQP? Atau adakah penghalang untuk membuktikan ini (mis. Dengan menyiratkan hal-hal lain yang kita tidak tahu bagaimana menunjukkannya tetapi masih mungkin benar)?

Abhinav

$\cos^2(\frac\pi8)$

Saya percaya itu adil untuk mengatakan bahwa entri terakhir dalam tabel adalah "X" karena Quantum Computing dengan Cluster Variabel Berkelanjutan oleh Gu et al . Mereka menunjukkan bahwa negara-negara cluster non-Gaussian dapat ditindaklanjuti dengan pengukuran homodyne untuk UQC.
Kolom hipotetis "Universal untuk BQP" akan memiliki "X" untuk baris pertama dan "memeriksa" untuk istirahat - kecuali baris hipotetis pada hasil Aaronson dan Arkhipov, yang akan memiliki "?" (meskipun mungkin merupakan "X" menurut penulis).
Lihat jawaban Chris Granade di atas.

UPDATE: Saya seharusnya juga bertanya apakah ada baris baru yang bisa ditambahkan. Bagaimanapun, memang seseorang dapat: masukkan deskripsi gambar di sini

Itu dari Veitch et al . Lihat juga Mari dan Eisert .

Chris Ferrie
sumber