Máquina de Quantum Turing - Quantum Turing machine

Máquinas de Turing
Máquina
Equivalentes da máquina de Turing Exemplos de máquina de Turing Galeria da máquina de Turing
Variantes
Máquina de Turing Alternada Computador neural diferenciável Máquina de Turing não determinística Máquina de Quantum Turing Máquina Pós-Turing Máquina de Turing Probabilística Máquina de Turing somente leitura Máquinas de Turing móveis corretas somente leitura Máquina de Turing Multitape Máquina de Turing Multi-track Máquina de Turing Simétrica Máquina de Turing Total Máquina de Turing inequívoca Máquina universal de Turing Máquina Zeno
Ciência
Alan Turing Categoria: Máquina de Turing
v t e

Uma máquina de Turing quântica ( QTM ) ou computador quântico universal é uma máquina abstrata usada para modelar os efeitos de um computador quântico . Ele fornece um modelo simples que captura todo o poder da computação quântica - ou seja, qualquer algoritmo quântico pode ser expresso formalmente como uma máquina de Turing quântica específica. No entanto, o circuito quântico equivalente computacionalmente é um modelo mais comum.

As máquinas de Turing quânticas podem ser relacionadas às máquinas de Turing clássicas e probabilísticas em uma estrutura baseada em matrizes de transição . Ou seja, uma matriz pode ser especificada cujo produto com a matriz que representa uma máquina clássica ou probabilística fornece a matriz de probabilidade quântica que representa a máquina quântica. Isso foi mostrado por Lance Fortnow .

Desenho informal

Problema não resolvido na física : Um computador quântico universal é suficiente para simular com eficiência um sistema físico arbitrário? (mais problemas não resolvidos em física)

Uma forma de entender a máquina de Turing quântica (QTM) é que ela generaliza a máquina de Turing clássica (TM) da mesma forma que o autômato finito quântico (QFA) generaliza o autômato finito determinístico (DFA). Em essência, os estados internos de uma TM clássica são substituídos por estados puros ou mistos em um espaço de Hilbert; a função de transição é substituída por uma coleção de matrizes unitárias que mapeiam o espaço de Hilbert para si mesmo.

Ou seja, uma máquina de Turing clássica é descrita por uma 7- tupla . ${\ displaystyle M = \ langle Q, \ Gamma, b, \ Sigma, \ delta, q_ {0}, F \ rangle}$

Para uma máquina de Turing quântica de três fitas (uma fita segurando a entrada, uma segunda fita segurando os resultados de cálculo intermediários e uma terceira fita segurando a saída):

• O conjunto de estados é substituído por um espaço de Hilbert . ${\ displaystyle Q}$
• Os símbolos do alfabeto da fita são igualmente substituídos por um espaço de Hilbert (geralmente um espaço de Hilbert diferente do conjunto de estados). ${\ displaystyle \ Gamma}$
• O símbolo em branco corresponde ao vetor zero. ${\ displaystyle b \ in \ Gamma}$
• Os símbolos de entrada e saída são geralmente considerados como um conjunto discreto, como no sistema clássico; portanto, nem a entrada nem a saída de uma máquina quântica precisam ser um sistema quântico em si. ${\ displaystyle \ Sigma}$
• A função de transição é uma generalização de um monóide de transição e é entendida como uma coleção de matrizes unitárias que são automorfismos do espaço de Hilbert . ${\ displaystyle \ delta: \ Sigma \ times Q \ otimes \ Gamma \ rightarrow \ Sigma \ times Q \ otimes \ Gamma \ times \ {L, R \}}$${\ displaystyle Q}$
• O estado inicial pode ser um estado misto ou um estado puro . ${\ displaystyle q_ {0} \ in Q}$
• O conjunto de estados finais ou de aceitação é um subespaço do espaço de Hilbert . ${\ displaystyle F}$${\ displaystyle Q}$

O texto acima é apenas um esboço de uma máquina de Turing quântica, ao invés de sua definição formal, pois deixa vagos vários detalhes importantes: por exemplo, com que frequência uma medição é realizada; veja, por exemplo, a diferença entre um QFA de medida única e medida de muitos. Esta questão de medição afeta a maneira como as gravações na fita de saída são definidas.

História

Em 1980 e 1982, o físico Paul Benioff publicou artigos que descreveram pela primeira vez um modelo de mecânica quântica de máquinas de Turing . Um artigo de 1985 escrito pelo físico David Deutsch da Universidade de Oxford desenvolveu ainda mais a ideia de computadores quânticos, sugerindo que as portas quânticas poderiam funcionar de maneira semelhante às portas lógicas binárias da computação digital tradicional .

Iriyama, Ohya e Volovich desenvolveram um modelo de máquina de Turing quântica linear (LQTM). Esta é uma generalização de um QTM clássico que possui estados mistos e que permite funções de transição irreversíveis. Isso permite a representação de medições quânticas sem resultados clássicos.

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 .

Veja também

• Simulador quântico § Resolvendo problemas de física

Referências

Leitura adicional

• Molina, Abel; Watrous, John (2018). "Revisitando a simulação de máquinas de Turing quânticas por circuitos quânticos". arXiv : 1808.01701 [ cs.CC ].
• Iriyama, Satoshi; Ohya, Masanori; Volovich, Igor (2004). "Máquina de Turing Quantum Generalizada e sua Aplicação ao Algoritmo SAT Chaos". arXiv : quant-ph / 0405191 .
• Deutsch, D. (1985). "Teoria Quântica, o Princípio de Church-Turing e o Computador Quântico Universal". Proceedings of the Royal Society of London. Série A, Ciências Matemáticas e Físicas . 400 (1818): 97-117. Bibcode : 1985RSPSA.400 ... 97D . CiteSeerX   10.1.1.41.2382 . doi : 10.1098 / rspa.1985.0070 . JSTOR   2397601 .

links externos

• O computador quântico - história