Quantum computers explained so simply even I can understand

Although I am physicist, I don’t have much to do with quantum mechanics. I teach elementary bits of it here and there, which is fun, but I do research on classical systems, so I don’t have a particularly good grasp of quantum stuff. So although I occasionally see some of the hype, and controversy, over quantum computers, I have not really understood what they actually are. But recently, I came across the blog of Scott Aaronson, a scientist in the field who, I think, explains it really well.

In particular, I guess I had some vague idea that if we could crack the problem of actually making a quantum computer with more than a handful of bits (called qubits), that this would somehow magically be faster than computers, like my laptop, that run on classical principles.

This is not so, people like Aaronson and many others are still working on what quantum computers can and cannot do, but it appears that they are much faster only for a relatively small set of problems. These include important practical problems like breaking a large number into its factor (i.e., breaking up 40 into 5*4*2, only for much bigger numbers). But they don’t include the toughest problems, like the travelling salesman problem.

This is the problem of a salesman needing to visit N cities, and wanting the shortest route between these N cities. The total number of routes increases as N!, which increases exponentially fast with N. The number of routes gets crazy big fast, for example for N=50 cities, this are already more than a trillion trillion trillion trillion trillion routes. No existing computer can deal with this many routes, and it may be that building quantum computers will not help us here.

For this interesting point, and a lot more, explained very clearly, there is an article by Aaronson here.

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 )

Google+ photo

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

Connecting to %s