<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-12-13T09:34:29.400Z
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.
Samuel Schlesinger
CC BY-SA 3.0
2017-12-13T15:32:12.170Z
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.
Ashley Montanaro
CC BY-SA 3.0
2017-12-18T19:35:07.247Z
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.
Samuel Schlesinger
CC BY-SA 3.0
2017-12-13T09:22:10.827Z
2017-12-13T09:22:10.827Z
Ashley Montanaro
<p>Lets define the class </p>

<p>$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\}.$</p>

<p>We note <a href="https://arxiv.org/pdf/1607.08473.pdf" rel="nofollow noreferrer">a construction of Ashley Montanaro</a>, that for any quantum circuit $C$ there exists some multilinear polynomial of size linearly proportional to $C$, $f_C$, such that</p>

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

<p>where $n$ is the number of variables in the polynomial and</p>

<p>$gap(f) = |f^{-1}(0)| - |f^{-1}(1)|.$ </p>

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

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

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

<p>$gap(f) = 2^n (Pr(f(x) = 0) - Pr(f(x) = 1))$</p>

<p>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$.</p>

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

<quantum-computing><circuit-complexity>
Is $CAPP \in P$ known to collapse some quantum complexity classes to classical ones?
Samuel Schlesinger
# Is $CAPP \in P$ known to collapse some quantum complexity classes to classical ones?

(Asked by: username_0 on 2017-12-12)

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](https://arxiv.org/pdf/1607.08473.pdf), 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.

**Tags:** quantum-computing, circuit-complexity

---

## 1 answers

### Answer by username_1 on 2017-12-13. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: 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.  

---

