Would we need to create new algorithms that only work on quantum computers or would be simply edit codes in languages such as C++ to involve the new primitives from quantum computing? Are there things that can be programmed on a classical computer that can’t be programmed ona. Quantum computer? I know that quantum computer are turing complete.
1 Answer
$\begingroup$
$\endgroup$
8
Short answer: no. Any classical algorithm can be transformed into quantum algorithm. This result has little practical value, because you don't obtain quantum speedup, but it is important from theoretical point of view.
-
$\begingroup$ So to take advantage of quantum computing’a speed up, we can’t simply translate classical algorithms to quantum language? We need to rethink how we create the algorithms? $\endgroup$– user10151Feb 23, 2020 at 18:59
-
$\begingroup$ Does one need to understand quantum field theory to program in quantum computers? $\endgroup$– user10151Feb 23, 2020 at 19:00
-
3$\begingroup$ To obtain quantum speedup we need different algorithms, having no classical analogs. $\endgroup$– kludgFeb 23, 2020 at 19:01
-
5$\begingroup$ "These quantum algorithms cannot be implemented on classical computers, right?" That is incorrect; a classical computer can simulate a quantum computer (and that simulation can run any quantum algorithm) - the kicker is that the simulation runs in time exponential in the quantum state size $\endgroup$– ponchoFeb 24, 2020 at 4:38
-
1$\begingroup$ @Numbers "Does the theory of computation need to be changed as a result of quantum computing? I mean like algorithmic complexity" see quantum computational complexity $\endgroup$– glS ♦Feb 24, 2020 at 10:44