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 1


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$
    – user10151
    Commented Feb 23, 2020 at 18:59
  • $\begingroup$ Does one need to understand quantum field theory to program in quantum computers? $\endgroup$
    – user10151
    Commented Feb 23, 2020 at 19:00
  • 3
    $\begingroup$ To obtain quantum speedup we need different algorithms, having no classical analogs. $\endgroup$
    – kludg
    Commented Feb 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$
    – poncho
    Commented Feb 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
    Commented Feb 24, 2020 at 10:44

Your Answer

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