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.


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy