¿Hay algún análogo cuántico del problema VP vs VNP?

8

De Wikipedia :

VP : La clase VP es el análogo algebraico de P; es la clase de polinomiosf de grado del polinomio que tienen circuitos de tamaño polinómicas sobre un campo fijoK .

VNP : La clase VNP es el análogo de NP. VNP puede considerarse como la clase de polinomiosf de grado polinomial de tal manera que, dado un monomio, podemos determinar su coeficiente enf eficiente, con un circuito de tamaño polinómico.

Ha habido intentos de implementar polinomios f usando circuitos cuánticos, cf. arXiv: 1805.12445 . Entonces, ¿existe algún análogo cuántico del problema VP vs. VNP ? ¿Hay algún documento sobre este tema?

PD: He hecho una pregunta muy relacionada en el sitio de Quantum Computing .

Dakota del Sur
fuente

Respuestas:

8

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

#PVNP

VP2nBQP

BPPMABQPQMAVP

Esto no quiere decir que todos estos enfoques no puedan funcionar, solo para compartir algunos pensamientos sobre ellos. ¡Espero que alguien pueda hacer que funcione!

Joshua Grochow
fuente