Decidibilidade / algoritmo para verificar a universalidade de um conjunto de portas quânticas

11

Dado um conjunto finito de portas quânticas , é decidível (no sentido teórico da computação) se G é um conjunto de portas universais? Por um lado, "quase todos" os conjuntos de portas são universais; por outro, os conjuntos de portas não universais ainda não são bem compreendidos (em particular, é claro, não se sabe se todos os conjuntos de portas não universais são classicamente simuláveis), então imagino que dar um algoritmo explícito para verificar a universalidade possa não ser trivial.G={G1,,Gn}G

Marcin Kotowski
fonte
3
Você pode esclarecer a pergunta? A resposta de Joe pressupõe que você tenha um número fixo de qubits e todos os portões agem sobre eles, mas, para a universalidade, geralmente assumimos que os portões podem agir em qualquer subconjunto de qubits. Por exemplo, CNOT + todos os portões de um qubit não são universais se os portões de um qubit só podem atuar no primeiro qubit, e o CNOT é apenas do qubit 1 ao qubit 2. No último caso, podemos querer extrapolar para muitos qubits para obter universalidade. Nesse caso, acho que a resposta pode ser desconhecida.
@DanielGottesman: Eu concordo com as limitações da minha resposta. Na verdade, eu acredito que é indecidível no último caso da seguinte forma: Dê um autômato celular em uma rede infinita de qubits e usá-lo para codificar o problema da parada (chamar essa atualização unitária ). Em seguida, tomar uma segunda rede com um QCA universal (com atualização unitária U 2 ). Podemos definir uma nova unidade C U 2 = | 0 0 | HI + | 1 1 | L 2 , onde o subscrito HU1U2CU2=|00|HI+|11|U2Hdenota um qubit definido como sse os primeiros paradas autómatos celulares. |1
Joe Fitzsimons
Assim, o portão é universal, se e somente se as primeiras máquina pára Turing, e é, portanto, indecidible. CU2×U1
Joe Fitzsimons

Respostas:

6

Para o caso dos hamiltonianos, em vez de portões, a resposta é trivialmente sim: você simplesmente enumera os elementos independentes da álgebra de Lie. Como a álgebra de Lie é um espaço vetorial com a adição do operador de colchete de Lie. Como o espaço é finito, possui uma base finita e pode ser facilmente verificado se está fechado ou aberto sob a operação do suporte Lie. A simples verificação do colchete de Lie de todos os pares de operadores ortogonais pode ser feita em tempo polinomial na dimensionalidade do espaço, e uma base de operador adequada pode ser encontrada pelo método de Gram-Schmidt.

Para portões, você realmente não tem a mesma opção de recorrer a infinitesimais imediatamente, e precisa construir portões com autovalores irracionais para poder arbitrariamente aproximar arbitrariamente os geradores infinitesimais necessários. Eu acho que existe uma maneira relativamente simples de fazer isso, mas não é imediatamente óbvio para mim.

De qualquer forma, pegar o log dos portões para obter um conjunto de operadores que os geram quando exponenciados e verificar se eles geraram a álgebra de Lie completa forneceriam um critério simples necessário, mas não suficiente para a universalidade.

Joe Fitzsimons
fonte
Por que devemos verificar apenas pares?
Alex 'qubeat'
@AlexV: Como o suporte Lie utiliza operações em 2 entradas. Toda vez que você produz um novo operador linearmente independente, produz um ortogonal e repete até obter o fechamento.
Joe Fitzsimons
[[Hk,Hj],Hl],]
@ AlexV: Você não precisa. É um espaço vetorial, portanto, um vetor é ortogonal a um determinado subespaço se e somente se for ortogonal a qualquer base desse subespaço.
21812 Joe Fitzsimons
É provável que estejamos falando de coisas diferentes - sobre qual espaço vetorial você está falando? Você não conhece desde o início a subalgebra gerada por seus portões - é necessário construí-la a partir de hamiltonianos para verificar se é toda a álgebra de Lie.
Alex 'qubeat'