Mesin Quantum Computing dan Turing: Apakah Mesin Turing masih Ukuran yang Akurat?

Di kelas minggu lalu, profesor saya berkomentar dan mengatakan bahwa mesin Turing digunakan sebagai ukuran / model standar dari apa yang dapat dihitung dan merupakan dasar diskusi yang bermanfaat untuk subjek itu. Dia juga mengatakan bahwa semua varian mesin Turing terbukti setara secara komputasi - baca, sama kuat - satu sama lain. W

Saya berkomentar dan mengatakan kemarin bahwa, mengenai daya komputasi, saya perhatikan bahwa beberapa mesin turing dapat mengambil banyak waktu untuk menghitung sesuatu yang sangat sederhana, sementara mesin turing dengan lebih banyak kaset dapat menghitung sesuatu dalam kompleksitas asimptotik yang lebih rendah sehubungan dengan jumlah tersebut. langkah-langkah yang dibutuhkan.

Dia mengatakan bahwa sehubungan dengan wacana kelas, runtime dari algoritma tertentu pada mesin turing tidak mengubah definisi kemampuan komputasi, atau kekuatan yang kita gunakan untuk mengukur kemampuan komputasi. "Kami prihatin tentang apa yang dapat dihitung, bukan apa yang secara efisien dapat dihitung pada saat ini." Jadi, tidak masalah jika mesin turing memiliki lebih banyak dan lebih banyak kaset, dan semakin banyak kaset menyiratkan bahwa ia dapat menghitung dalam langkah-langkah yang lebih rendah. Oke, saya mengerti bahwa kita benar-benar fokus pada apa yang dapat dihitung IS, bukan kecepatan kita dapat menghitungnya.

Sesuatu tentang hal itu hanya mengganggu saya, karena sampai saat ini, algoritma dengan kompleksitas waktu dan ruang asimptotik yang tidak normal benar-benar menentukan batas dari apa yang, mungkin harus saya katakan, secara praktis, dapat dihitung.

Jadi, saya punya beberapa pertanyaan:

1. Misalkan kita memiliki model untuk mesin turing kuantum , ini harus setara dengan mesin turing "biasa", kan?

Jadi, jawaban untuk pertanyaan itu saya pikir benar-benar mengarah pada alasan saya menulis posting ini. Apakah teknologi komputasi kuantum kuno definisi klasik dari apa yang dapat dihitung melalui mesin turing?

2. Apakah ini sesuatu di atas kepala saya dan haruskah saya menghapus posting ini? Saya tidak bermaksud dewasa sebelum waktunya, saya hanya tidak melihat pertanyaan yang mirip dengan saya.

Anda mencampuradukkan teori komputasi (juga dikenal sebagai teori rekursi ) dan teori kompleksitas (atau kompleksitas komputasi ). Teori komputabilitas adalah subjek matematika yang luas yang mempelajari konsekuensi dari konsep komputasi . Itu tidak berurusan dengan kompleksitas perhitungan. Seperti yang disebutkan oleh profesor Anda, semua model perhitungan (Turing-complete) adalah sama dari sudut pandang teori komputasi. Teori komputabilitas, meskipun subjek matematika yang menarik, bukan model yang baik untuk perhitungan dunia nyata karena alasan ini, seperti yang Anda sebutkan.

Teori kompleksitas memulai hidupnya sebagai upaya untuk mengatasi masalah ini. Teori kompleksitas mempelajari betapa sulitnya, dalam hal waktu dan ruang, untuk menghitung predikat dan fungsi tertentu. Dari sudut pandang teori kompleksitas, tidak semua model perhitungan adalah sama, dan mesin Turing diambil sebagai model referensi. Namun, bahkan teori kompleksitas tidak terlalu realistis, karena ia memperlakukan semua model komputasi yang secara polinomi setara dengan mesin Turing dengan cara yang sama (dua model setara secara polinomi jika ada masalah yang dapat diselesaikan dalam waktu dan ruang dalam satu model dapat diselesaikan dalam waktu dan spasi di yang lain, di mana adalah ukuran input danS ( n ) T ( n ) c S ( n ) c n c O ( 1 ) O ( n log n ) Ω ( n 2$T(n)$$S(n)$$T(n)^c$$S(n)^c$$n$$c$ adalah konstanta positif). Sebagai contoh, mesin Turing bukan model yang baik untuk komputer nyata karena mereka tidak mendukung akses acak (mengakses titik sembarang dalam memori dalam waktu ). Tentu saja, akses acak dapat disimulasikan oleh mesin Turing, tetapi simulasi bisa lambat. Sering dikatakan bahwa penyortiran dapat dilakukan dalam waktu , tetapi ini bukan kasus untuk mesin Turing, yang mungkin membutuhkan atau bergerak bahkan untuk menyortir bilangan bulat. Karena itu di bidang algoritma , model lain seperti mesin RAM menggantikan mesin Turing.$O(1)$$O(n\log n)$$\Omega(n^2)$

Akhirnya, komputer kuantum dapat dimodelkan dengan beberapa cara berbeda, seperti mesin Turing kuantum. Segala sesuatu yang dapat dihitung dengan menggunakan komputer kuantum juga dapat dihitung dengan menggunakan komputer klasik, dan dari sudut pandang teori komputasi, mesin Turing kuantum hanyalah model lain yang setara. Namun, mesin Turing kuantum secara luas dikira tidak secara politis setara dengan mesin Turing klasik: misalnya, pemfaktoran dan logaritma diskrit adalah "mudah" untuk mesin Turing kuantum (dapat dipecahkan dalam waktu polinomial), sementara itu dikira bahwa mereka "keras" untuk mesin Turing klasik (tidak dapat dipecahkan dalam waktu polinomial; meskipun beberapa orang berpikir bahwa anjak bilangan bulat mungkin dapat dipecahkan dalam waktu polinomial). Jadi dari sudut pandang teori kompleksitas, berbeda dari mesin Turing klasik.