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$ – Numbers Feb 23 at 18:59
  • $\begingroup$ Does one need to understand quantum field theory to program in quantum computers? $\endgroup$ – Numbers 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

Not the answer you're looking for? Browse other questions tagged or ask your own question.