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)?


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

  • $\begingroup$ 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? $\endgroup$ – BlackHat18 Apr 16 at 14:47
  • 1
    $\begingroup$ 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$. $\endgroup$ – Mark S Apr 16 at 15:40
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark S Apr 16 at 20:16
  • 1
    $\begingroup$ Indeed, the problem is that Stockmeyer gives you an approximation up to a multiplicative accuracy, but multiplicative accuracies don't behave nicely under differences. $\endgroup$ – Norbert Schuch Apr 16 at 20:58
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark S Apr 17 at 12:51

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.