6
$\begingroup$

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?

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

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Moore and fusion progress? Evidence? $\endgroup$
    – VS.
    Nov 28, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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