# Consequences of BPP=BQP

If BPP=BQP then there is a polynomial time randomized factoring algorithm. A lot of other quantum algorithms that appeared to have an exponential speedup have recently been dequantized. For examples, see https://arxiv.org/abs/1910.06151 and references therein.

What other significant practical consequences would BPP = BQP be likely to lead to?

• BQP complete problem in BPP with complexity $n^{10^{10^{10^{10}}}}$ will practically get you tenure. – VS. Nov 25 '19 at 19:50
• @VS I think you mean will definitely get you tenure in practice :) – user15587 Nov 25 '19 at 20:31
• Which exponential speedups have been dequantized? – Mark Nov 26 '19 at 8:03
• @Mark See for example arxiv.org/abs/1910.06151 – Lembik Nov 26 '19 at 8:07
• Simulating some of quantum mechanics. – Dmitri Urbanowicz Nov 26 '19 at 11:26

• The Hidden Subgroup Problems (including integer factorization, discrete logarithm, Simon's problem) are all thought to have exponential speed-ups in $NP \cap coNP$. Forrelation and Boson Sampling are believed to be outside of the polynomial hierarchy. – botsina Nov 29 '19 at 11:02