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?

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

Assuming a practical algorithm is found, the applications will overwhelmingly be in quantum simulation. Basically any research in large quantum systems - chemistry, biochemistry, condensed matter, nuclear systems will be affected. We'd likely see major advances in basic biology, medicine and pharmaceuticals. Moore's law would be restored for a few years and we would finally have working fusion reactors. Physical simulation using the new algorithm might also lead to new physics.

| cite | improve this answer | |
  • 1
    $\begingroup$ Moore and fusion progress? Evidence? $\endgroup$ – VS. Nov 28 '19 at 18:12
  • $\begingroup$ Could you give a specific example of such a problem that is in BQP that is exponentially hard to perform classically? The more detail, the better. $\endgroup$ – user15587 Nov 29 '19 at 8:07
  • $\begingroup$ 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. $\endgroup$ – botsina Nov 29 '19 at 11:02
  • $\begingroup$ Efficient quantum simulation would make it easier to deal with quantum effects in chip design and to design a quantum computer. That should allow some chip speedups. Fusion should be easier because it would be much easier to predict what fusion reactors are going to do and control them. $\endgroup$ – botsina Nov 29 '19 at 11:06
  • $\begingroup$ The Hidden Subgroup Problems are good examples but very similar to the example given by the OP. Can you give a mathematcal definition for a quantum chemistry simulation problem that is in BQP but not thought to be in BPP? $\endgroup$ – user15587 Nov 30 '19 at 17:21

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.