Is $CAPP \in P$ known to collapse some quantum complexity classes to classical ones?

Question

Lets define the class

$ZBQP = \{ L \mid \exists \textit{P-uniform circuit family } \{C_i\}, \forall n \in \mathbb{N}, |x| = n, |\langle 0|C_n|x \rangle - I(x \in L)| \leq 9/10 \Longleftrightarrow x \in L\}.$

We note a construction of Ashley Montanaro, that for any quantum circuit $C$ there exists some multilinear polynomial of size linearly proportional to $C$, $f_C$, such that

$\langle 0 | C|0\rangle = \frac{gap(f_C)}{2^n}$

where $n$ is the number of variables in the polynomial and

$gap(f) = |f^{-1}(0)| - |f^{-1}(1)|.$

We now define CAPP, the Circuit Approximate Probability Problem, which is a function problem:

$C \mapsto v \textit{ where } |v - Pr_x(C(x) = 1)| \leq 1/10.$

Using this problem, we can get a $2/10$ error approximation for $gap(f)$, as

$gap(f) = 2^n (Pr(f(x) = 0) - Pr(f(x) = 1))$

and thus we can get an approximation for $\langle 0|C_n|0 \rangle$ (or for $\langle y| C_n |x \rangle$ by modifying the circuit and thus $f_C$ in the obvious way). As we have a two sided error for $ZBQP$ and this approximation gets us close enough to distinguish which side we're on, it seems that this allows us to solve $ZBQP$ problems in basically whatever function classes where we can do $CAPP$, which is suspected to be in $FP$ and is already in $FBPP$.

Does $ZBQP \neq BQP$ for any reason I'm missing? It seems like they may be equal, but I dunno.

Answer 1

This is a bit of a subtle point, but the reason that solving CAPP (and hence finding an approximation to $gap(f)$ with the corresponding level of accuracy) doesn't immediately give a good algorithm for approximating $\langle 0 | C | 0 \rangle$ for arbitrary quantum circuits $C$ is because of normalisation. This is discussed in Proposition 8 of the paper you mention.

But in particular, we don't have $\langle 0 | C | 0 \rangle = gap(f) / 2^n$, where $n$ is the number of variables in the polynomial; we have $\langle 0 | C | 0 \rangle = gap(f) / 2^{n-h/2}$, where $h$ is the number of internal Hadamard gates in the circuit (see Proposition 1). So this means that to get a good approximation to $\langle 0 | C | 0 \rangle$ (say, up to an additive error $1/3$, which is BQP-complete), we would need to approximate $gap(f)$ up to additive error $1/3 \cdot 2^{n-h/2}$, which can be much smaller if $h$ is large.