Máquina de Turing quântica

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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. (July 1985). "Quantum theory, the Church-Turing principle and the universal quantum computer". Proceedings of the Royal Society of London; Series A, Mathematical and Physical Sciences 400 (1818): pp. 97–117. DOI:10.1098/rspa.1985.0070. Bibcode1985RSPSA.400...97D.
  2. Andrew Yao (1993). "Quantum circuit complexity". Proceedings of the 34th Annual Symposium on Foundations of Computer Science: 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. (2007-04-04) "Classically-Controlled Quantum Computation". Math. Struct. In Comp. Science 16 (4): 601–620. 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. DOI:10.1098/rspa.2005.1546. Bibcode2005RSPSA.461.3473A. Preprint available at [1]