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

11

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?

Mok-Kong Shen
fonte
2
Você parece ter uma conta registrada em outros sites do Stack Exchange. Você deve registrar sua conta CS e associá-la às outras (consulte a Central de Ajuda ). Entre outras coisas, isso permitirá que você participe do bate-papo do CS.
Gilles 'SO- stop being evil' em

Respostas:

10

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 .

Niel de Beaudrap
fonte
Embora o conhecimento de meu iniciante me diga que um circuito quântico representa uma transformação de matriz Hadamard, ainda não consigo ver como uma possibilidade de programação para fazer cálculos arbitrários de matriz em um computador clássico poderia ser um substituto de ter fisicamente um circuito quântico. Por exemplo, meu livro diz sobre a geração de números aleatórios da seguinte maneira: 1. | x> <- | 0> 2. | x> <- H | x> 3. Meça | x> O que em particular a etapa 3 corresponderia programação em um computador clássico?
Mok-Kong Shen
Uma matriz Hadamard (devidamente normalizada) é apenas uma transformação unitária possível. Para seu cálculo, podemos reconhecer que uma máquina de Turing determinística pode calcular a distribuição de probabilidade (0,5, 0,5) que consiste nas normas ao quadrado da primeira coluna da matriz Hadamard , e que para uma máquina de Turing aleatória (que pode executar trocas de moedas), podemos dar um passo adiante e produzir uma amostra dessa distribuição de probabilidade. Em qualquer caso, qualquer função calculada pelo circuito quântico com erro <1/2, uma máquina clássica também pode. |b|H|0|2
Niel de Beaudrap 25/10/12
@ Mok-Kong Shen: caso não fique claro pelas minhas observações sobre ineficiência ou lentidão, geralmente se supõe que os computadores quânticos são mais computacionalmente poderosos no sentido de serem capazes de calcular mais rapidamente . Venho abordando o fato de que eles não são capazes de calcular coisas que um computador clássico também não pode calcular (onde desconsidero a noção de "jogar uma moeda" como computação).
Niel de Beaudrap 25/10/12
10

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|ϕvGv

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.]{G1,G2,...}C=GnG2G1v

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.]|ϕCvGnG2G1v

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 .xy=f(x)yyxf

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

ABfAfBf

yy1p1y2p20

f(x)yipi>0.751ff(x)2ff(x)(y1,p1),(y2,p2),...

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
1p=0.751/2
2f

Tocou.
fonte
Eu poderia programar cálculos matriciais em um computador clássico, mas não sei como escrever um código para simular um cálculo quântico. Vou precisar de bits quânticos. Um bit quântico possui 2 valores comumente denotados por alfa e beta. Quais valores devo usar? Veja também meu comentário à resposta de Niel de Beaudrap para o caso de geração aleatória de números.
Mok-Kong Shen
@ Mok-Kong Shen: esses valores parecem coeficientes em uma superposição . Mas lembre-se de que a notação Dirac é meramente uma notação vetorial: é exatamente o mesmo que escrever usando a convenção usual. Esses coeficientes são apenas coeficientes vetor / matriz, que é o que o computador clássico avalia para simular (lentamente) o computador quântico. |ψ=α|0+β|1ψψ=[αβ]
Niel de Beaudrap 25/10/12
@Niel de Beaudrap: Mas quando eu escrevo um código para simular uma certa compilação quântica, por exemplo, a geração de números aleatórios que mencionei, preciso implementar bits quânticos simulados no computador clássico. Eu sou ignorante sobre como escrever código para fazer isso sem conhecer os valores desses coeficientes.
Mok-Kong Shen
@ Mok-Kong Shen: o ponto é que, em tempo de execução, você sabe; e o problema é exatamente o mesmo que a amostragem de uma distribuição de probabilidade clássica especificada na entrada, ou seja , reduz-se a problemas bem estudados na amostragem aleatória. Os métodos de Monte Carlo se aplicam aqui, por exemplo.
Niel de Beaudrap 25/10/12
1
@ Mok-KongShen Por favor, não use comentários (especialmente no post de outra pessoa) para discussões prolongadas. Vá para o bate - papo , na sala geral deste site ou em uma sala de chat criada para esse fim.
Gilles 'SO- stop being evil' em
1

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.=?

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 .

vzn
fonte
note, o aram harrow é um dos principais céticos em relação aos problemas de ruído de escrita da QM. outro bom ponto de partida, blog RJ Lipton, movimento perpétuo do século 21?
vzn