-2
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Oct 19 '17 at 19:06
  • $\begingroup$ @SashoNikolov yes, exactly, this is what I mean. $\endgroup$ – XL _At_Here_There Oct 20 '17 at 8:14
  • $\begingroup$ @XL_at_China Wouldn't that by very definition contradict the idea of "quantum supremacy"? (Which is a currently wide open question) $\endgroup$ – Clement C. Oct 20 '17 at 17:50
  • $\begingroup$ @ClementC. yes, I think so, because, Quantum computation does not reduce the computational complexity actually. NPC is still NPC $\endgroup$ – XL _At_Here_There Oct 21 '17 at 2:09
  • $\begingroup$ So then you are conjecturing that BQP is contained in BPP. This is unknown and, afaik, is widely believed to be false. $\endgroup$ – Sasho Nikolov Oct 22 '17 at 21:17
0
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – XL _At_Here_There Oct 19 '17 at 13:02
  • 4
    $\begingroup$ @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. $\endgroup$ – Stella Biderman Oct 19 '17 at 13:24
  • $\begingroup$ I think there must be an relation between them, in other word, quantum algorithm implies classic algorithm, but they are not same. $\endgroup$ – XL _At_Here_There Oct 20 '17 at 8:16
  • $\begingroup$ @XL_at_China That is the question I was trying to answer. I’ve edited my answer to hopefully be clearer about this. $\endgroup$ – Stella Biderman Oct 22 '17 at 12:28

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.