Comment définir les machines de Turing quantiques?

Dans le calcul quantique, quel est le modèle équivalent d'une machine de Turing? Il est tout à fait clair pour moi que les circuits quantiques puissent être construits à partir de portes quantiques, mais comment pouvons-nous définir une machine de Turing quantique (QTM) pouvant réellement bénéficier d'effets quantiques, à savoir fonctionner sur des systèmes de grande dimension?

^{( Remarque : la description complète est un peu complexe et comporte plusieurs subtilités que je préférais ignorer. Ce qui suit est simplement les idées de haut niveau pour le modèle QTM)}

Lors de la définition d'une machine Quantum Turing (QTM), on souhaiterait disposer d'un modèle simple, similaire au TM classique (c'est-à-dire une machine à états finis plus une bande infinie), tout en laissant au nouveau modèle l'avantage de la mécanique quantique.

Comme pour le modèle classique, QTM a:

1. - un ensemble fini d'états. Soit q 0 un état initial.$Q=\{q_0,q_1,..\}$$q_0$
2. , Γ = { γ 0 , . . } - jeu d'alphabet d'entrée / de travail$\Sigma=\{\sigma_0,\sigma_1,...\}$$\Gamma=\{\gamma_0,..\}$
3. un ruban infini et une seule "tête".

$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$

La chose intéressante à noter est que chaque "étape" de l'état du QTM est une superposition de configurations possibles, ce qui confère au QTM l'avantage "quantique".

La réponse est basée sur Masanao Ozawa, Sur le problème de l’arrêt des machines Quantum Turing . Voir aussi David Deutsch, théorie quantique, principe de Church-Turing et ordinateur quantique universel .

Comme l'indiquent les notes, la manière de définir un QTM consiste à définir la fonction de transition en tant que transformation unitaire d'état et de lettre. Ainsi, à chaque étape, vous imaginez multiplier le vecteur (état, lettre) par une transformation pour en obtenir un nouveau (état, lettre). Ce n'est pas particulièrement pratique, mais cela peut être défini.