Mașină Quantum Turing
| Este suficient un computer cuantic universal pentru a simula eficient un sistem fizic arbitrar? |
O mașină cuantică Turing ( MTQ ), numită și un computer cuantic universal , este o mașină abstractă utilizată pentru a modela efectul unui computer cuantic . Oferă un model foarte simplu care surprinde întreaga putere a calculului cuantic. Orice algoritm cuantic poate fi exprimat formal ca o anumită mașină cuantică Turing. Astfel de mașini Turing au fost propuse pentru prima dată într-un studiu din 1985 scris de fizicianul David Deutsch al Universității Oxford , care sugerează că porțile cuantice ar putea funcționa similar cu porțile logice binare tradiționale din computerele digitale. [1]
Mașinile Turing cuantice nu sunt întotdeauna utilizate pentru a analiza un calcul cuantic; circuitul cuantic este un model mai comun; aceste modele sunt echivalente din punct de vedere al calculului. [2]
Mașinile Turing cuantice pot fi legate de mașinile Turing clasice și probabilistice într-un cadru bazat pe matrici de tranziție , prezentate de Lance Fortnow . [3]
Iriyama, Ohya și Volovich au dezvoltat un model de mașină cuantică liniară Turing (MTQL). Aceasta este o generalizare a unui MTQ clasic care are stări mixte și care permite funcții de tranziție ireversibile. Acestea permit reprezentarea măsurătorilor cuantice fără rezultate clasice. [4]
O mașină cuantică post-selecție Turing a fost definită de Scott Aaronson , care a dovedit că clasa de timp polinomială pe o astfel de mașină ( PostBQP ) este egală cu clasa clasică de complexitate PP . [5]
Notă
- ^ David Deutsch, teoria cuantică, principiul Church-Turing și computerul cuantic universal ( PDF ), în Proceedings of the Royal Society A , vol. 400, n. 1818, iulie 1985, pp. 97–117, Bibcode : 1985RSPSA.400 ... 97D , DOI : 10.1098 / rspa.1985.0070 (arhivat din original la 23 noiembrie 2008) .
- ^ Andrew Yao , Proceedings of the 34th Symposium Annual on Foundations of Computer Science , Quantum circuit complex , 1993, pp. 352–361.
- ^ Lance Fortnow, One Complexity Theorist 's View of Quantum Computing , în Theoretical Computer Science , vol. 292, nr. 3, 2003, pp. 597-610, DOI : 10.1016 / S0304-3975 (01) 00377-2 .
- ^ Simon Perdrix și Philippe Jorrand, Calcul cuantic controlat clasic , în matematică. Struct. În Comp. Știință , vol. 16, n. 4, 4 aprilie 2007, pp. 601–620, DOI : 10.1017 / S096012950600538X , arXiv : quant-ph / 0407008 . De asemenea, Simon Perdrix și Philippe Jorrand, Calcul cuantic controlat clasic ( PDF ), în matematică. Struct. În Comp. Știință , vol. 16, n. 4, 2006, pp. 601–620, DOI : 10.1017 / S096012950600538X .
- ^ Scott Aaronson, Quantum computing, postselection și probabilistic polynomial-time , în Proceedings of the Royal Society A , vol. 461, n. 2063, 2005, pp. 3473–3482, Bibcode : 2005RSPSA.461.3473 , DOI : 10.1098 / rspa.2005.1546 . Pre-presare disponibilă pe [1]
Lecturi suplimentare
- ( EN ) Satoshi Iriyama, Masanori Ohya și Igor Volovich, Generalized Quantum Turing Machine și aplicarea sa la algoritmul SAT al haosului , 2004, arXiv : quant-ph / 0405191 .
- ( RO ) Extras din studiul lui Deutsch , pe links.jstor.org .
- ( EN ) Computerul cuantic - istorie , la ffden-2.phys.uaf.edu .
