|
==Origini==
La [[macchina di Turing]] (MT) utilizza gli [[Assioma|assiomi]] della [[fisica classica]], ossia lo stato del nastro e della testina sono sempre univocamente identificabili, gli spostamenti sono sempre regolati dalle leggi del moto, etc. Quindi la MT è totalmente deterministica (MTD). Una sua variante, che si dimostra equivalente ma più veloce, è la [[macchina di Turing probabilistica]] (MTP). Può risolvere ogni problema cherisolvibile è possibile risolvere tramite lavia MTD, ma di solito lo fa più velocemente (nel senso della [[teoria della complessità algoritmica]]). Anch'essa, però, è soggetta agli assiomi della fisica classica, e soprattutto nessuna delle due è reversibile, per il [[secondo principio della termodinamica]]. Dato che la [[meccanica quantistica]] è reversibile, lo è anche una [[macchina di Turing quantistica]] (MTQ) deve essere reversibile. Inoltre deve rispettare i [[postulati della meccanica quantistica|vincoli della meccanica quantistica]], tra cui il [[principio di indeterminazione di Heisenberg]] e l'[[equazione di Schrödinger]].
Lo sviluppo di una MTQ, e quindi di un calcolatore quantistico, ha richiesto, come spesso avviene, diversi passaggi.
Nel [[1973]] [[Charles Bennet]] dimostrò che è possibile costruire una MT reversibile. Nel 1980, [[Paul Benioff]] ha dimostratodimostrò che la reversibilità è una condizione necessaria per realizzare una MTQ. Due anni dopo [[Richard Feynman]] pubblicò il suo famoso lavoro sul [[computer quantistico]]. In esso, stabilisce che:
#Una MTD può simulare un sistema quantistico solo con un rallentamento esponenziale (nel senso della [[teoria della complessità algoritmica]]).
#Un computer basato sui [[qubit]] non è soggetto a tale limitazione, ed è dunque un ''simulatore quantistico universale''.
Finalmente, nel [[1985]], [[David Deutsch]] dell'[[Università di Oxford]] descrivedescrisse la prima vera MTQ.
I primi prototipi di computer a qubit sono statifurono realizzati dal Centro ricerche dell'IBM di Almaden nel 1997, misurando lo spin dei nuclei atomici di particolari molecole tramite la [[risonanza magnetica nucleare]]. Sono stati realizzati "processori" a 5 e 7 qubit, con cui tra l'altro è stato applicato per la prima volta l'[[algoritmo di fattorizzazione di Shor]]
==Principi dell'informatica quantistica ==
| 