<p>I have no idea how one would disprove a claim like that, but I doubt that it's true. We do have other exponential speedups by quantum algorithms that don't rely on the Abelian HSP. Moreover, Abelian HSP is not known to be BQP-complete.</p>

<p>On the other hand, problems which are known to be BQP-complete are problems like computing Knot invariants, other manifold invariants, partition functions and doing Hamiltonian simulation. With an oracle for any of <em>these</em> problems, BPP would be as powerful as BQP.</p>

<p>Finally, I'm sure one can construct an oracle separation between the two classes you mention, but that would not be a fair way to compare them since one class can make quantum queries and the other cannot, so the separation would merely reflect this fact.</p>

CC BY-SA 2.5
2010-09-14T22:58:46.533Z
what are the references on problems with superpolynomial speedups that don't rely on the Abelian HSP?
Marcos Villagra
CC BY-SA 2.5
2010-09-14T23:24:08.963Z
a more precise question is "what are the references on problems with superpolynomial speedups that don't rely on the HSP at all?"
Marcos Villagra
CC BY-SA 2.5
2010-09-15T00:19:07.703Z
The quantum algorithms zoo (http://www.its.caltech.edu/~sjordan/zoo.html) has a large list of algorithms and references for each.
Robin Kothari
CC BY-SA 2.5
2010-09-15T18:48:15.173Z
@Robin: I'm not sure I understand why you say an oracle separation would be "unfair" in this setting.  What is it that makes this setting different from, say, comparing BQP to P^NP, SZK, or PH by oracle results (or do you also think those results are unfair)?
Joshua Grochow
CC BY-SA 2.5
2010-09-15T19:35:31.017Z
@Joshua: Those oracle separations are fine, because they're trying to exhibit the power of quantum queries. Let me give an example of what I mean. If there were a polytime algorithm for 3SAT, and let this algorithm be called X. Clearly P^X contains NP. Yet, we can construct an oracle separation between P^X and NP, because in the first case only the P machine can access the oracle, and the separation merely reflects the fact that non-deterministic queries are better than deterministic queries. Similarly, even if BPP^AHSP contained BQP, we could separate them with an oracle quite easily.
Robin Kothari
CC BY-SA 2.5
2010-09-15T23:12:34.767Z
@Robin: Thanks for the clarification.  In a sense, both examples are really about giving a machine oracle access to an object that either does not or that we don't allow to relativize (in the first case, the object is a classical TM deciding unrelativized 3SAT, and in the second case AHSP).
Joshua Grochow
CC BY-SA 2.5
2010-09-16T08:18:45.030Z
Thanks for all the answers. In particular, thanks for reminding me about the Jones and HOMFLY polynomials, which have nothing to do with HSPs. Evaluating the Jones polynomial exactly at fifth roots of unity is #P-hard, but approximating them up to some fraction epsilon with some probabilistic accuracy is in BQP.
Jason
CC BY-SA 2.5
2010-09-14T15:40:47.537Z
2010-09-14T15:40:47.537Z
Robin Kothari
<p>Like many complexity-class separations, our best guess is that the answer is that BPP^{HSP} != BQP, but we can only prove this rigorously relative to oracles.  This separation was observed by Scott Aaronson in this <a href="http://scottaaronson.com/blog/?p=114">blog post</a>
where he observed that the <a href="http://www.arxiv.org/abs/quant-ph/0209131">welded-tree speedup of Childs, Cleve, Deotto, Farhi, Gutmann and Spielman</a> was not contained in SZK.</p>

<p>On the other hand, BPP^{HSP} <em>is</em> contained in SZK, at least if the goal is to determine the size of the hidden subgroup.  This includes even the abelian HSP, although I'm not sure how exactly to find the generators of an arbitrary hidden subgroup in SZK.  The reason we can decide the size of the hidden subgroup is that if f:G->S has hidden subgroup H, and we choose g uniformly at random from G, then f(g) is uniformly random over a set of size |G|/|H|. In particular, f(g) has entropy log|G| - log|H|.  And entropy estimation is in SZK.</p>

CC BY-SA 2.5
2010-10-03T17:53:05.093Z
I knew I had seen a blog post about this somewhere!
Joe Fitzsimons
CC BY-SA 2.5
2010-10-03T13:01:04.137Z
2010-10-03T14:32:45.863Z
2010-10-03T14:32:45.863Z
Aram Harrow
<p>I have to agree with Robin that this is not necessarily an easy claim to disprove, though it is almost certainly false. An immediate reason that makes me doubt it is that post selected quantum computation is equal to PP, and this would seem to hint that the statistics would be difficult to recreate. Scott Aaronson has a <a href="http://arxiv.org/abs/0910.4698" rel="nofollow noreferrer">paper</a> at STOC showing that there is an oracle relation problem which is solvable in BQP but not PH.</p>

<p>Additionally, Scott also seems to have a <a href="http://www.scottaaronson.com/talks/newev-qip.ppt" rel="nofollow noreferrer">result</a> showing that efficient classical sampling of the output of boson scattering would imply $BPP^{NP} = P^{\#P}$ (latex won't allow # here), which seems incredibly unlikely. I would think that you will get a similar result even if you allow an Abelian hidden subgroup oracle. Of course this also implies a barrier to deciding your question, since if the Abelian hidden subgroup problem was in P, then an affirmative answer would imply the collapse of the polynomial hierarchy.</p>

CC BY-SA 2.5
2010-09-15T00:28:57.523Z
P^{#P} = P^{PP}, so you could use that instead.
Robin Kothari
CC BY-SA 2.5
2010-09-15T00:32:30.123Z
Yes, that would have been the smart thing to do!
Joe Fitzsimons
CC BY-SA 3.0
2010-09-14T21:01:00.217Z
2017-04-30T23:22:12.160Z
2017-04-30T23:22:12.160Z
Joe Fitzsimons
<p>Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?</p>

CC BY-SA 2.5
2010-09-14T21:19:57.890Z
Actually there is a fair amount of work on non-Abelian hidden subgroup problems in quantum algorithms research, so I certainly hope this is not the case!
Joe Fitzsimons
CC BY-SA 2.5
2010-09-15T18:27:13.710Z
@Joe: I thought most of the work on non-Abelian HSPs was for groups that are somehow "close to Abelian" -- but please correct me if I'm wrong, as I'm no expert in the area.  But if that is indeed the case, then a positive answer to the question might not contradict the works you refer to.
Joshua Grochow
<complexity-classes><quantum-computing>
Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?
Jason
# Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?

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

Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?

**Tags:** complexity-classes, quantum-computing

> **Comments:**
> **username_1**: Actually there is a fair amount of work on non-Abelian hidden subgroup problems in quantum algorithms research, so I certainly hope this is not the case!  
> **username_2**: @Joe: I thought most of the work on non-Abelian HSPs was for groups that are somehow "close to Abelian" -- but please correct me if I'm wrong, as I'm no expert in the area.  But if that is indeed the case, then a positive answer to the question might not contradict the works you refer to.  

---

## 3 answers

### Answer by username_5 on 2010-10-03. Score: 27

Like many complexity-class separations, our best guess is that the answer is that BPP^{HSP} != BQP, but we can only prove this rigorously relative to oracles. This separation was observed by Scott Aaronson in this [blog post](http://scottaaronson.com/blog/?p=114)
where he observed that the [welded-tree speedup of Childs, Cleve, Deotto, Farhi, Gutmann and Spielman](http://www.arxiv.org/abs/quant-ph/0209131) was not contained in SZK.

On the other hand, BPP^{HSP} *is* contained in SZK, at least if the goal is to determine the size of the hidden subgroup. This includes even the abelian HSP, although I'm not sure how exactly to find the generators of an arbitrary hidden subgroup in SZK. The reason we can decide the size of the hidden subgroup is that if f:G->S has hidden subgroup H, and we choose g uniformly at random from G, then f(g) is uniformly random over a set of size |G|/|H|. In particular, f(g) has entropy log|G| - log|H|. And entropy estimation is in SZK.

> **Comments:**
> **username_1**: I knew I had seen a blog post about this somewhere!  

---

### Answer by username_3 on 2010-09-14. Score: 17

I have no idea how one would disprove a claim like that, but I doubt that it's true. We do have other exponential speedups by quantum algorithms that don't rely on the Abelian HSP. Moreover, Abelian HSP is not known to be BQP-complete.

On the other hand, problems which are known to be BQP-complete are problems like computing Knot invariants, other manifold invariants, partition functions and doing Hamiltonian simulation. With an oracle for any of *these* problems, BPP would be as powerful as BQP.

Finally, I'm sure one can construct an oracle separation between the two classes you mention, but that would not be a fair way to compare them since one class can make quantum queries and the other cannot, so the separation would merely reflect this fact.

> **Comments:**
> **username_4**: what are the references on problems with superpolynomial speedups that don't rely on the Abelian HSP?  
> **username_4**: a more precise question is "what are the references on problems with superpolynomial speedups that don't rely on the HSP at all?"  
> **username_3**: The quantum algorithms zoo (http://www.its.caltech.edu/~sjordan/zoo.html) has a large list of algorithms and references for each.  
> **username_2**: @Robin: I'm not sure I understand why you say an oracle separation would be "unfair" in this setting.  What is it that makes this setting different from, say, comparing BQP to P^NP, SZK, or PH by oracle results (or do you also think those results are unfair)?  
> **username_3**: @Joshua: Those oracle separations are fine, because they're trying to exhibit the power of quantum queries. Let me give an example of what I mean. If there were a polytime algorithm for 3SAT, and let this algorithm be called X. Clearly P^X contains NP. Yet, we can construct an oracle separation between P^X and NP, because in the first case only the P machine can access the oracle, and the separation merely reflects the fact that non-deterministic queries are better than deterministic queries. Similarly, even if BPP^AHSP contained BQP, we could separate them with an oracle quite easily.  
> **username_2**: @Robin: Thanks for the clarification.  In a sense, both examples are really about giving a machine oracle access to an object that either does not or that we don't allow to relativize (in the first case, the object is a classical TM deciding unrelativized 3SAT, and in the second case AHSP).  
> **username_0**: Thanks for all the answers. In particular, thanks for reminding me about the Jones and HOMFLY polynomials, which have nothing to do with HSPs. Evaluating the Jones polynomial exactly at fifth roots of unity is #P-hard, but approximating them up to some fraction epsilon with some probabilistic accuracy is in BQP.  

---

### Answer by username_1 on 2010-09-14. Score: 11

I have to agree with Robin that this is not necessarily an easy claim to disprove, though it is almost certainly false. An immediate reason that makes me doubt it is that post selected quantum computation is equal to PP, and this would seem to hint that the statistics would be difficult to recreate. Scott Aaronson has a [paper](http://arxiv.org/abs/0910.4698) at STOC showing that there is an oracle relation problem which is solvable in BQP but not PH.

Additionally, Scott also seems to have a [result](http://www.scottaaronson.com/talks/newev-qip.ppt) showing that efficient classical sampling of the output of boson scattering would imply $BPP^{NP} = P^{\#P}$ (latex won't allow # here), which seems incredibly unlikely. I would think that you will get a similar result even if you allow an Abelian hidden subgroup oracle. Of course this also implies a barrier to deciding your question, since if the Abelian hidden subgroup problem was in P, then an affirmative answer would imply the collapse of the polynomial hierarchy.

> **Comments:**
> **username_3**: P^{#P} = P^{PP}, so you could use that instead.  
> **username_1**: Yes, that would have been the smart thing to do!  

---

