From Wikipedia:

$\mathsf{VP}$: The class VP is the algebraic analog of P; it is the class of polynomials $f$ of polynomial degree that have polynomial size circuits over a fixed field $K$.

$\mathsf{VNP}$: The class VNP is the analog of NP. VNP can be thought of as the class of polynomials $f$ of polynomial degree such that given a monomial we can determine its coefficient in $f$ efficiently, with a polynomial-size circuit.

There have been attempts to implement polynomials $f$ using quantum circuits, cf. arXiv:1805.12445. So does there exist any quantum analog of the $\mathsf{VP}$ vs. $\mathsf{VNP}$ problem? Is there any paper on this topic?

P.S: I've asked a very related question on the Quantum Computing site.


1 Answer 1


This is not quite an answer, but some observations that are too long for a comment. I've thought about this question before, but not being an expert in quantum I was never really able to resolve it. The thing you want for this is a polynomial $f$ (really, a family of polynomials $f_n$, one for each $n$) such that $f = (f_n)$ is in some sense complete for $\mathsf{BQP}$ (resp., $\mathsf{QMA}$). While there are many problems on polynomials that show up in quantum classes, they are typically more of the form "Given some input graph G, compute (the coefficients of, or the evaluation of) some polynomial $f_G(x)$ at some point $x$". For example, a natural thing to think of here is the Jones polynomial. Given a link, approximating its Jones polynomial at a root of unity is $\mathsf{BQP}$-complete. Evaluating the Jones polynomial given a link in general is $\mathsf{\# P}$-hard (see references e.g. here). So there are two issues here in using this to define "$\mathsf{VBQP}$": the first is that the Jones polynomial in general is $\mathsf{\# P}$-hard, so if you tried to use it you might end up with $\mathsf{VNP}$ again. Second, it's not just a single family of polynomials, it's a question of the above form (given an input object $G$, compute $f_G$, rather than evaluate $f_n(G)$ which is what we'd want).

Another approach you might try is to consider the amplitudes of the output of a quantum circuit as a polynomial in their inputs. But these amplitudes can be permanents, so again we quickly seem to run into $\mathsf{\# P}$- or $\mathsf{VNP}$-completeness.

Yet another approach you might try is to somehow mimic the "universal circuit" constructions for $\mathsf{VP}$-complete problems (those by Burgisser and then Raz, see, e.g., Mahajan's survey or the references in Section 5 of Mahajan-Saurabh) with universal quantum circuits. Here we run into the issue that there seems to be somewhat of a mismatch between quantum circuits and algebraic circuits. In particular, a quantum circuit on n qubits maintains $2^n$ amplitudes, whereas an algebraic circuit maintains a single ring element on each wire, so a total number which is polynomial in the size of the circuit (linear if you measure size by number of wires or have bounded fan-in). Quantum circuits that maintain much less information than this - e.g. stabilizer circuits or linear-optics circuits - seem not to capture the full power of $\mathsf{BQP}$.

On a related noted, $\mathsf{BPP}$, $\mathsf{MA}$, $\mathsf{BQP}$, and $\mathsf{QMA}$ are all semantic classes with no known syntactic characterization (see, e.g., this or this). My first instinct is that this is related to the fact that algebraic complexity classes like $\mathsf{VP}$ are syntactic, but I'm not sure that's right. At any rate, I don't think we know of any such semantic class with an algebraic analogue.

This is not to say that all of these approaches can't work, just to share some thoughts on them. I hope someone can get it to work!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.