# Evidence that there is some problem in BQP distinct from BPP?

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?

• Well, there's the proof that they're in BQP. $\;$
– user6973
Oct 15, 2015 at 0:13
• Of course but the post is about whether there is really any evidence they are outside BPP. There is no collapse result for instance.
– user34945
Oct 15, 2015 at 0:14
• @Arul Can you be more specific what you mean by evidence? Oct 15, 2015 at 1:32
• 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?
– D.W.
Oct 20, 2015 at 5:36
• 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.)
– D.W.
Oct 20, 2015 at 6:28

• 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. Oct 15, 2015 at 8:56