1
$\begingroup$

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.

Improve this question
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So in your paper you write that $\langle 0 | C | 0 \rangle = gap(f)/2^{n + h/2}$, but more than that it seems you can use another equivalent $f$ which you construct after you do the Hadamard removal process for which this works. $\endgroup$ – Samuel Schlesinger Dec 13 '17 at 9:34
  • 1
    $\begingroup$ Though there are many circuits that correspond to a given polynomial $f$, each circuit $C$ has only one associated polynomial $f_C$. One way of understanding the approximation method proposed in the original question is that it approximates an amplitude corresponding to one circuit associated with that polynomial $f$ up to a certain level of accuracy, but this does not correspond to an arbitrary circuit associated with that polynomial. e.g. if we use the construction of Observation 3 in the paper, this would only give an approximation for circuits with no internal Hadamard gates. $\endgroup$ – Ashley Montanaro Dec 13 '17 at 15:32
  • $\begingroup$ Okay, so I misunderstood the paper I believe and I'll have to read it again and go through the argument myself more rigorously. I plan to use it as a way to start asking about other properties of quantum circuits. In particular, it seems that circuit size is exactly proportional to the number of terms in the polynomial, unless I'm misunderstanding, so you could probably prove some theorems about how differently sized circuits act. $\endgroup$ – Samuel Schlesinger Dec 18 '17 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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