Approximate counting problem capturing BQP In the black-box model, the problem of determining the output of a BPP machine $M(x,r)$ on input $x$ is the approximate counting problem of determining $E_r M(x,r)$ with additive error 1/3 (say).

Is there a similar problem for BQP? This comment by Ken Regan suggests such a problem



You can reduce a BPP question to approximating a single #P function, but with BQP what you get is the difference of two #P functions, call them $f$ and $g$. Approximating $f$ and $g$ separately does not help you approximate $f - g$ when $f - g$ is near zero!

BQP does give you a little help: When the answer to the BQP question on an input $x$ is yes, you get that $f(x) - g(x)$ is close to the square root of $2^m$, where the counting predicates defining $f$ and $g$ have m binary variables after you substitute for $x$. (There are no absolute-value bars; “magically” you always get $f(x) &gt; g(x)$. Under common representations of quantum circuits for BQP, $m$ becomes the number of Hadamard gates.) When the answer is no, the difference is close to 0.



Can you precisely formulate such a problem as close as possible to BQP? I am hoping for something like: given black-box access to functions $f,g$ mapping $X$ to $Y$, with the promise that ..., estimate $f-g$ to within $\varepsilon$.
Emanuele: Unfortunately, we don't know of any black-box problem capturing BQP as simple as the one you mentioned capturing BPP.

Intuitively, this is because it's hard to talk about BQP without bringing in unitarity in one form or another.  The ability to sum both positive and negative numbers is what makes BQP more powerful than BPP, but then unitarity is what makes BQP less powerful than #P! :-)

Having said that, besides the Dawson et al. paper that Martin Schwarz linked to, you should definitely check out this and this by Janzing and Wocjan, which give "surprisingly classical-looking" promise problems that capture BQP.

Also, let S &sube; {0,1}n, and consider a Boolean function f:S&rarr;{0,1}.  Then I have a conjecture from years ago which says that Q(f), the bounded-error quantum query complexity of f, is polynomially related to the minimum degree of a real polynomial p:Rn&rarr;R such that

(i) p(x)&isin;[0,1] for all x&isin;{0,1}n, and

(ii) |p(x)-f(x)| &le; &epsilon; for all x&isin;S.

If this conjecture holds, then an "approximate counting problem capturing BQP" would simply be to approximate the value of a polylog(n)-degree polynomial p:Rn&rarr;R, at a specified point on the Boolean cube, given that p is bounded everywhere on the Boolean cube.  This might be about as close as one could get to an answer to your question.