It is widely claimed, without any hesitation or disclaimer, that quantum computers (QC) can (or well, will be soon able to) break cryptography by factorizing large numbers. However, to my knowledge, largest number ever factorized by a quantum computer is 21 (= 7 x 3) for Shors algorithm, and to make things worse, this world record hasn't been improved for a whole decade!
Some larger numbers were factorized too, but not like "give me a number and I will factorize it". Rather, it was done by starting from a known solutuion and figuring out if this particular case could be programmed in to the QC - which is basically cheating, or at least not a useful factorization process.
So what is stopping the game? What are the factors that limit the size (measured in number of bits) of an arbitrary numer that can be factorized by a QC? Are they just a technologic annoyance or is there a fundamental obstacle that invalidades QC from ever factoring large numbers?
There’s no limit, in principle, any more than there’s any such limit for any ``classical" computer.
The issue is practical, not theoretical. Current ``quantum computers" can not realize, in practice, any unitary evolution operator, that’s all.
For ``breaking cryptography", for the near future, networks of conventional computers and social engineering (length of passwords) will remain more relevant; and social conventions will be more relevant for enforcing applications of cryptography.
Stam Nicolis Please eleaborate on the unitarity argument.
Second question: does factorizing a 50 bit number imply entanglement of 50 qubits at some point in calculation?
Quantum computers work with quantum gates, just like classical computers work with classical gates. In both cases the gates are ``logical''-their material implementation just respects the logic.
For classical computers it's known how to design logical circuits that can realize any computation-and how to construct real circuits that implement this; for quantum computers this isn't, yet, known at comparable level of detail.
Factoring a number means two things: (a) Deciding whether it's a prime or not; and, (b) Determining its factors. The two problems are, actually, independent, since it is possible to solve (a), without solving (b)-of course, solving (b) provides an answer to (a).
What was realized, before quantum algorithms were even imagined, was that it was possible to define the probability that, given a number N, another number, a, could be one of its factors. This led to classical factoring algorithms and quantum algorithms.
With 50 bits one can represent all integers from 0 to 250-1. So any such integer is a string of 50 bits. So it's necessary to translate the statements of problems (a) and (b) into operators on such strings. It might be useful to start with smaller numbers, to understand how things work. Shor's algorithm is presented here: https://en.wikipedia.org/wiki/Shor%27s_algorithm and this might be a good place to start. It solves problem (b) by realizing a way for computing the probability that some number is, or not, a factor of the number one wants to factor.
In general, the bits will be entangled, of course.
- Badges
- Science topic