<p>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.</p>

CC BY-SA 4.0
2019-11-28T18:12:39.217Z
Moore and fusion progress? Evidence?
VS.
CC BY-SA 4.0
2019-11-29T11:02:49.227Z
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
CC BY-SA 4.0
2019-11-29T11:06:02.270Z
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.
botsina
CC BY-SA 4.0
2019-11-28T14:52:48.567Z
2019-11-28T14:52:48.567Z
botsina
<p>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 <a href="https://arxiv.org/abs/1910.06151" rel="noreferrer">https://arxiv.org/abs/1910.06151</a> and references therein.</p>

<p>What other significant practical consequences would BPP = BQP be likely to lead to?</p>

CC BY-SA 4.0
2019-11-25T19:50:09.053Z
BQP complete problem in BPP with complexity $n^{10^{10^{10^{10}}}}$ will practically get you tenure.
VS.
CC BY-SA 4.0
2019-11-26T08:03:42.050Z
Which exponential speedups have been dequantized?
Mark Schultz-Wu
CC BY-SA 4.0
2019-11-26T08:07:05.403Z
@Mark See for example https://arxiv.org/abs/1910.06151
Simd
CC BY-SA 4.0
2019-11-26T11:26:36.490Z
Simulating some of quantum mechanics.
Dmitri Urbanowicz
CC BY-SA 4.0
2019-11-29T12:06:43.837Z
¿This also proposes that quantum cryptography is insecure when generated in certain contexts (ML)?
Lem n
CC BY-SA 4.0
2019-11-30T13:15:09.340Z
If $BQP=BPP$, then it doesn't make any sense. Why? because then Extended Church-Turing Thesis would be true or $P \neq BPP$. I believe that $BQP$ is larger class than $BPP$, i.e. $BQP \neq BPP$. Moreover, $BQP=BPP$ means quantum computation doesn't give us any powerful computation over randomized computation. And Dequantization = Derandomization.
user777
<cc.complexity-theory>
Consequences of BPP=BQP
Simd
# Consequences of BPP=BQP

(Asked by: username_0 on 2019-11-25)

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?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: BQP complete problem in BPP with complexity $n^{10^{10^{10^{10}}}}$ will practically get you tenure.  
> **username_2**: Which exponential speedups have been dequantized?  
> **username_0**: @Mark See for example https://arxiv.org/abs/1910.06151  
> **username_3**: Simulating some of quantum mechanics.  
> **username_4**: ¿This also proposes that quantum cryptography is insecure when generated in certain contexts (ML)?  
> **username_5**: If $BQP=BPP$, then it doesn't make any sense. Why? because then Extended Church-Turing Thesis would be true or $P \neq BPP$. I believe that $BQP$ is larger class than $BPP$, i.e. $BQP \neq BPP$. Moreover, $BQP=BPP$ means quantum computation doesn't give us any powerful computation over randomized computation. And Dequantization = Derandomization.  

---

## 1 answers

### Answer by username_6 on 2019-11-28. Score: 3

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.

> **Comments:**
> **username_1**: Moore and fusion progress? Evidence?  
> **username_6**: 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.  
> **username_6**: 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.  

---

