Macchina di Turing quantistica
Un computer quantistico universale è sufficiente per simulare efficientemente un sistema fisico arbitrario? |
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.[1]
Le macchine di Turing quantistiche non si usano sempre per analizzare una computazione quantistica; il circuito quantistico è un modello più comune; questi modelli sono computazionalmente equivalenti.[2]
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 Lance Fortnow.[3]
Iriyama, Ohya 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.[4]
Una macchina di Turing quantistica con post-selezione fu definita da Scott Aaronson, che dimostrò che la classe del tempo polinomiale su tale macchina (PostBQP) è uguale alla classe di complessità classica PP.[5]
Note
[modifica | modifica wikitesto]- ^ David Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer (PDF), in Proceedings of the Royal Society A, vol. 400, n. 1818, luglio 1985, pp. 97–117, Bibcode:1985RSPSA.400...97D, DOI:10.1098/rspa.1985.0070 (archiviato dall'url originale il 23 novembre 2008).
- ^ Andrew Yao, Proceedings of the 34th Annual Symposium on Foundations of Computer Science, Quantum circuit complexity, 1993, pp. 352–361.
- ^ Lance Fortnow, One Complexity Theorist's View of Quantum Computing, in Theoretical Computer Science, vol. 292, n. 3, 2003, pp. 597–610, DOI:10.1016/S0304-3975(01)00377-2.
- ^ Simon Perdrix e Philippe Jorrand, Classically-Controlled Quantum Computation, in Math. Struct. In Comp. Science, vol. 16, n. 4, 4 aprile 2007, pp. 601–620, DOI:10.1017/S096012950600538X, arXiv:quant-ph/0407008. Inoltre Simon Perdrix and Philippe Jorrand, Classically-Controlled Quantum Computation (PDF), in Math. Struct. In Comp. Science, vol. 16, n. 4, 2006, pp. 601–620, DOI:10.1017/S096012950600538X.
- ^ Scott Aaronson, Quantum computing, postselection, and probabilistic polynomial-time, in Proceedings of the Royal Society A, vol. 461, n. 2063, 2005, pp. 3473–3482, Bibcode:2005RSPSA.461.3473, DOI:10.1098/rspa.2005.1546. Prestampa disponibile su [1]
Bibliografia
[modifica | modifica wikitesto]- (EN) Satoshi Iriyama, Masanori Ohya e Igor Volovich, Generalized Quantum Turing Machine and its Application to the SAT Chaos Algorithm, 2004, arXiv:quant-ph/0405191.
- (EN) Estratto dello studio di Deutsch, su links.jstor.org.
- (EN) Il computer quantistico – storia, su ffden-2.phys.uaf.edu.