Introduction to Quantum Information: Part 7/7

in LeoFinance4 years ago

from https://bit.ly/3788MEy

GROVER'S ALGORITHM

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.


Follow @maar to stay updated and to know more about the fascinating world of Quantum Information and Computation!

from https://bit.ly/2HvG3ko

Sort:  

Congratulations @maar! You have completed the following achievement on the Hive blockchain and have been rewarded with new badge(s) :

You have been a buzzy bee and published a post every day of the week

You can view your badges on your board and compare yourself to others in the Ranking
If you no longer want to receive notifications, reply to this comment with the word STOP

To support your work, I also upvoted your post!

Do not miss the last post from @hivebuzz:

Saint-Nicolas challenge for well-behaved girls and boys
HiveFest⁵ badges available in the HiveBuzz shop
The new HiveFest⁵ Attendee badge is waiting for you

@maar, thank you for supporting the HiveBuzz project by voting for our witness.

Here Is a small present to show our gratitude
Click on the badge to view your Board of Honor.

Once again, thanks for your support!

Do not miss the last post from @hivebuzz:

Feedback from the January 1st Hive Power Up Day
Happy New Year - Project Activity Update