Boson Sampling , terkadang dengan gaya BosonSampling, adalah masalah kandidat yang menarik untuk membangun supremasi kuantum; masalah teknik muncul lebih diatasi daripada yang terkait dengan komputer kuantum Turing-lengkap.

Namun, Boson Sampling memiliki kelemahan, yaitu bahwa output dari komputer kuantum fotonik yang mampu mengeksekusi Boson Sampling hanya dengan segelintir ( atau lebih) qubit mungkin bahkan tidak dapat disimulasikan secara klasik. Hal ini, tentu saja, tidak seperti N P masalah seperti anjak piutang, aspek rekayasa yang secara signifikan lebih keras.$\le 100$$\mathsf{NP}$

Dengan demikian, kita dapat membentuk hasil Boson Sampling pada atau lebih foton, tetapi untuk memverifikasi hasil, kita perlu menghitung permanen dari 100 × 100 matriks. Komputasi ini terkenal sulit untuk diverifikasi. $100$$100\times100$

Mungkin superkomputer yang cukup kuat untuk menghitung permanen dapat melakukan triknya. Tapi kemudian semua orang akan harus percaya kedua hasil superkomputer dan hasil Boson Sampling.

Apakah ada sesuatu tentang Boson Sampling yang dapat dengan mudah diverifikasi?

Saya memiliki penerbangan yang bagus untuk menggunakan sumber daya dari jaringan penambangan cryptocurrency untuk digunakan untuk menghitung permanen, dan mengandalkan beberapa trik / I P untuk verifikasi publik, tetapi saya belum melangkah terlalu jauh.$\mathsf{\#P}$$\mathsf{IP}$

EDIT

Saya suka jawaban @ gIS.

$\mathsf{PCP}$

Tentang perlunya verifikasi boson sampling

Pertama-tama, izinkan saya menunjukkan bahwa ini bukan keharusan yang ketat untuk memverifikasi hasil sampler boson. Dengan ini, saya tidak bermaksud mengatakan bahwa tidak ada gunanya atau menarik untuk dicoba dan dilakukan, tetapi lebih pada arti bahwa lebih praktis daripada kebutuhan mendasar.

Saya pikir Anda sendiri mengajukan argumen yang bagus untuk ini ketika Anda menulis

Mungkin superkomputer yang cukup kuat untuk menghitung permanen dapat melakukan triknya. Tapi kemudian semua orang harus percaya hasil superkomputer dan Boson Sampling.

Memang, ada banyak contoh di mana seseorang memecahkan masalah dan mempercayai solusi yang tidak dapat benar-benar diverifikasi sepenuhnya. Maksud saya, lupakan mekanika kuantum, cukup gunakan komputer Anda untuk melipatgandakan dua angka besar. Anda mungkin memiliki kepercayaan diri yang tinggi bahwa hasil yang Anda dapatkan adalah benar, tetapi bagaimana Anda memverifikasinya tanpa menggunakan komputer lain?

Secara lebih umum, kepercayaan pada hasil perangkat berasal dari berbagai hal, seperti pengetahuan tentang kinerja perangkat, dan pengujian unit perangkat itu sendiri (yaitu, pengujian apakah itu berfungsi dengan benar untuk contoh khusus yang dapat Anda verifikasi dengan beberapa metode lain).

Masalah sertifikasi boson sampling tidak berbeda. Kita tahu bahwa, pada titik tertentu, kita tidak akan dapat sepenuhnya memverifikasi hasil sampler boson, tetapi itu tidak berarti bahwa kita tidak akan bisa mempercayainya. Jika perangkat dibangun dengan cermat, dan hasilnya diverifikasi untuk berbagai kejadian kecil, dan tes lain yang dapat dilakukan semuanya berhasil, maka pada titik tertentu seseorang membangun kepercayaan yang cukup pada perangkat untuk membuat klaim supremasi kuantum (atau apa pun yang orang ingin gunakan boson sampler) bermakna.

Apakah ada sesuatu tentang BosonSampling yang dapat dengan mudah diverifikasi?

Ya, ada properti yang bisa diverifikasi. Karena sifat pengambilan sampel dari masalah, apa yang biasanya dilakukan orang adalah untuk mengesampingkan model alternatif yang mungkin telah menghasilkan sampel yang diamati. Sebagai contoh, Aaronson dan Arkhipov ( 1309.7460 ) menunjukkan bahwa distribusi BosonSampling jauh dari distribusi seragam dalam total variasi jarak (dengan probabilitas tinggi atas matriks acak Haar yang mendorong distribusi), dan memberikan protokol untuk secara efisien membedakan dua distribusi. Sebuah karya yang lebih baru menunjukkan bagaimana tanda tangan statistik dapat digunakan untuk mengesahkan distribusi sampel boson terhadap hipotesis alternatif adalah ( Walschaers et al. 2014 ).

Semua pekerjaan lain yang saya ketahui fokus pada sertifikasi aspek spesifik boson sampler, daripada secara langsung menangani masalah menemukan distribusi alternatif yang jauh dari BosonSampling satu untuk interferometer acak.

Lebih khusus, seseorang dapat mengisolasi dua sumber kesalahan utama yang mungkin ada dalam peralatan pengambilan sampel boson: yang timbul karena penerapan interferometer yang salah, dan yang timbul dari foton input yang tidak sesuai dengan yang seharusnya (yaitu, sama sekali tidak dapat dibedakan).

Kasing pertama (relatif) mudah ditangani karena seseorang dapat secara efisien mengkarakterisasi interferometer menggunakan foton tunggal. Namun, sertifikasi pembeda foton yang sulit dibedakan lebih sulit. Satu ide untuk melakukan ini adalah mengubah interferometer menjadi non-acak, seperti interferometer QFT, dan melihat apakah sesuatu dapat diverifikasi secara efisien dalam kasus yang lebih sederhana ini. Saya tidak akan mencoba untuk menambahkan semua referensi yang relevan di sini, tetapi arah ini dimulai dengan (Tichy et al. 2010 , 2013 ).

Mengenai aspek verifikasi publik, tidak ada yang dilakukan ke arah ini yang saya dengar. Saya juga tidak yakin apakah itu adalah arah yang sangat berarti untuk dijelajahi: mengapa kita harus memerlukan "standar tinggi" verifikasi untuk sampler boson, padahal untuk hampir semua jenis eksperimen lain kita puas dengan memercayai orang-orang yang melakukan bereksperimen untuk menjadi baik pada apa yang mereka lakukan?

Hanya pelengkap kecil untuk jawaban luar biasa @gIS: Saya tahu beberapa orang (termasuk saya) tertarik pada aspek verifikasi publik. Sejauh yang saya tahu, semua upaya telah gagal, karenanya kurangnya literatur tentang subjek: begitu seseorang dapat membuktikan bahwa Boson sampler bertindak dengan benar, itu memang sebuah rezim di mana sampler Boson dapat disimulasikan secara efisien secara klasikal.

$IQP$$IQP$$P$