9

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 Answers1

12

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.

kludg
  • 3,204
  • 9
  • 18
  • 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? –  Feb 23 '20 at 18:59
  • Does one need to understand quantum field theory to program in quantum computers? –  Feb 23 '20 at 19:00
  • 3
    To obtain quantum speedup we need different algorithms, having no classical analogs. – kludg Feb 23 '20 at 19:01
  • These quantum algorithms cannot be implemented on classical computers, right? Are there algorithms that are slow on a classical computer relative to other algorithms, but fast on a quantum computer relative to the same compared algorithms? –  Feb 23 '20 at 19:03
  • QFT? Definitely not, but quantum information science is very useful. – kludg Feb 23 '20 at 19:03
  • Does the theory of computation need to be changed as a result of quantum computing? I mean like algorithmic complexity. –  Feb 23 '20 at 19:04
  • 5
    "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 – poncho Feb 24 '20 at 04:38
  • 1
    @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 – glS Feb 24 '20 at 10:44