Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ 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! $\endgroup$– Joe FitzsimonsSep 14, 2010 at 21:19
-
$\begingroup$ @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. $\endgroup$– Joshua GrochowSep 15, 2010 at 18:27
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
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.
-
3$\begingroup$ I knew I had seen a blog post about this somewhere! $\endgroup$ Oct 3, 2010 at 17:53
$\begingroup$
$\endgroup$
7
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.
answered Sep 14, 2010 at 15:40
-
$\begingroup$ what are the references on problems with superpolynomial speedups that don't rely on the Abelian HSP? $\endgroup$ Sep 14, 2010 at 22:58
-
$\begingroup$ a more precise question is "what are the references on problems with superpolynomial speedups that don't rely on the HSP at all?" $\endgroup$ Sep 14, 2010 at 23:24
-
6$\begingroup$ The quantum algorithms zoo (its.caltech.edu/~sjordan/zoo.html) has a large list of algorithms and references for each. $\endgroup$ Sep 15, 2010 at 0:19
-
1$\begingroup$ @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. $\endgroup$ Sep 15, 2010 at 19:35
-
2$\begingroup$ 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. $\endgroup$– JasonSep 16, 2010 at 8:18
$\begingroup$
$\endgroup$
2
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^{\#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.
-
3$\begingroup$ P^{#P} = P^{PP}, so you could use that instead. $\endgroup$ Sep 15, 2010 at 0:28
-
$\begingroup$ Yes, that would have been the smart thing to do! $\endgroup$ Sep 15, 2010 at 0:32