<p><a href="http://arxiv.org/abs/quant-ph/0408129v1" rel="nofollow">This paper</a> elaborates on the ideas sketeched above in detail.</p>

CC BY-SA 2.5
2010-09-14T21:46:06.820Z
Thanks for the link. The connection to polynomial equations over $Z_2$ looks interesting.
Manu
CC BY-SA 2.5
2010-10-06T04:52:58.360Z
@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?
Robin Kothari
CC BY-SA 2.5
2010-10-06T05:10:25.033Z
@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".
Martin Schwarz
CC BY-SA 2.5
2010-10-06T12:17:20.390Z
Oh, alright. No problem. So I guess the question is still unresolved then.
Robin Kothari
CC BY-SA 2.5
2010-09-14T21:20:40.787Z
2010-09-14T21:20:40.787Z
Martin Schwarz
<p>Emanuele: Unfortunately, we don't know of any black-box problem capturing BQP as simple as the one you mentioned capturing BPP.</p>

<p>Intuitively, this is because it's hard to talk about BQP without bringing in <i>unitarity</i> 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 <i>less</i> powerful than #P! :-)</p>

<p>Having said that, besides the Dawson et al. paper that Martin Schwarz linked to, you should definitely check out <a href="http://arxiv.org/abs/0705.1180">this</a> and <a href="http://arxiv.org/abs/quant-ph/0610235">this</a> by Janzing and Wocjan, which give "surprisingly classical-looking" promise problems that capture BQP.</p>

<p>Also, let S &sube; {0,1}<sup>n</sup>, 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:R<sup>n</sup>&rarr;R such that</p>

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

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

<p>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:R<sup>n</sup>&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.</p>

CC BY-SA 2.5
2010-10-12T12:14:46.010Z
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.
Manu
CC BY-SA 2.5
2010-10-13T03:13:49.027Z
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.
Scott Aaronson
CC BY-SA 2.5
2010-10-13T03:19:31.317Z
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.
Scott Aaronson
CC BY-SA 2.5
2010-10-11T22:00:18.623Z
2010-10-11T22:00:18.623Z
Scott Aaronson
<p>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).</p>

<p>Is there a similar problem for BQP? <a href="http://rjlipton.wordpress.com/2009/08/27/stockmeyers-approximate-counting-method/#comment-1208">This comment by Ken Regan</a> suggests such a problem</p>

<hr>

<p>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!</p>

<p>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.</p>

<hr>

<p>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$.</p>

CC BY-SA 2.5
2010-09-15T15:12:41.930Z
I think that Ken Regan’s comment refers to the result BQP⊆AWPP by Fortnow and Rogers (JCSS 1999; http://people.cs.uchicago.edu/~fortnow/papers/quantum.pdf).
Tsuyoshi Ito
<cc.complexity-theory><quantum-computing><black-box>
Approximate counting problem capturing BQP
Manu
# Approximate counting problem capturing BQP

(Asked by: username_0 on 2010-09-14)

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](http://rjlipton.wordpress.com/2009/08/27/stockmeyers-approximate-counting-method/#comment-1208) 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$.

**Tags:** cc.complexity-theory, quantum-computing, black-box
> **Comments:**
> **username_1**: I think that Ken Regan’s comment refers to the result BQP⊆AWPP by Fortnow and Rogers (JCSS 1999; http://people.cs.uchicago.edu/~fortnow/papers/quantum.pdf).  

---

## 2 answers

### Answer by username_4 on 2010-10-11. Score: 18 | Accepted answer

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](http://arxiv.org/abs/0705.1180) and [this](http://arxiv.org/abs/quant-ph/0610235) 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.

> **Comments:**
> **username_0**: 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.  
> **username_4**: 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.  
> **username_4**: 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.  

---

### Answer by username_2 on 2010-09-14. Score: 6

[This paper](http://arxiv.org/abs/quant-ph/0408129v1) elaborates on the ideas sketeched above in detail.

> **Comments:**
> **username_0**: Thanks for the link. The connection to polynomial equations over $Z_2$ looks interesting.  
> **username_3**: @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?  
> **username_2**: @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".  
> **username_3**: Oh, alright. No problem. So I guess the question is still unresolved then.  

---

