Qual é a prova de que computadores quânticos podem simular eficientemente sistemas mecânicos quânticos arbitrários?

A JBV sugeriu que eu transformasse alguns comentários em uma pergunta, então aqui vai.

Outra pergunta [1] pergunta sobre aplicações da computação QM. Uma resposta [2] foi "simulando eficientemente a mecânica quântica". Aparentemente, essa idéia remonta aos primeiros escritos de Feynman sobre o assunto; embora eu não tenha uma referência. Então:

Questão. Qual é a prova de que um computador quântico pode simular com eficiência um sistema mecânico quântico arbitrário?

Em um nível, isso parece básico. No entanto, isso não parece trivial pela seguinte razão: a maior parte da literatura sobre computação quântica parece se reduzir a operações em portões que agem sobre duas partículas ou outros pequenos subsistemas. (Sim, os portões de Toffoli atuam em 3 entradas, mas de qualquer maneira são frequentemente reduzidos a portões CNOT de dois qubit.)

Certamente não há dúvida, devido à completude de Turing, de que um computador quântico possa simular uma física clássica ou mesmo quântica arbitrária (embora talvez haja alguns opositores por causa do princípio da incerteza etc. - eu também ficaria curioso em saber disso). Mas parece-me que, para simular a física quântica arbitrária de forma eficiente, é necessário pelo menos uma maneira de simular interações arbitrárias de mão única em quase / quase duas vias .

Poder-se-ia argumentar que podemos construir portões de mão -de- obra arbitrárias , mas a evidência clara após muitos anos de pesquisa experimental é que mesmo apenas as portas de mão dupla são extremamente difíceis de construir, e que as portas de mão certamente seriam muito mais difíceis. (Existem algumas experiências quânticas de três vias , por exemplo , desigualdades de sino de três partículas, mas são difíceis de construir.)

[1] Aplicações do mundo real da computação quântica (exceto segurança)

[2] https://cstheory.stackexchange.com/a/10241/248.

reference-request quantum-computing application-of-theory vzn
fonte

pensamentos adicionais, a idéia geral de equivalência computacional QM com simulação física QM aparentemente se originou em Feynman, que parecia considerá-lo um dado ou suposição [que era mais um físico brilhante do que um cientista da computação] ... por exemplo, no artigo e na palestra ,

Simulando

Respostas:

$n$

$n$ $n$ $n$ $n$

$2^n$ $n$ $n$ $O(n)$

$n$ $n$ $k$ $k$

$n$

Se computadores quânticos podem simular com eficiência a teoria quântica de campos ainda é uma questão em aberto, mas atualmente está sendo feito progresso nela.

Peter Shor
fonte

não é que um erro de digitação na 1ª linha "deveria" => "não deveria". e note que estou focando na questão mais rígida da eficiência, não na mera equivalência. aceite que os computadores QM estão completos com Turing. como você diz que tudo isso é bastante direto, que tal o simples caso de simular um sistema quântico de partículas n em que nenhuma partícula é isolada uma da outra? como isso é feito com qubits?

vzn

n

$n$

vai acreditar na sua palavra, mas meu principal pt-- isso é discutido em algum lugar da literatura? parece que todas essas advertências poderiam facilmente encher um papel pelo menos. você parece estar afirmando que provavelmente todos os hamiltonianos físicos são eficientemente simuláveis por meio de qubits, mas isso precisa ser desenvolvido de alguma forma matematicamente. Acho que não é trivial o suficiente para que as autoridades não declarem com clareza que a simulação QM eficiente de todas as configurações arbitrárias de QM é intrinsecamente viável. talvez influências ambientais, por exemplo, configurações de campo elétrico ou magnético aplicadas possam complicar o hamiltoniano.

vzn

Acredito que já o vi discutido em algum lugar, mas não me lembro onde. Dizer quais hamiltonianos podem ser implementados fisicamente é uma pergunta complicada ... já que toda a dinâmica da natureza se origina na teoria quântica de campos, mostrar que a QFT pode ser simulada com eficiência com um computador quântico pode responder a essa pergunta, mas (1) ainda estamos muito tempo para provar isso e (2) isso pode ser algo como dizer que podemos simular turbulência usando a dinâmica atômica subjacente. Em certo sentido, pode ser verdade, mas é claramente a maneira errada de fazê-lo.

Peter Shor