Algoritma pendekatan kuantum

Secara umum dianggap tidak mungkin bahwa komputer kuantum akan dapat menyelesaikan masalah NP-complete secara efisien. Dalam kasus klasik, salah satu pendekatan untuk mengatasi masalah tersebut adalah dengan menggunakan algoritma aproksimasi. Apakah ada penelitian tentang algoritma aproksimasi menggunakan komputasi kuantum di mana kuantum memberikan peningkatan signifikan terhadap metode pendekatan klasik?

Dengan "signifikan" yang saya maksud tidak harus eksponensial, tetapi lebih besar daripada untuk algoritma yang sesuai. Dengan kata lain, saya tertarik jika melonggarkan persyaratan bahwa algoritma kami menghasilkan solusi yang tepat memberikan keuntungan yang signifikan untuk algoritma kuantum.

Komentar ditingkatkan menjadi jawaban parsial:

Ada cukup banyak pekerjaan akhir-akhir ini tentang dugaan (atau tidak) versi teorema PCP: lihat misalnya posting blog ini oleh Scott Aaronson http://www.scottaaronson.com/blog/?p=139 atau jawaban ini oleh Peter Shor di MathOverflow /mathpro/45106/quantum-pcp-theorem/45167#45167

Mengenai alpgoritma aproksimasi kuantum, Anda dapat melihat referensi ini "Algoritma aproksimasi untuk masalah lengkap QMA" http://arxiv.org/abs/1101.3884

Saya pribadi tidak mengetahui adanya pekerjaan ke arah algoritma perkiraan kuantum dalam arti perkiraan relatif (vs perkiraan tambahan) (walaupun itu tidak selalu berarti mereka tidak ada).

Perhatikan bahwa jika maksud Anda adalah merancang perkiraan kuantum waktu-poli untuk, katakanlah, masalah NP-hard, banyak masalah seperti MAX-CUT sudah memiliki perkiraan klasik ketat (dengan asumsi Konjektur Game Unik atau oleh PCP). Jadi sepertinya masuk akal untuk memulai dengan mempelajari masalah yang memiliki kesenjangan dalam rasio pendekatan yang diketahui versus hasil kekerasan.

Arah lainnya adalah kekerasan pendekatan - lihat misalnya http://arxiv.org/abs/0811.3412 dan http://arxiv.org/abs/1012.3319 untuk kemajuan parsial positif dan negatif mengenai kemungkinan teorema PCP kuantum.

Semacam jawaban yang sepele, tetapi ada yang memperkirakan probabilitas penerimaan dari rangkaian kuantum, atau masalah yang setara, seperti mendekati polinomial Jones, atau solusi sistem persamaan linear, atau jejak kekuatan sebuah matriks jarang besar.

Juga, perkiraan penghitungan mempercepat banyak algoritme pendekatan berbasis pengambilan sampel.

Algoritme aproksimasi untuk Algoritma Optimasi disajikan di sini - makalah ini menyajikan algoritme aproksimasi kuantum untuk fungsi objektif yang memiliki gerbang kesatuan yang memiliki lokalitas sebagai fungsi fungsi objektif yang optimal. Untuk tetap$i$ , dan yang bervariasi dengan ukuran input, algoritma kuantum menemukan pendekatan terhadap solusi optimal. Mereka telah mempelajari aplikasi untuk masalah optimasi MaxSat, dan MAX-CUT (untuk beberapa kasus grafik biasa). Fungsi obyektif untuk masalah optimisasi dilihat sebagai operator kesatuan khusus, yang memusatkan solusi, dan dengan demikian mencapai perkiraan.