<p>No, there is no particular reason to think that, given a quantum algorithm that solves a problem very fast, one can find a classical algorithm that also runs very fast. The basic building blocks of a quantum computer are different, and although a classical computer can simulate a quantum computer (which means that quantum comparability theory and classical computability theory are the same), as far as we know it cannot do so <em>efficiently</em>.</p>

<p>No one has every proven a result like</p>

<blockquote>
  <p>If there exists a quantum algorithm that solves a decision problem in $O(f(n))$ time, then there exists a classical algorithm that solves the problem in $O(g(f(n))$ time for polynomial $g$</p>
</blockquote>

<p>which is approximately what you’d need for this question to have an affirmative answer. As far as I know there’s absolutely not reason to think that a theorem along these lines is true. To talk about a specific example, let’s look at factoring.</p>

<p><a href="https://en.m.wikipedia.org/wiki/Shor%27s_algorithm" rel="nofollow noreferrer">Shor’s Algorithm</a> achieves a superpolynomial speed-up in factoring, going from $$O(e^{1.9(\log N)^{1/3}(\log\log N)^{2/3}})$$ in the classical case to $Õ((\log N)^2)$ in the quantum case. There’s no particular reason (based on the existence of Shor’s algorithm) to think that factoring is in $P$. The technique used in Shor’s algorithm is fundamentally unusuable by classical computers, and there doesn’t seem to be any way to replicate the technique with a classical computer.</p>

CC BY-SA 3.0
2017-10-19T13:02:08.577Z
I do not mean "given a quantum algorithm that solves a problem much faster than a classical algorithm, one can use that $quantum \space  algorithm $ to find a classical algorithm that also runs very fast.", I mean it is possible to find $new \space classic \space algorithm $ on classic Turing Machine which can speedup in classic Turing Machine in superpolynomial?
XL _At_Here_There
CC BY-SA 3.0
2017-10-19T13:24:17.610Z
@XL_at_China if you don’t use the quantum algorithm to find/work out/get to the new classical algorithm, why did you mention quantum algorithms at all? Also, the best way to make text show up in *italics* is to use a single * on each side of the text. Save $ for mathematics.
Stella Biderman
CC BY-SA 3.0
2017-10-20T08:16:34.867Z
I think there must be an relation between them, in other word, quantum algorithm implies classic algorithm, but they are not same.
XL _At_Here_There
CC BY-SA 3.0
2017-10-22T12:28:19.563Z
@XL_at_China That is the question I was trying to answer. I’ve edited my answer to hopefully be clearer about this.
Stella Biderman
CC BY-SA 3.0
2017-10-19T12:05:28.487Z
2017-10-22T12:27:34.810Z
2017-10-22T12:27:34.810Z
Stella Biderman
<p>Does the complexity speedup in superpolynomial  by quantum computation mean it is possible to find new algorithm on classic Turing Machine which can speedup in classic Turing Machine in superpolynomial? </p>

<p>update: I have just found that Strong CT thesis is contradict to the belief that quantum model is faster than classic one,or quantum model can not be implemented if it is speedup of classic one on some problem,see <a href="http://math.nist.gov/quantum/zoo/" rel="nofollow noreferrer">http://math.nist.gov/quantum/zoo/</a></p>

<p>So, Strong CT thesis is not correct or the quantum computer is unable to be implemented, or Strong CT thesis is not correct or the quantum computer is unable to be implemented, and we can find new algorithm for those problems about which we have speedup quantum algorithm but classic one, which can simulate the quantum one.</p>

CC BY-SA 3.0
2017-10-19T19:06:39.843Z
I am having real trouble deciphering this question. Are you asking whether the following is true: "if there exists a quantum algorithm Q for problem P that runs superpolynomially faster than a classical algorithm A for the same problem, then there also exists a classical algorithm B that runs superpolynomially faster than A"? I see no reason at all why something like this would be true.
Sasho Nikolov
CC BY-SA 3.0
2017-10-20T08:14:42.087Z
@SashoNikolov yes, exactly, this is what I mean.
XL _At_Here_There
CC BY-SA 3.0
2017-10-20T17:50:22.640Z
@XL_at_China Wouldn't that by very definition contradict the idea of "quantum supremacy"? (Which is a currently wide open question)
Clement C.
CC BY-SA 3.0
2017-10-21T02:09:34.740Z
@ClementC. yes, I think so, because, Quantum computation does not reduce the computational complexity actually. NPC is still NPC
XL _At_Here_There
CC BY-SA 3.0
2017-10-22T21:17:37.517Z
So then you are conjecturing that BQP is contained in BPP. This is unknown and, afaik, is widely believed to be false.
Sasho Nikolov
<cc.complexity-theory><quantum-computing>
Complexity class on quantum computation and classic ones
XL _At_Here_There
# Complexity class on quantum computation and classic ones

(Asked by: username_0 on 2017-10-19)

Does the complexity speedup in superpolynomial by quantum computation mean it is possible to find new algorithm on classic Turing Machine which can speedup in classic Turing Machine in superpolynomial?

update: I have just found that Strong CT thesis is contradict to the belief that quantum model is faster than classic one,or quantum model can not be implemented if it is speedup of classic one on some problem,see <http://math.nist.gov/quantum/zoo/>

So, Strong CT thesis is not correct or the quantum computer is unable to be implemented, or Strong CT thesis is not correct or the quantum computer is unable to be implemented, and we can find new algorithm for those problems about which we have speedup quantum algorithm but classic one, which can simulate the quantum one.

**Tags:** cc.complexity-theory, quantum-computing

> **Comments:**
> **username_1**: I am having real trouble deciphering this question. Are you asking whether the following is true: "if there exists a quantum algorithm Q for problem P that runs superpolynomially faster than a classical algorithm A for the same problem, then there also exists a classical algorithm B that runs superpolynomially faster than A"? I see no reason at all why something like this would be true.  
> **username_0**: @SashoNikolov yes, exactly, this is what I mean.  
> **username_2**: @XL_at_China Wouldn't that by very definition contradict the idea of "quantum supremacy"? (Which is a currently wide open question)  
> **username_0**: @ClementC. yes, I think so, because, Quantum computation does not reduce the computational complexity actually. NPC is still NPC  
> **username_1**: So then you are conjecturing that BQP is contained in BPP. This is unknown and, afaik, is widely believed to be false.  

---

## 1 answers

### Answer by username_3 on 2017-10-19. Score: 1

No, there is no particular reason to think that, given a quantum algorithm that solves a problem very fast, one can find a classical algorithm that also runs very fast. The basic building blocks of a quantum computer are different, and although a classical computer can simulate a quantum computer (which means that quantum comparability theory and classical computability theory are the same), as far as we know it cannot do so *efficiently*.

No one has every proven a result like

> If there exists a quantum algorithm that solves a decision problem in $O(f(n))$ time, then there exists a classical algorithm that solves the problem in $O(g(f(n))$ time for polynomial $g$

which is approximately what you’d need for this question to have an affirmative answer. As far as I know there’s absolutely not reason to think that a theorem along these lines is true. To talk about a specific example, let’s look at factoring.

[Shor’s Algorithm](https://en.m.wikipedia.org/wiki/Shor%27s_algorithm) achieves a superpolynomial speed-up in factoring, going from $$O(e^{1.9(\log N)^{1/3}(\log\log N)^{2/3}})$$ in the classical case to $Õ((\log N)^2)$ in the quantum case. There’s no particular reason (based on the existence of Shor’s algorithm) to think that factoring is in $P$. The technique used in Shor’s algorithm is fundamentally unusuable by classical computers, and there doesn’t seem to be any way to replicate the technique with a classical computer.

> **Comments:**
> **username_0**: I do not mean "given a quantum algorithm that solves a problem much faster than a classical algorithm, one can use that $quantum \space  algorithm $ to find a classical algorithm that also runs very fast.", I mean it is possible to find $new \space classic \space algorithm $ on classic Turing Machine which can speedup in classic Turing Machine in superpolynomial?  
> **username_3**: @XL_at_China if you don’t use the quantum algorithm to find/work out/get to the new classical algorithm, why did you mention quantum algorithms at all? Also, the best way to make text show up in *italics* is to use a single * on each side of the text. Save $ for mathematics.  
> **username_0**: I think there must be an relation between them, in other word, quantum algorithm implies classic algorithm, but they are not same.  
> **username_3**: @XL_at_China That is the question I was trying to answer. I’ve edited my answer to hopefully be clearer about this.  

---

