[Link] Understanding quantum computing through random walks

This article on Stack Oveflow has a nice metaphor to understand intuitively why quantum computing is fundamentally different than classic computation and much more powerful for some classes of problems:

Understanding quantum computing through drunken walks

A drunken walk in classic computing is basically a random walk: drunkards move to either the left or the right with equal probability and they tend to dispose themselves into a bell shaped curve.

But a quantum drunk is following a path that is a superposition of left and right: will go to left and right simultaneously and they tend to dispose into a “fangs” shaped curve (check the two curves in the article)

The quantum drunk has new properties. 

The drunkard tends to be farther away, and it is less likely to be close to the center.  Certain paths are less probable because of interference, while some are more probable. The overall spread is much different too.

Put in a labyrinth the quantum drunks can exit quicker:

Remember that the classical drunk is going to be flipping a coin at every node, whereas the quantum drunk is creating a superposition of every path at each node. The drunks tend to get stuck in the random connections in the middle, taking more time to find their way out. 
Since quantum drunks are more spread out, they can escape being stuck easier. This is why quantum drunks find the exit faster than classical drunks. 
For this problem as we send more and more drunks through, the quantum ones are going to make it through exponentially more than the classical ones! This is the power of quantum computing. Even though this is a simple example, all quantum algorithms work the same way: by exploiting the quantum spread in clever ways that fit the structure of a problem.

Check the original article for more details.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s