Existe algum análogo quântico do problema VP vs. VNP?

8

Da Wikipedia :

VP : A classe VP é o análogo algébrico de P; é a classe de polinômios de grau polinomial que têm circuitos de tamanho polinomiais sobre um campo fixo .fK

VNP : A classe VNP é o análogo do NP. O VNP pode ser considerado como a classe de polinômiosf de grau polinomial tal que, dado um monômio, podemos determinar seu coeficiente em f eficiência, com um circuito de tamanho polinomial.

Houve tentativas de implementar polinômios f usando circuitos quânticos, cf. arXiv: 1805.12445 . Existe algum análogo quântico do problema VP vs. VNP ? Existe algum artigo sobre este tópico?

PS: Fiz uma pergunta muito relacionada no site da Quantum Computing .

SD
fonte

Respostas:

8

ffnnf=(fn)BQPQMAfG(x)xBQP#PVBQP#PVNPGfGfn(G)

#PVNP

VP2nBQP

BPPMABQPQMAVP

Isso não quer dizer que todas essas abordagens não funcionem, apenas para compartilhar algumas idéias sobre elas. Espero que alguém consiga fazê-lo funcionar!

Joshua Grochow
fonte