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?
cc.complexity-theory
quantum-computing
circuit-complexity
Bill GASARCH
fonte
fonte
Respostas:
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.
fonte
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.
fonte