Macchina di Turing quantistica

Una macchina di Turing quantistica (MTQ), detta anche computer quantistico universale, è una macchina astratta usata per modellare l'effetto di un computer quantistico. Essa fornisce un modello molto semplice che cattura tutta la potenza della computazione quantistica. Qualsiasi algoritmo quantistico può essere espresso formalmente come una particolare macchina di Turing quantistica. Tali macchine di Turing furono proposte per la prima volta in uno studio del 1985 scritto dal fisico dell'Università di Oxford David Deutsch che suggeriva che le porte quantistiche potessero funzionare in maniera simile alle tradizionali porte logiche binarie dei computer digitali. Le macchine di Turing quantistiche non si usano sempre per analizzare una computazione quantistica; il è un modello più comune; questi modelli sono computazionalmente equivalenti. Le macchine di Turing quantistiche possono essere legate alle macchine di Turing classiche e probabilistiche in una cornice basata sulle matrici di transizione, mostrate da . Iriyama, e Volovich hanno sviluppato un modello di macchina di Turing quantistica lineare (MTQL). Questa è una generalizzazione di una MTQ classica che ha stati misti e che consente funzioni di transizione irreversibili. Queste permettono la rappresentazione di misurazioni quantistiche senza esiti classici. Una macchina di Turing quantistica con fu definita da Scott Aaronson, che dimostrò che la classe del tempo polinomiale su tale macchina è uguale alla classe di complessità classica .