Estimating output amplitudes of quantum circuits as GapP functions

Question

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

\begin{equation} \langle 0^{n}| U_x |0^{n} \rangle = \frac{f - g}{\sqrt{2^{h}}}, \end{equation} 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)?

Answer 1

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.

Answer 2

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)$.