I recently saw an article at phys org that did some sort of "quantum simulation" on a conventional computer to calculate prime probabilities, the article (and paper associated) does mention shor's as well.

What threat does this model pose to current cryptography?




1 Answer 1


What threat does this model pose to current cryptography?

Do you mean "what threat does their algorithm run on a quantum simulator pose to cryptography"?

If so, the answer is "none". Yes, there exist Quantum Simulators (which run on classical computers), that can run Quantum Algorithms. However simulating $n$ entangled states requires $O(2^n)$ memory and time, and so a Quantum Algorithm that runs in polynomial time on a real Quantum Computer would make the simulator take exponential time; we already can factor faster than that on a classical computer.

These simulators are useful in studying what a real (that is, reliable) Quantum Computer could do, once it is built; they are not particularly useful in actually solving problems.

On the other hand, if the question is "they have a new Quantum Algorithm for factoring; what threat does that pose, once we have a real Quantum Computer?"

The answer to that is "not much more than what is known now". We already have Shor's algorithm, which can factor in polynomial time. Their algorithm might run faster (or with less qubits or other resources), and hence be somewhat more practical. However with Shor's algorithm, anything that relies on the difficulty of factoring is assumed to be already broken - this algorithm would (at best) make it a bit more broken.

As an aside, of the commonly used public key cryptosystems, only RSA and Pallier rely on the difficulty of factorization. Shor's algorithm also addresses the discrete log problems (and so also covers DH and ECC); they don't mention whether their new algorithm can be used to attack those problems.


Your Answer

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

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