We are here, at last! The powerful Shor's algorithm!
I am confident that, at the end of this post, you will understand my excitement about this algorithm, especially if you are afraid of any quantum hacker trying to steal your assets!
In the following I will try to convince you that if today we are talking about quantum computers, it is because of this "simple" algorithm.
In extreme synthesis, Shor's algorithm would allow (with the proper quantum computer, whenever one powerful enough will be built) to break all the cryptographical keys that are nowadays "securing" our lives: bank accounts, cryptocurrency wallets, social media, etc. basically everything that is secured by a password would be vulnerable.
The strength of this protocol is in the superposition of states: it is like the algorithm could evaluate a function in multiple points in the same instance, finding the required value for the purpose.
What is important, it is to point out that there exist classical algorithms addressing the same problem (factorization of large integers, discrete logarithm, and similar problems belonging to the hidden subgroup problems), but they are solving this kind of problems in a time soooooo large, that it is almost unfeasible.
Yet, you know about hacking and cryptographical keys breaching, but a quantum computer (with enough qubits) would solve the same problem in exponentially less time.
To understand roughly the difference: while a classical computer may need decades for factorising a large integer, a quantum computer would only need minutes.
Shor's discovery rephrased completely our perception of computational complexity: now we are able, theoretically, to solve hard problems in a reasonable amount of time, and it is pushing all the research towards quantum-secure cryptosystems and the physical/technical development of quantum computers themselves.
Indeed, nowadays Shor's algorithm is not "that useful".
Up to now, researchers have experimentally factorised numbers with only two digits (i.e. n<100), because to build a large quantum computer is an extremely difficult task from an experimental, technical and technological point of view...we are expecting a vast, huge, increase of quantum computers' power in the next 5-10 years, but for now your personal data and accounts are safe (from a quantum attack, at least).
That's all for today!
Stay tuned and see you in the next post! In the last post we will meet the GROVER'S ALGORITHM!
@maar to stay updated and to know more about the fascinating world of Quantum Information and Computation!