Computação quântica unidirecional temporariamente plana

18

Eu sou um físico de coração e, portanto, acho que a computação quântica unidirecional é brilhante. Em particular, a computação quântica baseada em medição de estado de gráfico (MBQC) tem sido um desenvolvimento muito bom na pesquisa sobre computação quântica, originada por Raussendorf & Briegel . É necessário apenas preparar um estado emaranhado multipartidário, conforme descrito em um gráfico, e realizar medições seqüenciais em cada nó ou qubit (medições adaptativas para cálculos determinísticos).

Outro aspecto excelente dessa abordagem é que os circuitos de Clifford podem ser implementados em uma única rodada de medições, como mostrado por Raussendorf, Browne e Briegel . Esses circuitos podem ser simulados classicamente (eficientemente), como mostrado por Gottesman e Knill, por isso é uma conexão interessante entre a simulação clássica e os recursos temporais.

No entanto, acredita-se que nem todos os circuitos MBQC de estado gráfico temporalmente planos (consistindo em uma rodada de medições) sejam simuláveis ​​classicamente. Por exemplo, famílias de circuitos no modelo de circuito quântico que consiste em portões pendulares chamados circuitos IQP, conforme introduzidos por Shepherd e Bremner, podem ser implementados em uma única etapa no MBQC. Acredita-se que esses circuitos IQP não sejam classicamente simuláveis (em termos de complexidade computacional, isso levaria a um colapso da hierarquia polinomial) .

Veja também uma boa descrição de uma classe de circuitos implementados em uma etapa aqui . Dado que os unitários pendulares / diagonais podem ter algum comportamento interessante, mas os circuitos não pendulares são classicamente simuláveis. Seria interessante se houvesse circuitos não pendulares que possam ser implementados, mas ainda não demonstrados como classificáveis.

Enfim, minha pergunta é:

Existem outros circuitos interessantes que podem ser implementados em uma única etapa no MBQC?

Embora eu preferisse relações à complexidade computacional ou simulação clássica, encontraria algo interessante.

Edit: Após a excelente resposta de Joe abaixo, devo esclarecer algumas coisas. Como Joe disse (e um tanto embaraçosamente eu disse em um de meus artigos), os circuitos MBQC de uma única rodada de medição estão no IQP. Para ser mais preciso, estou interessado em circuitos interessantes nos problemas no IQP que podem ser implementados em uma rodada de medições no MBQC. Os circuitos de Clifford são um exemplo interessante. Se houver outros exemplos que sejam classicamente simuláveis, isso seria extremamente interessante. Como a simulação de circuitos IQP é improvável classicamente, seria interessante encontrar exemplos de circuitos que são.

Matty Hoban
fonte

Respostas:

5

Dada a atualização sobre a questão, achei melhor postar isso como uma nova resposta, pois é totalmente diferente da minha resposta anterior e espero que seja interessante.

Parece que, com a nova redação da pergunta, há uma suposição oculta de que o estado do recurso MBQC possui um número de polinômios de qubits no número de qubits lógicos. Isso não precisa necessariamente ser o caso, o que leva a uma situação potencialmente interessante. É possível construir cálculos baseados em medição de camada única para os quais o estado do recurso é necessariamente exponencial no número de qubits lógicos, n .

Para ver isso, observe que qualquer qubit em um estado gráfico medido no plano X - Z tem o mesmo efeito que a aplicação do operador exp ( i θ i Z i ) em que i varia sobre todos os qubits vizinhos de j . Para ver isso, observe que o operador de emaranhamento aplicado a j é | 0 0 | I + | 1 1 | ¸ i Z ijXZexp(EuθEuZEu)Eujj|0 00 0|Eu+|11|EuZEu. Como o qubit é inicialmente preparado no estado O resultado líquido é que o seguinte operador é aplicado sobre os qubits vizinhos: 1|+. Se o qubit for rotacionado porexp(iθX),o resultado será112(|0 0Eu+|1EuZEu)exp(EuθX)Assim se a uma correcção Pauli de.ΠiZiimplementamos deterministicamente o operadorcosθI+isenZ12(|0 0(porqueθEu+EupecadoEuZEu)+|1(EuZEu)(porqueθEu+EupecadoEuZEu)EuZEu que é apenas uma forma alternativa de exp ( i θ i Z i )porqueθEu+EupecadoEuZEuexp(EuθEuZEu) .

Observe que esses operadores são a transformação Hadamard dos componentes básicos dos programas X e que todos esses operadores comutam independentemente de quais qubits eles operam. IQP é definido em termos de programas X que são restritos a ter vários termos no máximo polinômio no número de qubits. No entanto, existe um número exponencial de termos independentes e, portanto, é possível especificar cálculos temporalmente planos que possuem programas X de tamanho exponencial. Na verdade, o -input Toffoli portão de fase (isto é, o C . . . . CnC....CZgate) é um exemplo de uma operação que requer um número exponencial de portões pendulares, embora possa ser alcançada com um número linear de portões não pendulares. Assim, é possível construir cálculos baseados em medição de camada única que implementam programas X que são exponenciais no número de qubits lógicos e, portanto, fora do IQP para os qubits lógicos (embora dentro do IQP para os qubits físicos).

Potencialmente, há um problema aqui, pois eles exigem um número exponencial de parâmetros para especificar exclusivamente todos os pares no programa X. No entanto, se você considerar que tais ângulos são gerados algoritmicamente (digamos, com a restrição de que cada ângulo pode ser calculado em tempo polinomial), ainda não está claro se a simulação de tal cálculo pode ser feita no BQP.

Joe Fitzsimons
fonte
9

Não faz sentido perguntar sobre a implementação de operadores não pendulares em uma única etapa (embora profundidade constante certamente faça sentido). No entanto, é possível implementar portas não comutáveis ​​no subespaço lógico de um MBQC que são implementadas usando medições de comutação no estado do recurso, embora as portas implementadas não sejam determinísticas.

Na verdade, acredito que você está visualizando o IQP de maneira mais restrita do que provavelmente deveria. A resposta para sua pergunta é que qualquer MBQC que possa ser implementado em uma única camada de medição no MBQC está contido no IQP. Isso ocorre simplesmente porque, em vez de expressar o resultado em termos do espaço lógico de Hilbert, você pode expressá-lo como uma série de operações pendulares nos qubits físicos. Shepherd e Bremner realmente lidam com isso em seu artigo (na seção 5.2, onde essas operações são chamadas de programas gráficos).

Joe Fitzsimons
fonte
Obrigado Joe. Eu estava pensando nesses programas gráficos exatamente quando falamos sobre o IQP e onde eles mostraram que todo programa X pode ser implementado por um programa gráfico. No entanto, constrói-se um programa gráfico de maneira prescritiva para executar um programa X. Talvez minha redação na pergunta seja um pouco desdenhosa. Acho que meu problema com os portões não pendulares é procurar um exemplo como um circuito de Clifford, que pode ser implementado em uma única etapa.
Matty Hoban
@ Matty: Meu argumento é que os portões do grupo Clifford estão pendulares no sistema físico, mas não na imagem lógica de Heisenberg que normalmente usamos para examinar a computação em um MBQC. Por estarem pendulares no sistema físico, caem no IQP. É simplesmente a interpretação lógica dos qubits que é colocada em cima disso que muda as coisas. Fundamentalmente, qualquer cálculo de MBQC de camada única está no IQP exatamente por esse motivo.
Joe Fitzsimons
Ah, claro. Entendi o que você quer dizer agora. Desculpe por ser um pouco lento. Obviamente, também existem circuitos no IQP que não podem ser implementados em uma etapa no MBQC. Obrigado por este ponto, Joe. Minha motivação inicial foi basicamente encontrar exemplos de circuitos no IQP que possam ser interessantes - basicamente para alguns parágrafos da minha tese.
Matty Hoban
1
Editei a pergunta para ser um pouco menos vaga. Mais uma vez obrigado pela sua resposta. A propósito, eu amo muito o TP.SE, então obrigado por isso também :).
Matty Hoban