Last but not least, we will talk about the famous Grover's algorithm.
This algorithm is, indeed, famous for two reasons: it finds a labeled item in an unstructured database faster than any classical algorithm, but (and this is the second reason why it is famous) not faster enough. It gives only a quadratic advantage (more or less, it is "something to the power two" faster than a classical algorithm).
The detailed description of the algorithm itself is long, tricky and maybe not that interesting for our purposes, but briefly I can say that in Grover's algorithm a series of rotations are applied to your qubits in order to match the item in the database that you are searching for. Easy 馃槀
Now I want to clarify my previous statement about how fast this algorithm reaches a solution.
I told you in the previous post how much faster, than any classical algorithm, Shor's algorithm is solving the factoring problem: it gives an exponential speed-up! And it shows the power of quantum computing respect to the classical one.
On the other hand, Grover's algorithm (by giving only a quadratic speed-up) is showing the limits of quantum computing: Quantum Computation is not a magical approach that can solve all the problems in an incredibly faster way.
Up to now, we know that with a quantum computer you may solve a wide class of problems very efficiently, but for other problems the speed-up is very limited.
An additional note about blockchain technologies: Grover's algorithm could be used for mining purposes in Proof of Work systems (for example Bitcoin is using it).
You may think the cryptographical puzzle to mine a new block as the problem of finding the inverse of the one-way hashing function. Hence, to find a nonce, such that a given hash is accepted as block's hash.
This leads to a consideration. A pool of powerful enough quantum computers may monopolise the mining process of a blockchain and even, in extreme cases, rewrite the history of the blockchain itself!
"How?" you may ask. It may happen because the speed-up is only quadratic, true, but it would be enough to do the following: imagine the already said pool of quantum computers and suppose that their are malicious. They may pick a point in the blockchain, then they start a fork from that point, and they may build a completely legit (but controlled only by them) new chain that would overcome the true legit chain (the one where honest miners where working).
Yes, it would be the collapse of all the system.
Don't worry, this would not happen soon. Plus, it seems that blockchains are orienting their efforts in developing Proof of Stake protocols, that would help in solving this possibility.
That's all for today!
And that's all for this series, too.
I hope you enjoyed this easygoing excursion in the quantum world, hoping to see you again.
@maar to stay updated and to know more about the fascinating world of Quantum Information and Computation!