<p>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 <span class="math-container">$f$</span> (really, a family of polynomials <span class="math-container">$f_n$</span>, one for each <span class="math-container">$n$</span>) such that <span class="math-container">$f = (f_n)$</span> is in some sense complete for <span class="math-container">$\mathsf{BQP}$</span> (resp., <span class="math-container">$\mathsf{QMA}$</span>). 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 <span class="math-container">$f_G(x)$</span> at some point <span class="math-container">$x$</span>". 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 <span class="math-container">$\mathsf{BQP}$</span>-complete. Evaluating the Jones polynomial given a link in general is <span class="math-container">$\mathsf{\# P}$</span>-hard (see references e.g. <a href="http://dx.doi.org/10.4086/toc.2015.v011a006" rel="nofollow noreferrer">here</a>). So there are two issues here in using this to define "<span class="math-container">$\mathsf{VBQP}$</span>": the first is that the Jones polynomial in general is <span class="math-container">$\mathsf{\# P}$</span>-hard, so if you tried to use it you might end up with <span class="math-container">$\mathsf{VNP}$</span> again. Second, it's <em>not</em> just a single family of polynomials, it's a question of the above form (given an input object <span class="math-container">$G$</span>, compute <span class="math-container">$f_G$</span>, rather than evaluate <span class="math-container">$f_n(G)$</span> which is what we'd want).</p>

<p>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 <span class="math-container">$\mathsf{\# P}$</span>- or <span class="math-container">$\mathsf{VNP}$</span>-completeness.</p>

<p>Yet another approach you might try is to somehow mimic the "universal circuit" constructions for <span class="math-container">$\mathsf{VP}$</span>-complete problems (those by <a href="https://dx.doi.org/10.1007/978-3-662-04179-6" rel="nofollow noreferrer">Burgisser</a> and then <a href="https://dx.doi.org/10.4086/toc.2010.v006a007" rel="nofollow noreferrer">Raz</a>, see, e.g., <a href="https://arxiv.org/abs/1307.3863" rel="nofollow noreferrer">Mahajan's survey</a> or the references in Section 5 of <a href="https://eccc.weizmann.ac.il//report/2016/038/" rel="nofollow noreferrer">Mahajan-Saurabh</a>) 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 <span class="math-container">$2^n$</span> 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 <span class="math-container">$\mathsf{BQP}$</span>.</p>

<p>On a related noted, <span class="math-container">$\mathsf{BPP}$</span>, <span class="math-container">$\mathsf{MA}$</span>, <span class="math-container">$\mathsf{BQP}$</span>, and <span class="math-container">$\mathsf{QMA}$</span> are all semantic classes with no known syntactic characterization (see, e.g., <a href="https://cstheory.stackexchange.com/q/1233/129">this</a> or <a href="https://cstheory.stackexchange.com/q/4792/129">this</a>). My first instinct is that this is related to the fact that algebraic complexity classes like <span class="math-container">$\mathsf{VP}$</span> are syntactic, but I'm not sure that's right. At any rate, I don't think we know of <em>any</em> such semantic class with an algebraic analogue.</p>

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

CC BY-SA 4.0
2019-05-14T16:31:45.260Z
2019-05-25T13:39:30.737Z
2019-05-25T13:39:30.737Z
Joshua Grochow
<p>From <a href="https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity#Algebraic_P_and_NP" rel="noreferrer">Wikipedia</a>:</p>
<blockquote>
<p><span class="math-container">$\mathsf{VP}$</span>: The class VP is the algebraic analog of P; it is the class of polynomials <span class="math-container">$f$</span>  of polynomial degree that have polynomial size circuits over a fixed field <span class="math-container">$K$</span>.</p>
<p><span class="math-container">$\mathsf{VNP}$</span>: The class VNP is the analog of NP. VNP can be thought of as the class of polynomials <span class="math-container">$f$</span> of polynomial degree such that given a monomial we can determine its coefficient in <span class="math-container">$f$</span> efficiently, with a polynomial-size circuit.</p>
</blockquote>
<p>There have been attempts to implement polynomials <span class="math-container">$f$</span> using quantum circuits, cf. <a href="https://arxiv.org/abs/1805.12445" rel="noreferrer">arXiv:1805.12445</a>. So does there exist any quantum analog of the <span class="math-container">$\mathsf{VP}$</span> vs. <span class="math-container">$\mathsf{VNP}$</span> problem? Is there any paper on this topic?</p>
<p><sup><strong>P.S:</strong> I've asked a very related question on the <a href="https://quantumcomputing.stackexchange.com/questions/6128">Quantum Computing</a> site.</sup></p>

<cc.complexity-theory><reference-request><quantum-computing><circuit-complexity>
Is there any quantum analog of the VP vs. VNP problem?
Sanchayan Dutta
# Is there any quantum analog of the VP vs. VNP problem?

(Asked by: username_0 on 2019-05-13)

From [Wikipedia](https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity#Algebraic_P_and_NP):

> $\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](https://arxiv.org/abs/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](https://quantumcomputing.stackexchange.com/questions/6128) site.

**Tags:** cc.complexity-theory, reference-request, quantum-computing, circuit-complexity

---

## 1 answers

### Answer by username_1 on 2019-05-14. Score: 8 | Accepted answer

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](http://dx.doi.org/10.4086/toc.2015.v011a006)). 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](https://dx.doi.org/10.1007/978-3-662-04179-6) and then [Raz](https://dx.doi.org/10.4086/toc.2010.v006a007), see, e.g., [Mahajan's survey](https://arxiv.org/abs/1307.3863) or the references in Section 5 of [Mahajan-Saurabh](https://eccc.weizmann.ac.il//report/2016/038/)) 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](https://cstheory.stackexchange.com/q/1233/129) or [this](https://cstheory.stackexchange.com/q/4792/129)). 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!


---

