Referências sobre comparação entre computadores quânticos e máquinas de Turing

Disseram-me que os computadores quânticos não são computacionalmente mais poderosos que as máquinas de Turing. Alguém poderia gentilmente ajudar a fornecer algumas referências da literatura que explicassem esse fato?

O que realmente é o caso é que qualquer coisa que um computador quântico possa calcular, uma máquina de Turing também pode calcular. (Isso sem comentar nada sobre quanto tempo a máquina de Turing leva para calcular a função em comparação com um computador quântico.)

Na verdade, isso não é difícil de ver, desde que você entenda a computação quântica. Para um circuito quântico sobre um conjunto de portas típico, por exemplo, o resultado é governado por uma distribuição de probabilidade, que é determinada pelos coeficientes de uma matriz unitária. Essa matriz unitária é apenas um produto da matriz dos portões e pode ser calculada - se você for paciente o suficiente - por um computador clássico. Portanto, para pura computabilidade (em oposição à eficiência), não há vantagem em usar computadores quânticos.

Todo o desafio decorrente da mecânica quântica é determinar se tais coeficientes podem ser calculados de forma eficiente , o que é um problema mais exigente do que se eles podem ser computados em tudo .

Considere um portão quântico. Suavizando todos os detalhes técnicos, pode ser representado como uma matriz . Uma entrada para o portão, digamos é apenas um vetor , e a saída do portão é o vetor .$G$$\vert \phi \rangle$$v$$Gv$

Agora, considere um circuito. Um circuito é apenas um monte de portas , e o próprio circuito pode ser visto como um "portão generalizado" , que opera no estado de entrada (o vetor ) [Novamente, essa é uma abstração muito grosseira.]$\{G_1, G_2, ... \}$$C=G_n \cdots G_2 G_1$$v$

Então, basicamente, calcular um circuito em uma entrada , é apenas computar o vetor ou . Está claro que tal tarefa (multiplicação de matrizes e multiplicação de matrizes por vetor) pode ser realizada por uma MT clássica, portanto, a MT é pelo menos tão forte quanto uma quantum-TM (QTM) [ok, circuitos clássicos são tão fortes quanto a quantum circuitos. esqueça isso.]$\vert \phi \rangle$$Cv$$G_n \cdots G_2 G_1 v$

Por outro lado, o QTM é trivialmente tão forte quanto o TM e, portanto, ambos os modelos são equivalentes.

EDITAR devido a comentários
Para perguntar qual "computador" é mais poderoso, precisamos primeiro esclarecer o que significa ser mais "computacionalmente poderoso". E essa discussão semi-filosófica começa com a pergunta

O que é computação ?

Os arquivos "reproduzir MP3" são um cálculo? A saída de números aleatórios é um cálculo?

A definição padrão diz que um cálculo é "computar uma função". Ou seja, para cada entrada (que pode ser qualquer sequência de qualquer comprimento finito), saída , onde novamente pode ser uma sequência de comprimento arbitrário (finito). Se o seu computador puder gerar para qualquer , dizemos que ele pode calcular .$x$$y=f(x)$$y$$y$$x$$f$

Agora, dizer que o computador "A" é mais poderoso que "B" significa apenas que A calcula mais funções$f$$B$

$A$$B$$f$$A$$f$$B$$f$

$y$$y_1$$p_1$$y_2$$p_2$$^0$

$f(x)$$y_i$$p_i>0.75$$^1$$f$$f(x)$$^2$$f$$f(x)$$(y_1,p_1), (y_2,p_2),...$

Com o exposto, deve ficar claro que ter probabilidades não altera a potência do modelo, e uma TM clássica pode apenas gerar a lista de possíveis saídas, juntamente com a probabilidade de cada saída. é exatamente isso que acontece quando uma TM multiplica matrizes e gera um vetor - o vetor representa a probabilidade de cada saída de medição possível.

^{$^0$
$^1$$p=0.75$$1/2$
$^2$$f$}

outras respostas são válidas, apenas quero acrescentar uma que enfatize que essa é realmente uma questão muito profunda (em grande parte ainda aberta / não resolvida) no centro de muitas pesquisas modernas sobre separações de classes de complexidade e computação quântica versus clássica. eles são funcionalmente equivalentes na medida em que os computadores TMs e QM são comprovadamente completos como Turing ; existem várias maneiras de provar isso.

mas a equivalência na teoria da complexidade depende muito das sutilezas / eficiências do tempo e do espaço, ou seja, recursos para calcular algoritmos específicos. e há também uma enorme quantidade de pesquisas analisando "ruído" na computação de QM, que considera que modelos teóricos e silenciosos podem não ser "reais" ou realizáveis ​​na prática, e modelos reais podem / terão ruído significativo. existem esquemas complexos para mitigar esse ruído, etc .; há excelentes comentários sobre isso em várias postagens no blog RJ Liptons, por exemplo, máquinas voadoras do século XXI

por exemplo, foi provado que o fatoração está no BQP, a classe de algoritmos quânticos que são executados no tempo P, por Shor em uma famosa prova de que na época também lançou uma grande quantidade de estudos / pesquisas sérias na computação QM devido à dramática resultado.

no entanto, mesmo com modelos QM "silenciosos", é uma questão em aberto se P BQP, onde o primeiro denota uma classe de complexidade clássica de algoritmos eficientes Poly-time e BQP é a classe de algoritmos QM eficientes / Poly-time . e existem várias perguntas abertas semelhantes.$\stackrel{?}{=}$

Scott Aaronson é um excelente escritor / pesquisador sobre o assunto e escreveu alguns artigos acessíveis ao leigo. veja, por exemplo, os limites dos computadores QM, SciAm ou QM computing prometem novas idéias, NYT .