# Estimating output amplitudes of quantum circuits as GapP functions

Let's fix a universal gate set comprising of a Hadamard gate and a Toffoli gate. Consider an $$n$$ qubit quantum circuit $$U_{x}$$, made up of gates from that universal set, applied to initial state $$|0^{n} \rangle$$.

The transition amplitude $$\langle 0^{n}| U_x |0^{n} \rangle$$ can be written as

$$$$\langle 0^{n}| U_x |0^{n} \rangle = \frac{f - g}{\sqrt{2^{h}}},$$$$ where $$h$$ is the number of Hadamard gates and $$f$$ and $$g$$ are two #P functions. This equivalence is proven in https://arxiv.org/abs/quant-ph/0408129 (equation 6).

Let's say that we are given an efficient classical description of $$U_x$$ and we want to estimate this transition amplitude classically, upto inverse polynomial additive error. We do not care whether our estimated value preserves the sign of the original output amplitude.

A naive way to estimate the transition amplitude classically, given an efficient description of the circuit $$U_{x}$$ as the input, would be to estimate $$f$$ and $$g$$ individually, upto inverse polynomial additive error. Something like this is hinted in Section V of the paper linked.

But don't we need oracle access to the formulas corresponding to $$f$$ and $$g$$ (ie, two Boolean/3SAT formulas such that $$f$$ is the number of solutions for one, and $$g$$ is the number of solutions for the other) to individually estimate $$f$$ and $$g$$ respectively (upto an inverse polynomial additive error)?

Can we efficiently get a description of these two corresponding Boolean formulas just from the description of the quantum circuit $$U_x$$ given to us as input (and hence, not need oracle access to these formulas in the input)?

Given a description of $$U_x$$ you can efficiently find a decription of $$\textbf{B}$$ and $$\phi$$ by iterating over the gates of $$U_x$$ and adding one "free" variable every time you have a Hadamard gate and imposing the constraint of the Toffoli gate.

Regarding the approximation, you can estime $$f, g$$ to additive error $$\frac{2^h}{\text{poly}(h)}$$ (see here) but this will give you $$\frac{2^{h/2 + 1}}{\text{poly}(h)}$$ error for $$|\langle 0^n|U_x|0^n \rangle |$$.

In fact, you can't hope for a classical randomized poly-time algorithm to give an estimate of $$|\langle 0^n|U_x|0^n \rangle |$$ with additive inverse polynomial error unless BQP = BPP, since if $$L \in$$ BQP:

• $$x \in L \implies \text{Pr(aceptance)} > 1 - 2^{-n} \implies |\langle 0^n|U_x|0^n \rangle |^2 < 2^{-n}$$
• $$x \notin L \implies \text{Pr(aceptance)} < 2^{-n} \implies |\langle 0^n|U_x|0^n \rangle |^2 > 1- 2^{-n}$$

and with an estimate of $$|\langle 0^n|U_x|0^n \rangle |$$ with additive inverse polynomial error would allow us to distinguish between the two cases.

I think there might be a confusion between a Boolean formula (which may be easy to evaluate) and the number of solutions or a difference in the number solutions of the Boolean formula (which may be very difficult to evaluate). You're calling $$f$$ and $$g$$ #P-functions, but really you're interested in $$\#(0)$$ and $$\#(1)$$ which are values that count the number of solutions to a given function.

For example let $$U_x$$ be a quantum circuit; we can use this circuit to build a classical description of certain function, call it $$\textbf B$$. We can let $$\#(0)$$ and $$\#(1)$$ count the number of positive and negative terms in the sum:

$$\langle \textbf b\vert U_x\vert \textbf a\rangle=\frac{1}{\sqrt{2^h}}\sum_{x:\textbf B(x)=\textbf b}(-1)^{\phi(x)}.$$

That is, I believe that your classical description of $$U_x$$ indeed gives you sufficient information to get an efficient classical description of the formulae $$\phi$$ to which $$\#(0)$$ and $$\#(1)$$ count the number of $$0$$'s/$$1$$'s; however, that doesn't necessarily mean that you can efficiently evaluate $$\#(0)$$ and $$\#(1)$$ to a high-enough precision to calculate $$\vert \#(0)-\#(1)\vert$$.

There are some tricks such as Stockmeyer approximation that let you classically evaluate $$\#(0)$$ or $$\#(1)$$ individually to some precision, but these tricks are not efficient (being in Arthur-Merlin). More importantly these tricks are nowhere near enough accuracy to efficiently evaluate the (absolute value of) the difference between $$\#(0)$$ and $$\#(1)$$.

• This is where my confusion lies. Given an efficient classical description of $U_x$, can we, in classical polynomial time, find a description of the function $\textbf B$ and the formula $\phi$? If so, how? The paper outlines a method for it, but why is the method efficient? – BlackHat18 Apr 16 at 14:47
• I haven't studied the paper in a lot of detail but couldn't the method on FIG. 2 and equation 2 be generalized? There are only a polynomial number of Hadamard gates $H$. – Mark S Apr 16 at 15:40
• I'm not sure but I think the problem is most interesting when $\#(0)$ and $\#(1)$ are close to each other initially. For example you can consider a Monte-Carlo alg. to separately evaluate the volume of two polytopes centered at the origin that are of similar size and of similar shape and of a similar orientation, but the Monte-Carlo algorithm would likely fail to evaluate the volume of the symmetric difference if the two polytopes look really close to each other. I think in the linked question one of $\#(0)$ or $\#(1)$ would already be large and hence trivial to solve. – Mark S Apr 16 at 20:16
• Indeed, the problem is that Stockmeyer gives you an approximation up to a multiplicative accuracy, but multiplicative accuracies don't behave nicely under differences. – Norbert Schuch Apr 16 at 20:58
• That sounds close to correct but multiplicative error to find any one of #0 or #1 individually might still require inverting a hash function which can be tough, in NP. – Mark S Apr 17 at 12:51