Simulasi klasik cepat dari algoritma kuantum

10

Adakah contoh kasus di mana simulasi klasik suatu algoritma kuantum untuk suatu masalah mengungguli algoritma klasik yang paling dikenal sebelumnya untuk masalah ini? "Outperforms" tidak harus berarti kelas kompleksitas yang berbeda, itu bisa saja lebih baik skala.

Pertanyaan ini terinspirasi oleh kasus simulasi klasik yang efisien dari algoritma rekomendasi kuantum .

cc.complexity-theory quantum-computing quantum-information delete000
sumber
1
Pertanyaan Anda sebagaimana dinyatakan tidak masuk akal. Simulasi klasik dari algoritma kuantum adalah jenis tertentu dari algoritma klasik, sehingga tidak bisa lebih cepat dari algoritma klasik terbaik. Ini bisa menjadi algoritma klasik yang paling cepat diketahui, tetapi tidak bisa lebih baik karena itu akan membuatnya lebih baik daripada dirinya sendiri.
Craig Gidney
Saya kira Anda maksudkan "Mengungguli algoritma klasik terbaik yang sebelumnya dikenal "
Frédéric Grosshans
Saya memikirkan peringatan itu ketika saya membaca pertanyaan, tetapi diharapkan akan menjadi jelas bahwa salah satu dari dua algoritma klasik akan menjadi "yang sebelumnya dikenal" non-simulasi algoritma kuantum. Saya tahu lebih baik sekarang.
delete000

Jawaban:

6

Pertanyaan Anda diilhami oleh kemajuan klasik yang diilhami kuantum terbaru dalam algoritme rekomendasi. Perhatikan bahwa ini bukan waktu pertama hal seperti itu terjadi. Pada tahun 2015, perkembangan serupa terjadi dengan perkiraan MAX3LIN : algoritma quanutm mengungguli semua algoritma klasik yang diketahui sebelumnya memotivasi pencarian sukses untuk algoritma klasik yang lebih baik. Namun, sejauh yang saya tahu, dalam kedua kasus ini, algoritma klasik tidak terlihat seperti simulasi klasik evolusi kuantum.

Saya tahu satu makalah yang menggambarkan simulasi klasik dari sistem kuantum yang memungkinkan untuk mengungguli algoritma yang dikenal sebelumnya (Pengungkapan penuh: penulis adalah teman saya) :

Algoritma yang terinspirasi oleh kuantum untuk memperkirakan permanen matriks semidefinit positif, oleh L. Chakhmakhchyan, NJ Cerf, R. Garcia-Patron, arXiv: 1609.02416 / Phys. Pendeta A 96 , 022329

Ini didasarkan pada hubungan antara optik permanen dan kuantum, yang ditunjukkan oleh boson sampling . Bertentangan dengan pendekatan yang biasa, mereka melihat keadaan yang dikenal mudah untuk disimulasikan (keadaan termal), dan menggunakan simulasi ini untuk melakukan perhitungan Monte-Carlo permanen dari matriks semidefinit positif Hermitian. Untuk beberapa kelas matriks, algoritma ini memberikan perkiraan yang lebih baik daripada algoritma terbaik yang diketahui sebelumnya (algoritma Gurvits).

Frédéric Grosshans
sumber