Apakah ada pernyataan umum tentang masalah apa yang dapat didekati dengan lebih efisien menggunakan komputer kuantum?

Seperti namanya, pertanyaan ini merupakan tindak lanjut dari pertanyaan ini . Saya senang dengan kualitas jawaban, tetapi saya merasa akan sangat menarik jika wawasan tentang teknik optimasi dan perkiraan ditambahkan, tetapi mungkin jatuh di luar topik, maka pertanyaan ini.

Dari jawaban Blue:

aturan praktis dalam teori kompleksitas adalah bahwa jika komputer kuantum "dapat membantu" dalam hal penyelesaian dalam waktu polinomial (dengan batas kesalahan) jika kelas masalah dapat diselesaikan terletak pada BQP tetapi tidak dalam P atau BPP

Bagaimana ini berlaku untuk kelas aproksimasi? Apakah ada properti topologi, numerik, dll. Spesifik dari komputasi kuantum yang dapat dimanfaatkan?

Sebagai contoh dari apa yang bisa saya tanyakan (tapi jelas tidak terbatas pada itu!), Ambil algoritma Christofides : ia mengeksploitasi sifat-sifat geometris tertentu dari grafik yang dioptimalisasi (simetri, ketimpangan segitiga): salesman bepergian di dunia yang layak . Tetapi salesman juga memiliki massa yang sangat besar, dan kita dapat mengetahui posisi dan momentum mereka pada saat yang sama dengan sangat teliti. Mungkin model kuantum dapat bekerja dengan baik untuk jenis metrik lainnya dengan batasan lebih santai, seperti perbedaan KL ? Dalam hal penyelesaian itu masih akan NP lengkap, tetapi optimasi akan berlaku untuk topologi yang lebih luas. Contoh ini mungkin jauh, tapi saya harap Anda mengerti maksud saya. Saya tidak benar-benar tahu apakah itu masuk akal sama sekali, tetapi jawabannya juga bisa mengatasinya dalam hal ini :)

TERKAIT:

• Tingkat keuntungan yang diberikan oleh anil untuk penjual keliling

The Algorithm Optimization Perkiraan Quantum adalah tempat yang baik untuk memulai untuk menganalisis kinerja relatif dari algoritma quantum pada masalah pendekatan. Salah satu hasil sejauh ini adalah bahwa pada p = 1 QAOA secara teoritis dapat mencapai rasio perkiraan 0,624 untuk MaxCut pada grafik 3-reguler. Hasil ini diperoleh dengan menggunakan enumerasi brute force dari berbagai kemungkinan kasus. Ini bukan teknik yang mudah digeneralisasikan, sehingga relatif sedikit yang diketahui tentang kinerja QAOA pada masalah lain.

Seperti saat ini berdiri QAOA menggunakan sangat sedikit struktur dalam masalah optimasi kombinatorial dan beroperasi lebih di sepanjang garis metode pencarian langsung. Salah satu konsekuensi yang mungkin adalah bahwa QAOA akan paling baik digunakan untuk masalah di mana ada struktur minimal. Dalam hal ini tidak ada yang dapat digunakan algoritma klasik untuk mempercepat proses pencarian.