Are there any evidences (1 physics, 2 mathematics AND 3 computer science) that particular problems such as integer factorization, discrete logarithm are in BQP but not in BPP? There do not seem to be any classical collapse results if these problems are in BPP. Is there reason to think BQP is certainly a class different from BPP?

  • $\begingroup$ Well, there's the proof that they're in BQP. $\;$ $\endgroup$
    – user6973
    Commented Oct 15, 2015 at 0:13
  • $\begingroup$ Of course but the post is about whether there is really any evidence they are outside BPP. There is no collapse result for instance. $\endgroup$
    – user34945
    Commented Oct 15, 2015 at 0:14
  • 5
    $\begingroup$ @Arul Can you be more specific what you mean by evidence? $\endgroup$ Commented Oct 15, 2015 at 1:32
  • $\begingroup$ One possible piece of "evidence" that factoring is not in BPP is that there has been a lot of effort to try to find a BPP algorithm for factoring, with no success. Do you count that as evidence? $\endgroup$
    – D.W.
    Commented Oct 20, 2015 at 5:36
  • 1
    $\begingroup$ OK, so then the question I should have asked is: why or why not? And what criteria are you using for what counts as "evidence"? Finally: please edit the question to include this information in the question, so people can choose answers that match your intent. (Lastly, I can't resist making one minor comment: In the question you ask "Is there reason to think BQP is different from BPP?", and the fact that people have tried and failed to find a factoring algorithm is a reason to think BQP is different from BPP. You might not like the reason, but it is a reason.) $\endgroup$
    – D.W.
    Commented Oct 20, 2015 at 6:28

1 Answer 1


Scott Aaronson has been addressing this topic: http://arxiv.org/abs/0910.4698

Related hardness results:

  • 6
    $\begingroup$ Specifically: Scott has been trying to show that if $\mathsf{BQP\subseteq PH}$, that the polynomial hierarchy collapses. If this is true, a similar collapse would result from $\mathsf{BQP = BPP}$ as a corollary. $\endgroup$ Commented Oct 15, 2015 at 8:56
  • 3
    $\begingroup$ You could expand your answer to include works on the question of whether BPP = BQP may imply a big collapse of the Polinomial Hierarchy (ie, the simulating commuting circuits, boson samplers, DQC1 => collapse of PH results). I can also do it later if you don't have time. $\endgroup$ Commented Oct 15, 2015 at 12:57

Your Answer

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