A simulação Hamiltoniana é BQP-complete

14

Muitos trabalhos afirmam que a simulação Hamiltoniana é BQP-completa (por exemplo, simulação Hamiltoniana com dependência quase ótima de todos os parâmetros e Simulação Hamiltoniana por Qubitização ).

É fácil ver que a simulação hamiltoniana é difícil para o BQP, porque qualquer algoritmo quântico pode ser reduzido para a simulação hamiltoniana, mas como é a simulação hamiltoniana no BQP?

ou seja, qual é exatamente o problema de decisão da simulação hamiltoniana no BQP e sob quais condições o hamiltoniano?

groupsgroupsgroups
fonte

Respostas:

14

Existem muitas variantes diferentes, particularmente no que diz respeito às condições no Hamiltoniano. É um pouco complicado, por exemplo, tentar encontrar a classe mais simples possível de hamiltonianos, para a qual a simulação ainda está completa no BQP.

|ψHO^t ip | e i H t O e - i H t | ip 1O^1tψ|eiHtO^eiHt|ψ112+aaa=112aaa=16


Detalhes adicionais

Simulação Hamiltoniana é difícil para BQP

A construção básica (originalmente devido a Feynman, aqui foi aprimorada um pouco) basicamente mostra como você pode projetar um Hamiltoniano que implementa qualquer computação quântica, incluindo qualquer computação BQP-completa. O observável que você mediria é apenas em um qubit de saída específico, os dois resultados de medição correspondentes a 'yes' e 'no'.Z

O tipo mais simples de Hamiltoniano em que você pode pensar é considerar um cálculo de seqüenciais agindo em qubits, começando em um estado . Em seguida, você pode introduzir um qubits extra e especificar o Hamiltoniano Se você preparar seu estado inicial como , depois de um tempo , ele estará em um estado queU n M | 0 H N H = 2N1UnM|0MN| 1| 0( N - 1 ) | 0H Nπ/4| 0

H=2Nn=1N-1n(N-n)(|1001|n,n+1você+|0110|n,n+1você).
|1|0 0(N-1)|0 0MNπ/4 | & Phi;|0 0(N-1)|1|Φ|Φé a saída do cálculo desejado. Os pontos fortes do acoplamento que usei aqui, os são escolhidos especificamente para fornecer evolução determinística e estão relacionados ao conceito de transferência de estado perfeita . Normalmente, você verá resultados declarados com acoplamentos iguais, mas com evolução probabilística.n(N-n)

Para ver como isso funciona, defina um conjunto de estados A ação do Hamiltoniano é então que prova que a evolução é restrita a um subespaço representado por uma matriz tridiagonal (que é a coisa específica estudada na transferência de estado perfeita).

|ψn=|0(n1)|1|0Nn(Un1Un2U1|0M).
H|ψn=2N(n1)(N+1n)|ψn1+2Nn(Nn)|ψn+1,
N×N

Obviamente, esse hamiltoniano não possui propriedades particularmente agradáveis ​​- é altamente não local, por exemplo. Existem muitos truques que podem ser usados ​​para simplificar o hamiltoniano de ser, por exemplo, unidimensional. Pode até ser invariante da tradução, se você quiser, ao custo de ter que preparar um estado inicial do produto mais complexo (nesse ponto, o cálculo não é mais codificado no Hamiltoniano, que é universal, mas é codificado no estado de entrada) . Veja aqui , por exemplo.

Simulação Hamiltoniana

A evolução de qualquer Hamiltoniano local em alguma rede, atuando em um estado inicial do produto, por um tempo que não seja mais que polinomial no tamanho do sistema, pode ser simulada por um computador quântico, e qualquer medição implementável com eficiência pode ser aplicada a estimar um observável. Nesse sentido, você pode ver que a simulação hamiltoniana não é mais difícil que a computação quântica, o contraponto à afirmação anterior de que a computação quântica não é mais difícil que a simulação hamiltoniana.

Existem várias maneiras de fazer isso (e houve alguns trabalhos recentes que mostram melhorias significativas na escala de erros para determinadas classes de Hamiltoniana). Hre é bem simples. Pegue o Hamiltoniano que você deseja simular. Divida-o em partes diferentes, , cada uma delas pendulares. Por exemplo, em um hamiltoniano do vizinho mais próximo em algum gráfico, você não precisa de mais peças do que o grau máximo do gráfico. Você então trotteriza a evolução, escrevendo a aproximação Então, você apenas precisa construir um circuito que implemente termos como , que é composto pelos termos de deslocamentoHHi

eiHt(eiH1δteiH2δteiHnδt)t/δt
eiH1δtH1=nhn, cada um dos quais atua apenas em um pequeno número de qubits. Como isso é apenas uma unidade em um pequeno número de termos, um computador quântico universal pode implementá-lo.
eiH1δt=neihnδt
DaftWullie
fonte