Màquina de Turing quàntica

Una màquina de Turing quàntica és una màquina abstracta usada per modelar els efectes d'un computador quàntic. Proporciona un model molt simple que captura tota la potència de la computació quàntica. Qualsevol algorisme quàntic es pot expressar formalment com una màquina de Turing quàntica particular. Van ser proposades per primer cop el 1985 pel físic David Deutsch en un article on suggeria que les portes lògiques quàntiques podrien funcionar d'una forma similar a les tradicionals portes lògiques binàries.

No sempre es fan servir màquines de Turing quàntiques per modelar computadors quàntics, molts cops es fan servir circuits quàntics, que son equivalents.

Les màquines de Turing quàntiques es poden relacionar amb les màquines de Turing clàssiques mitjançant l'ús de matrius estocàstiques, tal com va demostrar Lance Fortnow.

També s'ha definit la màquina de Turing quàntica amb postselecció, que pel que fa al temps d'execució (classe PostBQP) és equivalent a la classe de complexitat PP.

Definició

Una forma d'entendre aquesta màquina de Turing és veient que generalitza la màquina de Turing clàssica de la mateixa manera que els autòmats finits quàntics generalitzen els autòmats finits. En essència, els estats interns clàssics de la màquina de Turing es canvien per estats purs o mixtes d'un espai de Hilbert. La funció de transició es canvia per un conjunt de matrius unitàries que mapen l'espai de Hilbert cap a si mateix.

Sigui una màquina de Turing clàssica descrita per la 7-tupla $M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle$.

Per una màquina quàntica de Turing amb 3 cintes (una per l'entrada, una pels càlculs parcials i una per la sortida):

• el conjunt d'estats Q es canvia per un espai de Hilbert
• els símbols de l'alfabet $\Gamma$ es canvien per un espai de Hilbert (normalment un espai de Hilbert diferent al conjunt d'estats)
• el símbol buit $b\in \Gamma$ es correspon al vector nul
• els símbols d'entrada i sortida $\Sigma$ normalment s'agafen com un conjunt discret com a la màquina clàssica.
• la funció de transició $\delta :\Sigma \times Q\otimes \Gamma \rightarrow \Sigma \times Q\otimes \Gamma \times \{L,R\}$ és una generalització d'un monoide de transició i s'entén com una col·lecció de matrius unitàries que son automorfismes de l'espai de Hilbert Q.
• l'estat inicial $q_{0}\in Q$ pot ser un estat quàntic pur o mixt
• el conjunt F del conjunt d'estats finals acceptats és un subespai de Hilbert Q