Bisakah mesin Turing mensimulasikan komputer kuantum?

62

Saya tahu bahwa mesin Turing 1 secara teoritis dapat mensimulasikan "apa pun", tetapi saya tidak tahu apakah itu dapat mensimulasikan sesuatu yang secara fundamental berbeda dengan komputer berbasis kuantum. Apakah ada upaya untuk melakukan ini, atau adakah yang membuktikannya mungkin / tidak mungkin?

Saya sudah mencari di sekitar, tapi saya bukan ahli dalam topik ini, jadi saya tidak yakin ke mana harus mencari. Saya telah menemukan artikel Wikipedia tentang mesin Turing kuantum , tetapi saya tidak yakin bagaimana tepatnya perbedaannya dari TM klasik. Saya juga menemukan kertas Universal Quantum Turing Machine karya Deutsch , oleh W. Fouché dkk., Tetapi agak sulit untuk dimengerti bagi saya.

1. Dalam hal tidak jelas, dengan mesin Turing yang saya maksud adalah konsep teoritis, bukan mesin fisik (yaitu implementasi dari konsep teoritis).

simulation quantum-turing-machine computability-theory Riker
sumber

Jawaban:

44

Ya , komputer kuantum dapat disimulasikan oleh mesin Turing , meskipun ini tidak boleh dianggap menyiratkan bahwa komputer kuantum dunia nyata tidak dapat menikmati keuntungan kuantum , yaitu keunggulan implementasi yang signifikan dibandingkan komputer klasik dunia nyata.

Sebagai patokan, jika manusia bisa secara manual menggambarkan atau membayangkan bagaimana sesuatu harus beroperasi, imajinasi itu dapat diimplementasikan pada mesin Turing. Komputer kuantum termasuk dalam kategori ini.

Saat ini, motivasi besar untuk komputasi kuantum adalah bahwa qubit dapat eksis di superposisi , pada dasarnya memungkinkan untuk penghitungan paralel masif. Lalu ada anil kuantum dan trik kecil lainnya yang pada dasarnya adalah taktik komputasi analog .

(1)|ψ⟩=α|0⟩+β|1⟩,

Namun, manfaatnya adalah efisiensi. Dalam beberapa kasus, efisiensi yang melampaui astronomi, memungkinkan hal-hal yang tidak praktis pada perangkat keras klasik. Ini menyebabkan komputasi kuantum memiliki aplikasi utama dalam kriptografi dan semacamnya.

Namun, komputasi kuantum saat ini tidak dimotivasi oleh keinginan untuk hal-hal yang pada dasarnya tidak dapat kita lakukan sebelumnya. Jika komputer kuantum dapat melakukan operasi, maka mesin Turing klasik dapat melakukan simulasi komputer kuantum yang melakukan operasi itu.

Keacakan bukan masalah. Saya kira dua alasan utama:

  1. Keacakan dapat lebih tepatnya ditangkap dengan menggunakan matematika distribusi .

  2. Keacakan bukan " hal " yang nyata untuk memulai; itu hanyalah ketidaktahuan. Dan kita selalu bisa menghasilkan ketidaktahuan.

Nat
sumber
7

Untuk mensimulasikan runtuhnya fungsi gelombang Anda perlu sumber keacakan. Jadi Anda akan membutuhkan mesin Turing probabilistik .

Bjørn Kjos-Hanssen
sumber
6
Perangkat klasik dapat menggunakan generator nomor acak yang khas, atau apa pun yang sesuai untuk tujuan mereka. Keacakan bukanlah kualitas fundamental yang perlu bersumber dari mekanika kuantum (yang merupakan kesalahpahaman konsepsi yang cukup besar yang sering didapat orang dari interpretasi Kopenhagen , yang mungkin paling baik dipahami sebagai pendekatan penyederhanaan).
Nat
3
Secara umum jika Anda tidak peduli dengan efisiensi, Anda bisa mencoba setiap elemen dari ruang alih-alih mengambil sampel darinya, menghindari kebutuhan akan keacakan.
Tavian Barnes
2
Jika Anda benar-benar ingin membuat semua efek kuantum yang relevan, Anda harus dapat melanggar ketimpangan Bell dan karenanya mesin Turing probabilistik tidak cukup. Jika Anda hanya ingin mencocokkan kekuatan komputasi dari mesin Turing kuantum, kita dapat menggunakan mesin Turing tanpa keacakan untuk melakukannya. Bagaimanapun, mesin Turing probabilistik tidak akan berguna.
Kadal diskrit
4

Untuk melengkapi apa yang dikatakan orang lain: sejauh yang kami tahu mesin Turing (klasik) tidak dapat benar-benar mensimulasikan korelasi kuantum . Ini secara eksplisit diklaim dalam bagian Properties dari komputer kuantum universal oleh makalah seminalis oleh teori David Deutsch Quantum, prinsip Church-Turing dan komputer kuantum universal (Prosiding Royal Society of London A 400, hal. 97-117 (1985) )).

Detail akan tergantung pada implementasinya atau pada definisi pasti Anda untuk mesin Turing, komputer kuantum, dan terutama simulasi (jika Anda cukup dermawan dengan arti simulasi , apa pun dapat mensimulasikan apa pun). Secara umum, adalah mungkin untuk merancang komputer kuantum yang, ketika berulang kali dioperasikan dengan mulai dari keadaan awal yang sama (atau bit input), dalam setiap operasi menghasilkan bit output acak yang menghadirkan korelasi kuantum tertentu satu sama lain.

Sejauh yang saya tahu, mesin Turing tidak bisa melakukan itu.

agaitaarino
sumber
1
Mungkin bermanfaat untuk menambahkan (Ini mungkin lebih dari pengulangan ulang, tapi yang saya pikir berguna) yang menambahkan 'generasi nomor acak' ke mesin Turing (misalnya sebagai oracle) tidak membantu dalam simulasi Turing kuantum mesin, karena tidak dapat mensimulasikan bit yang melanggar ketimpangan Bell, sedangkan mesin Turing kuantum dapat (seperti yang dinyatakan dalam makalah oleh Deutsch, jika saya membacanya dengan benar).
Kadal diskrit