PARITY está em QAC_0 (se isso faz sentido)

17

Como é sabido, o PARITY não pode ser feito em circuitos de profundidade constante de tamanho poli e, de fato, os circuitos const-dept requerem número de portas EXP.

E os circuitos QUANTUM?

a) O PARITY pode ser feito com um circuito quântico que tenha profundidade constante e número poli de portas?

b) Minha pergunta faz sentido?

Bill GASARCH
fonte
2
Isso parece relevante: eccc.uni-trier.de/eccc-reports/1999/TR99-032
Ross Snider

Respostas:

20

A pergunta faz sentido, e a resposta curta é que é um problema em aberto.

Aqui está a resposta longa: Dependendo de como você define os circuitos quânticos de profundidade constante com ventilador ilimitado, você pode obter classes diferentes. O QAC 0 é geralmente definido como tendo portas de Toffoli de ventilador ilimitadas e portas de um qubit único. QAC 0 wf é a classe em que também permitimos um portão de "fanout", que copia um bit de entrada para muitas saídas. (Implementa | a> | 0> ... | 0> -> | a> | a> ... | a>) Essa classe é realmente poderosa, pois contém, além de PARITY e AC 0 , também ACC 0 e TC 0 .

Portanto, a pergunta óbvia a ser feita é se PARITY está contido no QAC 0 , e esse é um problema em aberto. É equivalente a perguntar se QAC 0 = QAC 0 wf . Eu acho que a crença é que PARITY não está no QAC 0 . Mais informações podem ser encontradas na pesquisa Circuitos quânticos de profundidade pequena de Bera, Green e Homer.

Robin Kothari
fonte
TC0 0QUMACC0 0
@SamuelSchlesinger: Este artigo mostra que você pode calcular limiar, a paridade, a maioria, etc. apenas com portões fanout e portões 2-qubit: theoryofcomputing.org/articles/v001a005
Robin Kothari
9

Surpreendentemente, o número de qubits extras de trabalho (ancilla) é importante. No momento, sabe-se que PARITY não está no QAC_0 com ancilares limitadas. Limites inferiores quânticos para fanout fornecem uma prova para circuitos que usam no máximo linearmente ancilla e doi: 10.1016 / j.ipl.2011.05.002 fornece outra prova para circuitos que não usam ancillae.

dBera
fonte