Are there schemes for encrypting classical ciphertext using quantum algorithms? Specifically, if a public key system exists for classical data, and classical ciphertexts, can this scheme be implemented by quantum algorithms (A quantum algorithm implementing classical public key algorithms)?

  • 1
    $\begingroup$ What are Quantum algorithm for you ? $\endgroup$ – Biv Apr 20 '18 at 8:26
  • $\begingroup$ Any kind, Shors' algorithm, Grovers search(if usable in such a scheme), BB84 key scheme, or even adiabatic quantum algorithms that implement a public key encryption scheme. $\endgroup$ – user3483902 Apr 20 '18 at 8:45
  • 3
    $\begingroup$ As a quantum computer can simulate any classical computer in polynomial time, a quantum computer can perform all classical public key encryption schemes. $\endgroup$ – SEJPM Apr 20 '18 at 10:06
  • 1
    $\begingroup$ There's a more interesting question potentially lurking here, which may or may not be what you meant to ask: Are there cryptosystems that can be efficiently implemented by a quantum computer (measured in qubits and qubit operations, under the premise that they some day become efficiently implementable), but not by a classical computer (measured in bits and bit operations)? $\endgroup$ – Squeamish Ossifrage May 7 '18 at 22:13
  • $\begingroup$ Given space available, the question, simply put firstly - before efficiency , and robustness of qubit operations come into play, is that of whether any scheme that of public key, or private key, or hashing based, can any of them be implemented on a qubit based quantum cryptosystem, measured in qubits, and qubit operations? $\endgroup$ – user3483902 May 8 '18 at 4:07

Yes, a quantum computer can implement any classical algorithm.

This can be easily proven, because quantum computers are Turing-complete. And if a computer is Turing complete then it can, by definition, run any classical algorithm:

A universal Turing machine can be used to simulate any Turing machine and by extension the computational aspects of any possible real-world computer.

And that's - as far as I can see - QED.

| improve this answer | |
  • $\begingroup$ This is a bit of a cop out. Presumably the question is about algorithms that couldn't run just as well on a classical computer! For example, imagine an algorithm that somehow uses Shor's algorithm as a subroutine. $\endgroup$ – Squeamish Ossifrage May 7 '18 at 21:46
  • $\begingroup$ @SqueamishOssifrage If it was about speeding up classical algorithms then the question should have stated that. The only question I can see is if classical algorithms can be run on a quantum computer and this does answer this. If the answer is not complete then the user is free to comment. And you are of course free to supply your own answer, ask for clarifications to the author or indeed ask a new question. The word "specifically" (i.e. specifying the question further) followed by "can this scheme be implemented by quantum algorithms" doesn't leave that much room IMHO. $\endgroup$ – Maarten Bodewes May 7 '18 at 22:09

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.