29
$\begingroup$

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

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
18
$\begingroup$

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 ⊆ {0,1}n, and consider a Boolean function f:S→{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→R such that

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

(ii) |p(x)-f(x)| ≤ ε for all x∈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→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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks. I checked this answer since "This might be about as close as one could get to an answer to your question." Question: what is the role of "S" in your conjecture? I am confused by (i) talking about {0,1}^n and the rest talking about S. $\endgroup$
    – Manu
    Commented Oct 12, 2010 at 12:14
  • $\begingroup$ Emanuele: If S={0,1}^n, then f is a total Boolean function. In that case, it's already known that the quantum query complexity is polynomially related to the approximate degree (as well as to the deterministic and randomized query complexity). So the interesting case is when f is a partial Boolean function: i.e., the quantum algorithm only needs to work on inputs satisfying the promise that x belongs to S. That's the situation where quantum algorithms like Simon's (which exponentially outperform the best classical algorithm) become possible. $\endgroup$
    – Scott Aaronson
    Commented Oct 13, 2010 at 3:13
  • $\begingroup$ Note that, while the quantum algorithm only needs to compute f on inputs belonging to the set S, the algorithm's acceptance probability on inputs not in S still belongs to the interval [0,1]! Silly as it sounds, that's often been a crucial observation in proving quantum lower bounds via the polynomial method. And if I hadn't required the polynomial p to be bounded in [0,1] for all x in {0,1}^n (even x not in S), then my conjecture would have been trivially false. $\endgroup$
    – Scott Aaronson
    Commented Oct 13, 2010 at 3:19
6
$\begingroup$

This paper elaborates on the ideas sketeched above in detail.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the link. The connection to polynomial equations over $Z_2$ looks interesting. $\endgroup$
    – Manu
    Commented Sep 14, 2010 at 21:46
  • 1
    $\begingroup$ @Emanuele Viola, @Martin Schwarz: I don't really see how this paper answers the original question. For one, this paper doesn't talk about black box problems at all. I can't seem to get a crisp formulation of a black box problem out of the paper, of the type that is asked in the question. Perhaps one of you could shed some light on this? $\endgroup$
    – Robin Kothari
    Commented Oct 6, 2010 at 4:52
  • 1
    $\begingroup$ @Robin Kothari: I agree, that the paper doesn't yield a black box problem, as originally asked. It does elaborate on the Ken Regan comment, though. I should have made this a "comment" rather than an "answer". $\endgroup$
    – Martin Schwarz
    Commented Oct 6, 2010 at 5:10
  • 1
    $\begingroup$ Oh, alright. No problem. So I guess the question is still unresolved then. $\endgroup$
    – Robin Kothari
    Commented Oct 6, 2010 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.