Dapatkah pemecah aljabar linear klasik menerapkan algoritme kuantum dengan percepatan yang serupa?
Algoritme kuantum dimulai dengan register qubit dalam keadaan awal, operator kesatuan (algoritme) memanipulasi status qubit tersebut, dan kemudian status qubit tersebut dibacakan (atau setidaknya beberapa informasi tentang status pada satu menjalankan algoritme).
Tampak bagi saya bahwa komputer kuantum menjawab pertanyaan tentang tindakan kesatuan pada keadaan kuantum. Ini "hanya" soal aljabar linier. Saya terkejut, kemudian, komputer kuantum dapat dilihat sebagai kalkulator aljabar linier.
Lalu mengapa kita membutuhkan mekanika kuantum? Tidak dapatkah kita menemukan sistem klasik yang mengimplementasikan operasi aljabar linier dan menggunakannya untuk mengimplementasikan algoritma yang telah dirancang untuk komputer kuantum? Tentu saja komputer digital klasik tidak akan mencukupi, mesin ini didasarkan pada pemrosesan informasi biner daripada manipulasi vektor dalam ruang berdimensi tinggi.
Pertanyaan: Adakah kandidat untuk pemecah aljabar linier klasik (komputer analog klasik) yang dapat mengimplementasikan algoritme "komputer kuantum" sambil menikmati kecepatan yang sama dibandingkan komputer klasik digital?
Pertanyaan 2: Mungkin saya terlalu menyederhanakan dengan mereduksi komputer kuantum menjadi pemecah aljabar linier. Apakah ini masalahnya? Kompleksitas apa yang saya sembunyikan?
Jawaban
Kompleksitas yang Anda abaikan adalah yang dalam kasus umum perlu Anda simpan $2^n$ amplitudo kompleks bahkan untuk mewakili $n$sistem qubit klasik. Oleh karena itu, untuk komputer kuantum katakanlah 1000 qubit yang perlu Anda simpan$2^{1000}$amplitudo kompleks. Bahkan jika Anda menggunakan satu atom per amplitudo untuk melakukan ini, Anda masih kehabisan atom di alam semesta yang dapat diamati.
Sejauh yang saya tahu, di atas adalah argumen umum. Namun, mungkin masih ada cara untuk merepresentasikan algoritme kuantum tertentu dengan cara yang dapat ditelusuri secara klasik dengan memanfaatkan beberapa wawasan cerdas untuk menghemat kebutuhan representasi algoritme, sehingga berjalan di bawah$2^n$kebutuhan. Tetapi ini mungkin menjadi masalah khusus dan tidak mungkin berhasil dalam kasus umum.
Sesuai pernyataan pertanyaan tentang komputasi digital vs analog, ada utas lain di situs ini yang menanyakan tentang proposal serupa. Lihat, misalnya di sini , dan di sini . Antara lain, sistem analog klasik tidak dapat terlibat dalam keterjeratan; sehingga menyusun kembali komputer kuantum sebagai komputer analog tidak akan menghasilkan percepatan yang diamati.
Meskipun demikian, lebih jauh dari jawaban @Attila Kun ada masalah khusus dalam aljabar linier / pembelajaran mesin yang memiliki algoritme kuantum cepat tetapi telah disusun ulang sebagai algoritme klasik yang memiliki kecepatan serupa.
Misalnya, masalah rekomendasi yang digunakan oleh Netflix / Amazon / dll. memiliki algoritma yang cepat di komputer kuantum. Algoritme ini menunjukkan peningkatan eksponensial dari algoritme klasik (saat itu) paling terkenal.
Namun, dalam upaya untuk membuktikan bahwa algoritme kuantum benar-benar lebih unggul, E. Tang menunjukkan bahwa memang ada "sistem klasik yang mengimplementasikan operasi aljabar linier dan menggunakan ini untuk mengimplementasikan algoritme yang telah dirancang untuk komputer kuantum".
Pekerjaan Tang telah memulai program dequantization - yaitu mendesain ulang algoritma kuantum cepat dalam aljabar linier / pembelajaran mesin sebagai algoritma klasik cepat. Artikel Majalah Quanta menjelaskan masalah dan pendekatan Tang.
Masalah mana yang menyetujui dequantization ini adalah area penelitian aktif, seperti yang dibahas utas ini . Ini mungkin tergantung pada peringkat matriks yang dipertimbangkan.