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$
$\endgroup$
6
-
$\begingroup$ Well, there's the proof that they're in BQP. $\;$ $\endgroup$– user6973Oct 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$– user34945Oct 15, 2015 at 0:14
-
5$\begingroup$ @Arul Can you be more specific what you mean by evidence? $\endgroup$– Joshua HermanOct 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.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.Oct 20, 2015 at 6:28
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
2
Scott Aaronson has been addressing this topic: http://arxiv.org/abs/0910.4698
Related hardness results:
- Boson sampling: http://arxiv.org/abs/1011.3245
- Commuting circuits: http://arxiv.org/abs/1005.1407
- DQC1 model: http://arxiv.org/abs/1509.07276
- Extended Clifford circuits: http://arxiv.org/abs/1305.6190
-
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$ 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$ Oct 15, 2015 at 12:57