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 Oct 15 '15 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 Oct 15 '15 at 0:14
  • 5
    $\begingroup$ @Arul Can you be more specific what you mean by evidence? $\endgroup$ – Joshua Herman Oct 15 '15 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. Oct 20 '15 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. Oct 20 '15 at 6:28

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

Related hardness results:

  • 5
    $\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$ – Niel de Beaudrap Oct 15 '15 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$ – Juan Bermejo Vega Oct 15 '15 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy