(Maaf untuk pertanyaan yang agak amatir)
Saya belajar komputasi kuantum dari 2004 hingga 2007, tetapi saya sudah kehilangan jejak sejak itu. Pada saat itu ada banyak hype dan pembicaraan tentang QC yang berpotensi menyelesaikan segala macam masalah dengan mengungguli komputer klasik, tetapi dalam praktiknya hanya ada dua terobosan teoretis:
- Algoritma Shor, yang memang menunjukkan kecepatan yang signifikan, tetapi yang memiliki penerapan terbatas, dan tidak benar-benar berguna di luar faktorisasi bilangan bulat.
- Algoritma Grover, yang berlaku untuk kategori masalah yang lebih luas (karena dapat digunakan untuk menyelesaikan masalah NP-Complete), tetapi yang hanya menunjukkan kecepatan polinomial dibandingkan dengan komputer klasik.
Anil kuantum juga dibahas, tetapi tidak jelas apakah itu benar-benar lebih baik daripada anil simulasi klasik atau tidak. QC berdasarkan pengukuran dan representasi status grafik dari QC juga merupakan topik hangat, tetapi tidak ada yang pasti telah dibuktikan di bagian depan itu.
Apakah ada kemajuan di bidang algoritma kuantum yang telah dibuat sejak saat itu? Khususnya:
- Apakah ada algoritma yang benar-benar inovatif selain Grover dan Shor?
- Apakah ada kemajuan dalam mendefinisikan hubungan BQP dengan P, BPP dan NP?
- Sudahkah kita membuat kemajuan dalam memahami sifat kuantum mempercepat selain mengatakan bahwa "itu pasti karena keterjeratan"?
speedup
grovers-algorithm
shors-algorithm
Alex Kinman
sumber
sumber
Jawaban:
Itu tergantung pada apa yang Anda maksud dengan "benar-benar melanggar". Grover dan Shor sangat unik karena mereka benar-benar contoh pertama yang menunjukkan jenis percepatan yang sangat berharga dengan komputer kuantum (mis. Dugaan peningkatan eksponensial untuk Shor) dan mereka memiliki aplikasi pembunuh untuk komunitas tertentu.
Ada beberapa algoritma kuantum yang telah dirancang sejak itu, dan saya pikir tiga sangat layak disebutkan:
Algoritma BQP-lengkap untuk mengevaluasi polinomial Jones pada titik-titik tertentu. Saya menyebutkan ini karena, selain dari hal-hal yang lebih jelas seperti simulasi Hamilton, saya percaya itu adalah algoritma BQP-lengkap pertama, sehingga benar-benar menunjukkan kekuatan penuh komputer kuantum.
The algoritma hhl untuk memecahkan persamaan linear. Ini agak lucu karena lebih seperti subrutin kuantum, dengan input dan output kuantum. Namun, itu juga BQP-lengkap dan itu menerima banyak perhatian saat ini, karena aplikasi potensial dalam pembelajaran mesin dan sejenisnya. Saya kira ini adalah kandidat terbaik untuk benar-benar terobosan, tapi itu masalah pendapat.
Kimia Kuantum . Saya tahu sedikit tentang ini, tetapi algoritma telah berkembang secara substansial sejak Anda sebutkan, dan selalu dikutip sebagai salah satu aplikasi yang berguna dari komputer kuantum.
Intinya, tidak. Kami tahu BQP mengandung BPP, dan kami tidak tahu hubungan antara BQP dan NP.
Bahkan ketika Anda mempelajarinya awalnya, saya akan mengatakan itu lebih tepat didefinisikan dari itu. Ada (dan) perbandingan yang baik antara set gerbang universal (berpotensi mampu memberikan kecepatan eksponensial) dan set gerbang simulable klasik. Misalnya, ingat bahwa gerbang Clifford menghasilkan belitan tetapi secara klasik dapat disimulasikan. Bukan berarti langsung menyatakan secara tepat apa yang dibutuhkan dengan cara yang lebih pedagogis.
Mungkin di mana beberapa kemajuan telah dibuat adalah dalam hal model perhitungan lain. Sebagai contoh, model DQC1 lebih baik dipahami - ini adalah model yang tampaknya memiliki beberapa percepatan atas algoritma klasik tetapi tidak mungkin mampu melakukan perhitungan BQP-lengkap (tetapi sebelum Anda tertarik pada hype yang mungkin Anda temukan online , ada adalah hadir keterikatan selama perhitungan).
Di sisi lain, pernyataan "itu karena keterjeratan" masih belum sepenuhnya diselesaikan. Ya, untuk perhitungan kuantum keadaan murni, harus ada beberapa keterjeratan karena jika tidak, sistem ini mudah disimulasikan, tetapi untuk keadaan campuran yang dapat dipisahkan, kami tidak tahu apakah mereka dapat digunakan untuk perhitungan, atau apakah mereka dapat disimulasikan secara efisien.
Juga, orang mungkin mencoba untuk mengajukan pertanyaan yang lebih mendalam: Sudahkah kita membuat kemajuan dalam memahami masalah mana yang akan dapat diterima untuk mempercepat kuantum? Ini agak berbeda karena jika Anda berpikir bahwa komputer kuantum memberi Anda gerbang logika baru yang tidak dimiliki komputer klasik, maka jelas bahwa untuk mendapatkan kecepatan, Anda harus menggunakan gerbang baru itu. Namun, tidak jelas bahwa setiap masalah dapat menerima manfaat tersebut. Yang mana Ada kelas masalah di mana orang mungkin berharap untuk mempercepat, tetapi saya pikir itu masih bergantung pada intuisi individu. Itu mungkin masih bisa dikatakan tentang algoritma klasik. Anda telah menulis sebuah algoritma x. Apakah ada versi klasik yang lebih baik? Mungkin tidak, atau mungkin Anda tidak melihatnya. Itu sebabnya kita tidak tahu apakah P = NP.
sumber
Algoritma Kerenidis-Prakash adalah terobosan, sampai Ewin Tang memperbaiki tanah:
Majalah Quanta: Kemajuan Komputasi Utama Quantum Dibuat Kuno oleh Remaja .
sumber