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 poderiam funcionar de maneira similar à computação digital tradicional das portas lógicas binárias. Máquinas de Turing quânticas não são sempre usadas para analisar computação quântica; o é um modelo mais comum; esses modelos são computacionalmente equivalentes. 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 . Iriyama, , 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. Uma máquina de Turing quântica com foi definida por , que mostrou que a classe de tempo polinomial em tal máquina (PostBQP) é igual à classe de complexidade clássica .