Dalam Mesin Quantum Turing, bagaimana keputusan untuk bergerak di sepanjang pita memori dibuat?

14

Biarkan, untuk mesin Quantum Turing (QTM), keadaan ditetapkan menjadi , dan alfabet simbol menjadi = { 0 , 1 } , yang muncul di kepala kaset. Kemudian, sesuai pemahaman saya, pada waktu tertentu sedangkan QTM adalah menghitung, qubit yang muncul di kepala akan mengadakan sebarang vektor V Σ = a | 1 + b | 0 . Juga, jika | q 0, | q 1, . . . QQ={0,1}V=a|1+b|0|q0,|q1,...Q, maka vektor keadaan pada saat itu juga akan menjadi vektor arbitrer .Vq=b0|q0+b1|q1+...

Sekarang, setelah siklus instruksi selesai, vektor dan V q akan memutuskan apakah QTM akan bergerak ke kiri atau kanan sepanjang pita qubit. Pertanyaan saya adalah- karena ruang Hilbert yang dibentuk oleh Q adalah himpunan tak terbatas yang tak terhitung dan { Kiri, Kanan } adalah himpunan diskrit, pemetaan di antara mereka akan sulit untuk dibuat.VVqQ{Left,Right}

Jadi bagaimana keputusan untuk bergerak ke kiri atau kanan dibuat? Apakah QTM bergerak baik kiri dan kanan pada saat yang sama, yang berarti bahwa himpunan juga membentuk ruang Hilbert yang berbeda, dan karenanya gerakan QTM menjadi sesuatu seperti sebuah | Kiri + b | Benar .{Left,Right}a|Left+b|Right

Atau, seperti mesin Turing Klasik, QTM bergerak ke kiri atau kanan, tetapi tidak keduanya sekaligus?

Prem kumar
sumber
Lihat apakah ini membantu Bagaimana QTM menghitung
Pirate X
@PirateX Saya telah membaca posting itu, tetapi saya tidak mengerti apakah status internal dari QTM adalah entitas klasik atau Quantum. Bisakah itu terjadi di superposisi dari berbagai kondisi internal? Juga, dapatkah QTM bergerak ke kiri dan ke kanan di sepanjang pita memori itu pada saat yang sama? Q
Prem kumar

Jawaban:

7

Jika kita memiliki QTM dengan set negara dan alfabet pita Σ = { 0 , 1 } , kita tidak bisa mengatakan bahwa qubit yang dipindai oleh kepala kaset "memegang" vektor a | 0 + b | 1 atau bahwa (internal) negara adalah vektor dengan dasar negara sesuai dengan Q . Qubit pada pita dapat dikorelasikan satu sama lain dan dengan keadaan internal, serta dengan posisi kepala pita.QΣ={0,1}a|0+b|1Q

Sebagai analogi, kami tidak akan menggambarkan keadaan global mesin Turing yang probabilistik dengan secara independen menentukan distribusi untuk keadaan internal dan untuk masing-masing kotak pita. Sebaliknya, kita harus menggambarkan semuanya bersama-sama sehingga dapat mewakili korelasi di antara bagian mesin yang berbeda. Sebagai contoh, bit yang disimpan dalam dua kotak kaset jauh mungkin berkorelasi sempurna, baik 0 dengan probabilitas 1/2 dan keduanya 1 dengan probabilitas 1/2.

Jadi, dalam kasus kuantum, dan dengan asumsi kita sedang berbicara tentang keadaan murni mesin kuantum Turing dengan evolusi kesatuan (sebagai lawan dari model yang lebih umum berdasarkan keadaan campuran), keadaan global diwakili oleh vektor yang entrinya diindeks oleh konfigurasi (yaitu, deskripsi klasik dari keadaan internal, lokasi kepala pita, dan isi dari setiap pita persegi) dari mesin Turing. Perlu dicatat bahwa kita umumnya mengasumsikan bahwa ada simbol kosong khusus dalam alfabet pita (yang bisa 0 jika kita ingin kotak kaset kita untuk menyimpan qubit) dan bahwa kita memulai perhitungan dengan paling tidak banyak kotak yang kosong, sehingga himpunan semua konfigurasi yang terjangkau dapat dihitung. Ini berarti bahwa negara akan diwakili oleh vektor satuan dalam ruang Hilbert yang dapat dipisahkan.

Akhirnya, dan mungkin ini adalah jawaban aktual untuk pertanyaan yang diartikan secara harfiah, gerakan kepala pita ditentukan oleh fungsi transisi, yang akan menetapkan "amplitudo" untuk setiap tindakan yang mungkin (keadaan baru, simbol baru, dan gerakan kepala pita) ) untuk setiap pasangan klasik (q,σ)

Misalnya, Anda dapat membayangkan QTM dengan danQ={0,1}Σ={0,1}(dan kami akan menganggap 0 sebagai simbol kosong). Kita mulai dalam keadaan 0 memindai kotak yang menyimpan 1, dan semua kotak lain menyimpan 0. Saya tidak akan secara eksplisit menuliskan fungsi transisi, tetapi hanya akan menggambarkan perilaku dalam kata-kata. Pada setiap gerakan, isi kotak kaset yang dipindai ditafsirkan sebagai bit kontrol untuk operasi Hadamard pada kondisi internal. Setelah Hadamard yang dikontrol dilakukan, kepala bergerak ke kiri jika kondisi (baru) adalah 0 dan bergerak ke kanan jika kondisi (baru) adalah 1. (Dalam contoh ini kita tidak pernah benar-benar mengubah isi rekaman itu.) Setelah satu langkah , QTM akan berada dalam superposisi dengan bobot yang sama antara berada dalam keadaan 0 dengan pita pemindaian kepala pita -1, dan berada dalam keadaan 1 dengan persegi pemindaian pita kepala +1. Pada semua gerakan selanjutnya, Hadamard yang dikontrol tidak melakukan apa-apa karena setiap kotak selain dari kotak 0 berisi simbol 0. Karenanya, tape head akan terus bergerak secara simultan baik kiri dan kanan, seperti partikel yang bergerak ke kiri dan ke kanan dalam superposisi.

Jika Anda mau, tentu saja Anda dapat menentukan varian model mesin Turing kuantum yang lokasi dan gerakan head tape menjadi deterministik, dan ini tidak akan merusak universalitas komputasi model, tetapi definisi "klasik" dari kuantum Turing mesin tidak memaksakan pembatasan ini.

John Watrous
sumber
1
@Premkumar: Sebagai catatan kaki untuk jawaban ini --- jika Anda mencari referensi resmi untuk akun QTMs ini, tempat yang baik untuk dipertimbangkan adalah karya seminal "Teori kompleksitas kuantum" oleh Bernstein dan Vazirani (Proc. 25 Tahunan Tahunan ACM STOC (hal.1411–1473), 1997 [tautan PDF gratis di citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.144.7852 ]. Hampir semua komentar John di atas pada dasarnya merupakan perluasan dari Definisi 3.2 dalam artikel itu, dan beberapa diskusi di Bagian yang sama
Niel de Beaudrap 5'18
@Niel: Saya tidak yakin apakah Anda dapat mengedit komentar, tetapi karena saya yakin Anda tahu versi konferensi makalah Bernstein dan Vazirani muncul pada 1993, bukan 1997. Versi jurnal 1997 muncul di SIAM Journal of Computing (di masalah khusus yang benar-benar monumental dalam komputasi kuantum).
John Watrous
Cukup benar, dan bahkan tautan PDF gratis menggambarkan tahun 1993; Saya sepertinya mendapatkan beberapa kabel yang disilangkan. (Komentar dapat diedit hingga 10 menit.)
Niel de Beaudrap
@NieldeBeaudrap Koreksi kecil: hingga 5 menit :) (untuk pengguna normal). Mod dapat mengedit komentar, kapan saja.
Sanchayan Dutta
4

Mesin Turing kuantum dapat bergerak ke superposisi bergerak ke kiri dan ke kanan. Ini berbeda dari mesin Turing klasik yang hanya bisa bergerak ke kiri atau ke kanan.

piramida
sumber