Apakah artikel ini menyiratkan bahwa Turing-Computability tidak sama dengan "computable secara efektif"?

Pertama-tama, saya minta maaf jika ini ditanyakan, tetapi saya benar-benar tidak menemukan apa pun.

Saya menemukan artikel ini . Dikatakan bahwa ada masalah yang hanya bisa diselesaikan oleh Komputer Quantum. Dalam pemahaman saya, ini harus berarti, secara intuitif, bahwa masalah ini "dapat dihitung secara efektif", karena kita memiliki metode yang efektif dan nyata untuk menghitungnya: membangun komputer kuantum dan menyelesaikannya. Tapi, karena Turing Machine (mesin turing bukan komputer kuantum, saya pikir?) Tidak bisa menyelesaikannya, ini bukan turing-computable.

Oleh karena itu, apakah ini berarti bahwa "efektif dihitung" dan "turing-dapat dihitung" bukanlah konsep yang sama? Jadi, apakah tesis Church-Turing salah? Intuisi saya mengatakan "tidak", karena dalam hal ini, ini akan menjadi berita yang sangat besar. Jadi, jika tidak, mengapa tidak?

Juga, saya sadar bahwa sudah ada model komputasi yang lebih kuat daripada mesin turing, tetapi itu hanya "teori", bukan? Komputer kuantum, di sisi lain, secara fisik dapat dibangun.

Ada banyak arti kata "bisa". Apakah ada algoritma yang dapat memecah enkripsi AES-512? Salah satu strategi adalah mengambil semua blok 2 ^ 512 yang mungkin dari 512 bit, mengenkripsi semuanya dengan kunci publik, dan untuk masing-masing memeriksa apakah cocok dengan ciphertext. Dalam arti abstrak murni, ini adalah algoritma yang "dapat" memecahkan AES-512. Dari sudut pandang praktis, mengubah semua materi di alam semesta yang diketahui menjadi komputer, dan menjalankan program pada mereka sampai kematian panas alam semesta, tidak akan dapat memeriksa semua 2 ^ 512 blok.

Dengan demikian, ada konsep abstrak, teoritis "bisa" yang tidak memperhitungkan jumlah sumber daya yang dibutuhkan, dan makna praktis yang melakukannya.

Turing Computability berkaitan dengan jenis "kaleng" pertama. Mesin Turing adalah perangkat yang diizinkan berjalan untuk waktu yang tidak terbatas dengan memori tidak terbatas. Ini adalah model abstrak yang digunakan untuk merumuskan klaim teoritis. Tidak ada TM yang benar-benar ada di dunia nyata.

Dengan demikian, tidak ada kontradiksi antara mengklaim, di satu sisi, bahwa apa pun yang dapat dilakukan komputer kuantum, TM juga dapat melakukannya, dan di sisi lain mengklaim bahwa ada masalah yang dapat diselesaikan oleh komputer kuantum, tetapi tidak ada komputer klasik yang dapat melakukannya. memecahkan; komputer yang sebenarnya akan memiliki batasan daya komputer yang tidak dimiliki TM.

Pertama-tama, komputer kuantum (atau lebih tepatnya, model perhitungan kuantum teoretis), pada kenyataannya, tidak lebih kuat dari mesin Turing, dalam arti bahwa mereka dapat ditiru pada mesin Turing dan dapat meniru mesin Turing sendiri. Perhatikan bahwa artikel itu sendiri tidak menggunakan kata 'computable', dan untuk alasan yang bagus. Komputasi bukan apa yang mereka bicarakan.

Perbedaan antara komputer kuantum dan yang klasik adalah kecepatan. Di sinilah teori kompleksitas masuk. Di sini, semua masalah yang kami anggap dapat dihitung, tetapi beberapa mungkin sangat tidak efisien untuk diselesaikan dalam hal waktu berjalan asimtotik atau penggunaan memori.

Hierarki polinomial (PH) adalah kelas besar yang berisi masalah yang pada dasarnya merupakan permainan bolak-balik antara menebak solusi secara non-deterministik dan menemukan satu (atau lebih tepatnya, bolak-balik bilangan eksistensial dan universal), tetapi semuanya dalam waktu polinomial. P adalah kelas paling dasar di dalam PH dan kira-kira sesuai dengan masalah yang dapat kita pecahkan dalam waktu yang wajar pada komputer klasik. NP adalah subkelas dasar lain dari PH.

BQP adalah analog untuk P untuk komputer kuantum. Yah, tidak sepenuhnya, BQP lebih dekat ke BPP, di mana kami mengizinkan komputer klasik kami memberikan jawaban yang salah dengan probabilitas yang kecil. Efek kuantum tidak dapat benar-benar dieksploitasi tanpa melibatkan probabilitas secara bermakna. Bagaimanapun, BPP masih dalam PH.

Artikel ini adalah tentang masalah yang telah terbukti tidak terletak pada PH, tetapi pada BQP. Di satu sisi, 'langkah kuantum' memungkinkan untuk memecahkan masalah yang bahkan tidak dekat dengan P atau BPP secara klasik, bahkan dalam hierarki tak terbatas yang sama, dalam waktu polinomial pada komputer kuantum. Jadi, ini adalah bukti kuat untuk kekuatan (teoritis) dari model komputasi kuantum.

Adapun tesis Gereja-Turing, perhitungan kuantum menjadi lebih cepat daripada klasik tidak bertentangan, karena tesis tidak peduli tentang waktu perhitungan. Tesis Extended Church-Turing yang lebih kuat , bagaimanapun, mendapat kontradiksi dengan hasil ini (yaitu, jika komputer kuantum scalable benar-benar dibangun)