Daftar algoritma yang terinspirasi kuantum

11

Kemajuan dalam komputasi kuantum telah menyebabkan pengembangan algoritma klasik baru. Contoh terkini yang terkenal adalah algoritma yang terinspirasi kuantum untuk aljabar linier:

dan untuk Maks 3LIN:

Mungkin sangat berguna untuk menyusun daftar semua algoritma klasik yang diketahui yang terinspirasi dari komputasi kuantum. Apa contoh lain yang diketahui?

quantum-computing randomized-algorithms Juan Miguel Arrazola
sumber

Jawaban:

5

Seperti yang diklaim oleh Leslie G. Valiant dalam makalah mani 1 ,

Algoritma holografik terinspirasi oleh model komputasi kuantum. Namun, mereka dapat dieksekusi di komputer klasik dan tidak membutuhkan komputer kuantum.

Itu adalah teknik desain algoritmik yang telah digunakan (oleh Valiant sendiri dan orang lain) untuk menghasilkan algoritma waktu polinomial untuk beberapa masalah yang merupakan variasi kecil dari masalah NP-hard yang penting (lebih lanjut tentang itu di wikipedia 2 ).

Alessandro Cosentino
sumber
8

Ada juga karya terbaru tentang pemrograman semidefinit peringkat rendah yang, meskipun tidak didasarkan langsung pada algoritma kuantum, masih menggunakan teknik yang diilhami kuantum yang sama.

Ewin
sumber
3

Ada seluruh pekerjaan yang harus dilakukan dengan algoritma evolusioner yang diilhami kuantum (QIEA), dengan algoritma aktual yang menggunakan teknik komputasi kuantum, lihat survei (sumber ACM) . Algoritma lain yang terinspirasi oleh kuantum menggunakannya dalam optimasi numerik .

pengguna3483902
sumber
3

Algoritma kuantum Monte Carlo quantum annealing (QMC-QA 1 ) atau diskrit waktu simulasi (SQA 2 ) yang disimulasikan bekerja lebih baik daripada perangkat D-Wave yang diuji dalam penelitian terbaru :

Kami menetapkan contoh pertama dari keuntungan penskalaan untuk annealer kuantum eksperimental dibandingkan annealing simulasi klasik: kami menemukan bahwa perangkat D-Wave menunjukkan penskalaan yang lebih baik secara sertifikasi daripada anil simulasi, dengan kepercayaan 95%, pada kisaran ukuran masalah yang dapat kami uji . Namun, kami tidak menemukan bukti untuk percepatan kuantum: simulasi anil kuantum menunjukkan penskalaan terbaik dengan margin yang signifikan.

Karena perangkat D-Wave dan SQA mengungguli SA untuk contoh masalah tertentu, ini memberi kesan bahwa SQA adalah semacam algoritma yang diilhami kuantum. Studi yang lebih baru menguji prosesor D-Wave 2000Q juga menemukan bahwa kinerjanya berkorelasi lebih baik dengan model klasik yang diusulkan berlabel "algoritma spin-vektor Monte Carlo (SVMC)" dalam penelitian itu daripada dengan SQA:

Kami menggunakan ini untuk berargumen bahwa alasan utama perlambatan kuantum relatif terhadap SQA adalah suhu sub-optimal yang tinggi, yang menyebabkannya berperilaku lebih seperti SVMC. Dengan demikian, kinerja yang kuat dari SQA pada kelas instance logis-ditanam menunjukkan bahwa kelas ini adalah target atau dasar yang baik untuk eksplorasi speedup kuantum akhirnya menggunakan perangkat keras QA.

Jika kita mengabaikan latar belakang cerita D-Wave, apakah kita masih dapat menyimpulkan bahwa SQA adalah algoritma optimasi yang diilhami oleh kuantum yang mengungguli annealing simulasi klasik (dan mungkin algoritma optimasi lainnya) untuk masalah tertentu? Tergantung. Jika tujuannya sebenarnya adalah untuk menemukan keadaan dasar dari suatu sistem kuantum, maka jawabannya adalah ya. Tetapi jika tujuannya adalah untuk memiliki algoritma optimasi tujuan umum yang mirip dengan simulasi anil, maka jawabannya adalah tidak.

  1. Martoňák, R., Santoro, GE & Tosatti, E. Quantum annealing dengan metode path-integral Monte Carlo: Model Ising acak dua dimensi. Phys Pendeta B 66 , 094203 (2002). URL http://link.aps.org/doi/10.1103/PhysRevB.66.094203
  2. Santoro, GE, Martoňák, R., Tosatti, E. & Car, R. Teori quantum annealing dari Ising spin glass. Sains 295 , 2427-2430 (2002). URL http://dx.doi.org/10.1126/science.1068774 .
Thomas Klimpel
sumber