Quão poderosa é a computação “quântica” exata se você suspender a unitariedade?

Pergunta curta.

Qual é o poder computacional dos circuitos "quânticos", se permitirmos portas não unitárias (mas ainda invertíveis) e exigirmos que a saída dê a resposta correta com certeza?

Esta questão é de certa forma sobre o que acontece com a classe quando você permite que os circuitos usem mais do que apenas portas unitárias. (Ainda somos forçados a restringir-nos a portões invertíveis acima de se quisermos ter um modelo de computação bem definido.)$\mathsf{EQP}$$\mathbb C$

(Esta questão passou por algumas revisões à luz de alguma confusão da minha parte sobre os resultados conhecidos sobre esses circuitos no caso unitário.)

Sobre a computação quântica "exata"

Eu defino $\mathsf{EQP}$ para o bem desta pergunta como a classe de problemas que podem ser resolvidos exatamente por uma família de circuitos quânticos uniformes, em que os coeficientes de cada unitário são computáveis ​​por máquinas de Turing com limite de tempo polinomial (da cadeia de entrada $1^n$ ) para cada tamanho de entrada $n$ , e que o layout do circuito como uma rede direcionada também possa ser produzido em tempo polinomial. Por "exatamente" resolvido, quero dizer que medir o bit de saída produz $|0\rangle$ com certeza para instâncias não, e $|1\rangle$ com certeza para instâncias SIM.

Ressalvas:

• Mesmo restringindo a portas unitárias, essa noção de $\mathsf{EQP}$ é diferente da descrita por Bernstein e Vazirani usando máquinas quânticas de Turing. A definição acima permite uma família circuito $\{ C_n \}$ a, em princípio, tem um conjunto de porta infinito - cada circuito indivíduo $C_n$ utiliza apenas um subconjunto finito, é claro - porque as portas estão no efeito calculado a partir das entradas. (Uma máquina de Turing quântica pode simular qualquer conjunto de portas finitas que você gosta, mas pode simular apenas conjuntos de portas finitas, porque possui apenas um número finito de transições.)

• Esse modelo de computação banaliza qualquer problema em $\mathsf P$ , porque o unitário pode conter uma única porta que codifica a solução para qualquer problema em $\mathsf P$ (seus coeficientes são afinal determinados por um cálculo em tempo poligonal). Portanto, a complexidade específica de tempo ou espaço dos problemas não é necessariamente interessante para esses circuitos.

Podemos acrescentar a essas ressalvas a observação de que implementações práticas de computadores quânticos terão ruído de qualquer maneira. Este modelo de computação é interessante principalmente por razões teóricas , como se preocupa com a compor transformações unitárias ao invés de computação viável, e também como uma versão exata do . Em particular, apesar das ressalvas acima, temos P ⊆ E Q P ⊆ B Q P .$\mathsf{BQP}$$\mathsf{P} \subseteq \mathsf{EQP} \subseteq \mathsf{BQP}$

A razão para a definição da maneira que fazer é por isso que DISCRETA-LOG pode ser colocado em E Q P . Em [  Mosca + Zalka 2003  ], existe um algoritmo de tempo polinomial para construir um circuito unitário que resolve exatamente instâncias do DISCRETE-LOG produzindo versões exatas do QFT, dependendo do módulo de entrada. Acredito que podemos então colocar DISCRETE-LOG em E Q P , como definido acima, incorporando os elementos de construção de circuitos na maneira como os coeficientes de gate são calculados. (Portanto, o resultado DISCRETE-LOG ∈ E Q P é essencialmente válido, mas depende da construção de Mosca + Zalka.)$\mathsf{EQP}$$\mathsf{EQP}$$\mathsf{EQP}$$\in \mathsf{EQP}$

Suspender a unitariedade

Seja a classe computacional que obtemos se suspendermos a restrição de que as portas são unitárias e permitir que elas abranjam transformações invertíveis. Podemos colocar essa classe (ou até caracterizá-la) em termos de outras classes tradicionais não determinísticas C ?$\mathsf{EQP_{\mathrm{GL}}}$$\mathbf C$

Uma das minhas razões para perguntar: se é a classe de problemas solucionáveis ​​eficientemente com erro limitado , por famílias uniformes de circuitos "quantum não unitário" - onde as instâncias YES fornecem uma saída de | 1 ⟩ com probabilidade de, pelo menos, 2/3, e nenhum exemplo com probabilidade de, no máximo, 1/3 (após normalização do estado-vector) -, em seguida, [Aaronson 2005] mostra que B Q P L L = P P . Ou seja: suspender a unitariedade é, neste caso, equivalente a permitir erros ilimitados.$\mathsf{BQP}_{\mathrm{GL}}$$|1\rangle$$\mathsf{BQP}_{\mathrm{GL}} = \mathsf{PP}$

Um resultado semelhante, ou algum resultado claro, é obtido para ?$\mathsf{EQP_{\mathrm{GL}}}$

Resposta curta. Acontece que a suspensão do requisito de transformações unitárias e a exigência de que cada operação seja invertível dão origem a classes exatas definidas por intervalos. As classes específicas em questão são e uma 'nova' subclasse L P W P P , ambas situadas entre S P P e$\mathsf{LWPP}$$\mathsf{LPWPP}$$\mathsf{SPP}$ . Essas classes têm definições bastante técnicas, que são brevemente descritas abaixo; embora essas definições agora possam ser substituídas, em princípio, por outras em termos de algoritmos não-unitários "do tipo quântico".$\mathsf{C_=P}$

A classe de contagem contém ISOMORFISMO GRÁFICO. Ele também contém toda a classe U P , portanto, não esperamos que algoritmos quânticos unitários exatos sejam tão poderosos quanto as classes não unitárias (como poderíamos mostrar N P ⊆ B Q P ).$\mathsf{SPP}$$\mathsf{UP}$$\mathsf{NP \subseteq BQP}$

Resposta mais longa.

• Na minha pergunta, propus redefinir para permitir problemas solucionáveis ​​por famílias de circuitos uniformes que usam portas que são eficientemente computáveis, mas não necessariamente extraídas de um conjunto finito de portas. Não tenho mais tanta certeza de que é uma boa idéia redefinir E Q P dessa maneira, embora eu acredite que essas famílias de circuito valham a pena estudar. Podemos chamar esta classe algo como L n i t um r y P C em seu lugar.$\mathsf{EQP}$ $\mathsf{EQP}$$\mathsf{UnitaryP_{\mathbb C}}$

  É possível demonstrar que , que até recentemente era o melhor conhecido ligado por E Q P . A classe L W P P mais ou menos corresponde a problemas para os quais existe um algoritmo aleatório, onde instâncias de NO produzem um resultado de 1 com probabilidade exatamente de 0,5 e instâncias de YES produzem um resultado de 1 com alguma probabilidade que pode ser eficiente e exatamente calculado de forma racional, que é maior que (mas possivelmente exponencialmente próximo a) 0,5. A definição técnica de L W $\mathsf{UnitaryP_{\mathbb C} \subseteq LWPP}$$\mathsf{EQP}$$\mathsf{LWPP}$ é apresentado em termos de máquinas de Turing não determinísticas, mas não é mais esclarecedor.$\mathsf{LWPP}$

  Se definirmos como o equivalente de porta invertível de U n i t a r y P C , de modo que o conjunto de problemas seja exatamente solucionável por famílias de circuitos invertíveis com coeficientes de porta eficientemente computáveis, então G L P C = G W P P .$\mathsf{GLP}_{\mathbb C}$$\mathsf{UnitaryP_{\mathbb C}}$$\mathsf{GLP_{\mathbb C} = LWPP}$

• Se restringirmos a gate-conjuntos finitos, é possível mostrar que as famílias de circuito unitárias podem ser simulados em um subconjunto de , que podemos chamar G P W P P . (Usando a descrição de L W P P acima, isso corresponde a algoritmos aleatórios em que a probabilidade de obter uma saída de 1 para instâncias YES é exatamente m t ( x ) / 2 p ( | x | ) , para alguns polinômios p , alguns inteiro $\mathsf{LWPP}$$\mathsf{LPWPP}$$\mathsf{LWPP}$$m^{t(x)} / 2^{p(|x|)}$$p$$m$e algum polinômio eficientemente computável .)$t$

  Se nós definimos ser o equivalente invertível-porta de E Q P , uma vez que é normalmente definida, podemos mostrar que E Q P G G ⊆ G P W P P .$\mathsf{EQP_{\mathrm{GL}}}$$\mathsf{EQP}$$\mathsf{EQP_{\mathrm{GL}} \subseteq LPWPP}$

Uma correção em relação ao LOG DISCRETO.

Os resultados acima se baseiam em técnicas padrão para representar coeficientes algébricos, de maneira independente da entrada (mas que pode depender do tamanho da entrada). Na descrição da pergunta original, afirmei que [ Mosca + Zalka 2003 ] mostra que DISCRETE LOG é exatamente solucionável por um conjunto de portas com coeficientes eficientemente computáveis. A verdade parece ser mais complicada. Se alguém se preocupa com a solvabilidade exata, considero importante a representação exata dos coeficientes: mas Mosca e Zalka não fornecem uma maneira de fazer isso de maneira dependente de entrada. Portanto, não é óbvio que DISCRETE LOG está de fato em ou na nova classe U n i t a r y $\mathsf{EQP}$ .$\mathsf{UnitaryP_{\mathbb C}}$

Referência.

• de Beaudrap, Contagem exata e complexidade quase-quântica , [ arXiv: 1509.07789 ].