Kira-kira pengambilan sampel dari polihedron cembung dengan komputer kuantum

Komputer kuantum sangat baik untuk distribusi sampel yang kita tidak tahu bagaimana sampel menggunakan komputer klasik. Sebagai contoh jika f adalah fungsi Boolean (dari hingga ) yang dapat dihitung dalam waktu polinomial maka dengan komputer kuantum kita dapat secara efisien sampel sesuai dengan distribusi yang dijelaskan oleh Perluasan Fourier f. (Kami tidak tahu bagaimana melakukannya dengan komputer klasik.)- 1 , $\{-1,1\}^n$${-1,1}$

Bisakah kita menggunakan komputer kuantum untuk sampel atau sekitar sampel titik acak dalam polyhedron yang dijelaskan oleh sistem n ketidaksetaraan dalam variabel d?

Pindah dari ketidaksetaraan ke poin tampak bagi saya agak mirip dengan "transformasi". Selain itu, saya akan senang melihat algoritma kuantum bahkan jika Anda memodifikasi distribusi, misalnya mempertimbangkan produk dari distribusi Gaussian yang dijelaskan oleh hyperplanes polyhedron atau beberapa hal lainnya.

Beberapa komentar: Dyer, Frieze dan Kannan menemukan algoritma waktu polinomial klasik yang terkenal untuk sekitar sampel dan sekitar menghitung volume polyhedron. Algoritma ini didasarkan pada jalan acak dan pencampuran cepat. Jadi kami ingin menemukan algoritma kuantum yang berbeda untuk tujuan yang sama. (Oke, kita bisa berharap bahwa algoritma kuantum juga dapat mengarah pada hal-hal dalam konteks ini yang kita tidak tahu harus dilakukan secara klasik. Tetapi untuk memulai, yang kita inginkan adalah algoritma yang berbeda, ini harus dimungkinkan.)

Kedua, kami bahkan tidak bersikeras untuk mengambil sampel distribusi seragam. Kami akan dengan senang hati mengambil sampel beberapa distribusi bagus lainnya yang secara kasar didukung pada polyhedron kami. Ada argumen oleh Santosh Vampala (dan juga oleh saya dalam konteks lain) yang mengarah dari sampling ke optimasi: jika Anda ingin mengoptimalkan f (x) sampel untuk menemukan titik y di mana f (x) adalah tipikal. Tambahkan batasan {f (x)> = f (y)} dan ulangi.

Seperti yang diakui oleh pos, keberadaan algoritma waktu polinomial klasik untuk memperkirakan volume cembung polytope adalah game-changer. Algoritma kuantum jauh lebih kecil kemungkinannya untuk menjadi menarik kecuali kompetitif dengan algoritma klasik. Lagi pula, tanpa kriteria itu, algoritma klasik apa pun bisa disebut sebagai algoritma kuantum.

Yang mengatakan, masih ada ruang untuk percepatan polinomial, dan sudut pandang utama yang diketahui untuk jenis speedup itu adalah quantum walk, terutama mengingat akselerasi klasik dalam kasus ini didasarkan pada berjalan acak yang baik. (Memang, setiap algoritma kuantum dapat dipandang sebagai jalan kuantum, tetapi untuk beberapa algoritma ini belum tentu mencerahkan.) Berbagai makalah dalam literatur QC telah menunjukkan bahwa algoritma untuk memperkirakan volume polytope cembung menggunakan walks acak, dan bahwa mungkin ada percepatan dari jalan kuantum. Jadi, tampaknya para peneliti mengetahui saran ini, tetapi tidak ada yang mencoba mencari tahu akselerasi polinomial apa yang mungkin Anda dapatkan untuk masalah ini. Anda mungkin tidak mendapatkan apa pun jika algoritma klasik terbaik memiliki semacam spoiler,

Berikut ini adalah kumpulan makalah yang semuanya menyebutkan ide dasar secara sepintas; lagi, Google Cendekia tampaknya menyarankan bahwa tidak ada yang melangkah lebih jauh.

1. arXiv: quant-ph / 0104137 - Quantum Walks di Hypercube
2. arXiv: quant-ph / 0205083 - Jalan acak kuantum menekan secara eksponensial lebih cepat
3. arXiv: quant-ph / 0301182 - Decoherence dalam jalan kuantum Diskrit
4. arXiv: quant-ph / 0304204 - Mengontrol jalan kuantum diskrit: koin dan status awal
5. arXiv: quant-ph / 0411065 - Jalan kuantum dengan dua partikel terjerat
6. arXiv: quant-ph / 0504042 - Keterikatan dalam quantum walks berjalan pada grafik reguler
7. arXiv: quant-ph / 0609204 - Percepatan kuantum dari proses pencampuran klasik
8. arXiv: 0804.4259 - Mempercepat melalui pengambilan sampel kuantum
9. Pendekatan berjalan acak ke algoritma kuantum
10. Jalan kuantum diskrit untuk menyelesaikan persamaan nonlinier pada bidang hingga

Sisi lain dari algoritma klasik untuk memperkirakan volume cytope polytope adalah pemrograman linier. Saya tidak tahu ada kemajuan dalam menemukan percepatan kuantum untuk itu. Tampaknya sulit untuk menghindari tahap pemrograman linier untuk menempatkan cembung polytope dalam posisi yang menguntungkan untuk pengambilan sampel.