Bagaimana cara mendefinisikan mesin kuantum Turing?

Dalam perhitungan kuantum, apa model yang setara dari mesin Turing? Sangat jelas bagi saya bagaimana sirkuit kuantum dapat dibangun dari gerbang kuantum, tetapi bagaimana kita dapat mendefinisikan mesin Turing kuantum (QTM) yang benar-benar dapat mengambil manfaat dari efek kuantum, yaitu, bekerja pada sistem dimensi tinggi?

^{( catatan : penjelasan lengkap agak rumit, dan memiliki beberapa seluk yang saya lebih suka abaikan. Berikut ini hanyalah gagasan tingkat tinggi untuk model QTM)}

Ketika mendefinisikan mesin Quantum Turing (QTM), orang ingin memiliki model sederhana, mirip dengan TM klasik (yaitu, mesin keadaan terbatas ditambah pita tak terbatas), tetapi memungkinkan model baru keuntungan mekanika kuantum.

Mirip dengan model klasik, QTM memiliki:

1. - seperangkat status terbatas. Biarkan q 0 menjadi kondisi awal.$Q=\{q_0,q_1,..\}$$q_0$
2. , Γ = { γ 0 , . . } - set input / alfabet yang berfungsi$\Sigma=\{\sigma_0,\sigma_1,...\}$$\Gamma=\{\gamma_0,..\}$
3. pita tak terbatas dan satu "kepala".

$C=(q,T,i)$$q\in Q$$T\in \Gamma^*$$i$

$\mathcal{H}$$Q\times\Sigma^*\times \mathrm{Z}$$C=(q,T,i)$

$|\psi(0)\rangle = |q_0\rangle |T_0\rangle |1\rangle$$T_0\in \Gamma^*$$x\in\Sigma^*$

$U$

$n$$|\psi(n)\rangle = U^n|\psi(0)\rangle$$U$$\langle q',T',i'|U|q,T,i\rangle$$i'= i \pm 1$$T'$$T$$i$

$q_f$

Hal yang menarik untuk diperhatikan, adalah bahwa setiap "langkah" keadaan QTM adalah superposisi dari kemungkinan konfigurasi, yang memberi QTM keuntungan "kuantum".

Jawabannya didasarkan pada Masanao Ozawa, On the Halting Problem untuk Quantum Turing Machines . Lihat juga David Deutsch, teori Quantum, prinsip Church-Turing dan komputer kuantum universal .

Seperti yang ditunjukkan oleh catatan, cara untuk mendefinisikan QTM adalah dengan mendefinisikan fungsi transisi sebagai transformasi kesatuan negara dan huruf. Jadi di setiap langkah, Anda membayangkan mengalikan vektor (negara bagian, huruf) dengan transformasi untuk mendapatkan yang baru (negara bagian, huruf). Ini tidak terlalu nyaman, tetapi dapat didefinisikan.