Máquina de Turing quântica

Uma máquina de Turing quântica, ou também computador quântico universal é uma máquina abstrata usada para modelar o efeito de um computador quântico. Ela provê um modelo muito simples que captura todo o poder da computação quântica. Qualquer algoritmo quântico pode ser expressado formalmente como uma máquina de Turing quântica. Tais máquinas de Turing foram primeiramente propostas num periódico de 1985 escrito pelo físico da Universidade de Oxford David Deutsch, sugerindo que portais quânticos poderiam funcionar de maneira similar à computação digital tradicional das portas lógicas binárias.^[1]

Máquinas de Turing quânticas não são sempre usadas para analisar computação quântica; o circuito quântico é um modelo mais comum; esses modelos são computacionalmente equivalentes.^[2]

Máquinas de Turing quânticas podem se relacionar com máquinas clássicas e probabilísticas num framework baseado em matrizes de transição, como mostrado por Lance Fortnow.^[3]

Iriyama, Ohya, e Volovich desenvolveram um modelo de uma Máquina de Turing Quântica Linear (LQTM). É uma generalização da máquina quântica clássica, que tem estados misturados e permite funções de transição irreversíveis. Estes permitem a representação de medidas quânticas sem consequências clássicas.^[4]

Uma máquina de Turing quântica com pós-seleção foi definida por Scott Aaronson, que mostrou que a classe de tempo polinomial em tal máquina (PostBQP) é igual à classe de complexidade clássica PP.^[5]

Referências

1. Deutsch, David (julho de 1985). «Quantum theory, the Church-Turing principle and the universal quantum computer» (PDF). Proceedings of the Royal Society of London; Series A, Mathematical and Physical Sciences. 400 (1818): 97–117. Bibcode:1985RSPSA.400...97D. doi:10.1098/rspa.1985.0070. Consultado em 5 de julho de 2012. Arquivado do original (PDF) em 23 de novembro de 2008
2. Andrew Yao (1993). «Quantum circuit complexity». Proceedings of the 34th Annual Symposium on Foundations of Computer Science. pp. 352–361
3. Lance Fortnow (2003). «One Complexity Theorist's View of Quantum Computing». Theoretical Computer Science. 292 (3): 597–610. doi:10.1016/S0304-3975(01)00377-2
4. Simon Perdrix; Philippe Jorrand (4 de abril de 2007). «Classically-Controlled Quantum Computation». Math. Struct. In Comp. Science. 16 (4): 601–620. arXiv:quant-ph/0407008. doi:10.1017/S096012950600538X also Simon Perdrix and Philippe Jorrand (2006). «Classically-Controlled Quantum Computation» (PDF). Math. Struct. In Comp. Science. 16 (4): 601–620. doi:10.1017/S096012950600538X
5. Aaronson, Scott (2005). «Quantum computing, postselection, and probabilistic polynomial-time». Proceedings of the Royal Society A. 461 (2063): 3473–3482. Bibcode:2005RSPSA.461.3473A. doi:10.1098/rspa.2005.1546 Preprint available at