up vote 18 down vote favorite
2
share [g+] share [fb]

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

link|improve this question
2  
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 Sep 14 '10 at 21:19
@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 Sep 15 '10 at 18:27
feedback

3 Answers

up vote 19 down vote

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 where he observed that the welded-tree speedup of Childs, Cleve, Deotto, Farhi, Gutmann and Spielman 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.

link|improve this answer
2  
I knew I had seen a blog post about this somewhere! – Joe Fitzsimons Oct 3 '10 at 17:53
feedback
up vote 14 down vote

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.

link|improve this answer
what are the references on problems with superpolynomial speedups that don't rely on the Abelian HSP? – Marcos Villagra Sep 14 '10 at 22:58
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 Sep 14 '10 at 23:24
5  
The quantum algorithms zoo (its.caltech.edu/~sjordan/zoo.html) has a large list of algorithms and references for each. – Robin Kothari Sep 15 '10 at 0:19
1  
@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 Sep 15 '10 at 19:35
2  
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 Sep 16 '10 at 8:18
show 2 more comments
feedback
up vote 9 down vote

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 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 showing that efficient classical sampling of the output of boson scattering would imply $BPP^{NP} = P^{SharpP}$ (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.

link|improve this answer
2  
P^{#P} = P^{PP}, so you could use that instead. – Robin Kothari Sep 15 '10 at 0:28
Yes, that would have been the smart thing to do! – Joe Fitzsimons Sep 15 '10 at 0:32
feedback

Your Answer

 
or
required, but never shown
discard

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