Aplikasi dunia nyata komputasi kuantum (kecuali untuk keamanan)

Mari kita asumsikan bahwa kita telah membangun komputer kuantum universal.

Kecuali untuk masalah yang berhubungan dengan keamanan (kriptografi, privasi, ...) yang mana masalah dunia nyata saat ini dapat mengambil manfaat dari menggunakannya?

Saya tertarik pada keduanya:

• masalah saat ini tidak terpecahkan untuk entri praktis,
• masalah yang saat ini sedang diselesaikan, tetapi percepatan yang signifikan akan sangat meningkatkan kegunaannya.

Mensimulasikan mekanika kuantum secara efisien.

Brassard, Hoyer, Mosca, dan Tapp menunjukkan bahwa pencarian Grover yang digeneralisasi, yang disebut amplitude amplification, dapat digunakan untuk mendapatkan kecepatan kuadratik pada kelas besar heuristik klasik. Intuisi di balik ide mereka adalah bahwa heuristik klasik menggunakan keacakan untuk mencari solusi untuk masalah yang diberikan, sehingga kita dapat menggunakan amplitude amplifikasi untuk mencari rangkaian string acak untuk satu yang akan membuat heuristik menemukan solusi yang baik. Ini menghasilkan percepatan kuadrat dalam waktu berjalan dari algoritma. Lihat bagian 3 dari kertas yang ditautkan di atas untuk lebih jelasnya.

Mensimulasikan sistem kuantum!

Saya perhatikan bahwa dalam jawaban lain yang menyebutkan ini ada beberapa komentar tentang apakah ini benar karena itu adalah klaim yang tidak jelas. Dan orang-orang meminta referensi. Berikut ini beberapa referensi.

Proposal asli oleh Feynman:

Feynman, R .: Mensimulasikan fisika dengan komputer. Int. J. Theor. Phys 21 (6) (1982) 467-488

Algoritma yang efisien untuk semua sistem kuantum yang didefinisikan oleh Hamiltonian "lokal". (Lloyd juga menjelaskan bahwa sistem apa pun yang konsisten dengan relativitas khusus dan umum berkembang sesuai dengan interaksi lokal.)

Lloyd, S .: Simulator kuantum universal. Sains 273 (5278) (1996) 1073-1078

Generalisasi lebih lanjut untuk warga Hamilton yang jarang, yang lebih umum daripada penduduk Hamilton setempat:

Aharonov, D., Ta-Shma, A .: Generasi keadaan kuantum adiabatik dan pengetahuan nol statistik. Dalam: Proc. 35th STOC, ACM (2003) 20–29

Bacaan lebih lanjut:

Berry, D., Ahokas, G., Cleve, R., Sanders, B .: Algoritma kuantum E sien untuk mensimulasikan Hamiltonians yang jarang. Komunal. Matematika Phys 270 (2) (2007) 359-371

Childs, AM: Pemrosesan informasi kuantum dalam waktu terus menerus. Tesis PhD, Massachusetts Institute of Technology (2004)

Visioning berbahaya dan polemik di bidang ini, jadi kita harus berhati-hati dengan topik ini. Namun beberapa algoritma-Q dengan percepatan polinomial memiliki aplikasi potensial yang menarik.

Diketahui bahwa pencarian Grover dapat digunakan untuk mencari solusi untuk masalah NP-lengkap [1] . Ini terbukti untuk 3-SAT di [2] . Beberapa aplikasi SAT, yang dipinjam dari [3] , adalah: memeriksa kesetaraan rangkaian , pembuatan pola-tes otomatis , pengecekan model menggunakan Linear Time Logic , perencanaan dalam kecerdasan buatan dan haplotyping dalam bioinformatika . Meskipun saya tidak tahu banyak tentang topik-topik ini, penelitian ini terlihat praktis bagi saya.

Juga, ada algoritma kuantum untuk mengevaluasi NAND-tree dengan percepatan polinomial atas perhitungan klasik [ 8 , 10 , 11 ]. Pohon NAND adalah contoh dari pohon permainan, struktur data yang lebih umum digunakan untuk mempelajari pertandingan permainan papan seperti Catur dan Go. Kedengarannya masuk akal bahwa speed-up semacam ini dapat digunakan untuk mendesain pemain game yang lebih kuat. Bisakah ini menarik minat beberapa pengembang game-video-kuantum?

Sayangnya, bermain game pada kenyataannya tidak persis sama dengan mengevaluasi pohon: ada komplikasi, misalnya, jika pemain Anda tidak menggunakan strategi optimal [ 12 ]. Saya belum melihat studi yang mempertimbangkan skenario kehidupan nyata, jadi sulit untuk mengatakan seberapa bermanfaat percepatan dari [ 8 ] dalam praktiknya. Ini bisa menjadi topik diskusi yang bagus.

berpikir Anda telah mengajukan pertanyaan yang sangat bagus di garis depan penelitian QM (sebagian ditunjukkan oleh kurangnya jawaban Anda sejauh ini), tetapi itu belum sepenuhnya secara resmi didefinisikan atau ditangkap sebagai masalah. pertanyaannya adalah di sepanjang baris "apa sebenarnya algoritma QM dapat dihitung secara efisien?" dan jawaban yang lengkap tidak diketahui & sedang dikejar secara aktif. beberapa di antaranya terkait dengan kompleksitas (pertanyaan terbuka tentang) kelas terkait QM.

ini akan menjadi kasus bahwa ada pertanyaan yang agak formal didefinisikan. jika kelas QM dapat ditunjukkan setara dengan kelas non-QM yang "sangat kuat", maka ada jawaban Anda. tema umum dari jenis hasil ini adalah kelas "tidak-terlalu-sulit-di-QM" setara dengan kelas "sulit-di-non-QM". ada berbagai pemisahan kelas kompleksitas terbuka dari jenis ini (mungkin orang lain dapat menyarankan mereka secara lebih rinci).

sesuatu yang aneh tentang pengetahuan QM saat ini tentang algoritma kuantum adalah bahwa ada semacam tas algoritma yang diketahui bekerja di QM tetapi tampaknya tidak banyak koherensi / kohesi pada mereka. mereka tampak aneh dan terputus dalam beberapa hal. tidak ada "aturan praktis" yang jelas untuk "masalah yang dapat dihitung dalam QM umumnya dalam bentuk ini" meskipun ada harapan yang masuk akal bahwa seseorang dapat berada di sana.

misalnya membandingkan ini dengan teori kelengkapan NP yang jauh lebih kohesif dibandingkan. sepertinya mungkin jika teori QM lebih baik dikembangkan itu akan mendapatkan rasa kohesi yang lebih besar ini mengingatkan pada teori kelengkapan NP.

ide yang lebih kuat mungkin bahwa pada akhirnya ketika teori kompleksitas QM lebih baik, kelengkapan NP akan cocok dengan "rapi" ke dalamnya.

bagi saya percepatan QM paling umum atau strategi yang dapat diterapkan secara luas yang pernah saya lihat tampaknya adalah algoritma Grovers karena begitu banyak perangkat lunak praktis terkait dengan permintaan db. dan dalam beberapa hal semakin "tidak terstruktur":

$O(\sqrt{N})$$Ω(N)$