What Sorts Of Problems Are Quantum Computers Good For?

A couple of weeks ago, the APS’s Physics ran a piece titled Traveling with a Quantum Salesman, about a quantum computing approach to the famous “Traveling Salesman” problem. I saw the headline, and immediately thought “Oh, yeah, of course that would be a good problem for a quantum computer…” The paper in question is far enough from my core expertise that I can’t really do better than the original Physics piece in terms of explaining what the researchers did and why it matters. My reaction to it, though, seems like a useful jumping-off point for a post correcting some misconceptions about how quantum computers really work, and what they’re good for. Justin Trudeau, Canada’s prime minister, gestures as he speaks during a panel session at the World Economic Forum. Photographer: Matthew Lloyd/Bloomberg. The most common non-technical way to explain quantum computers is to talk in terms of added power from having the ability to put bits in superposition states. Or, as the Prime Minister of Canada famously put it:

Normal computers work, either there’s power going through a wire or not. It’s 1 or a 0. They’re binary systems. What quantum states allow for is much more complex information to be encoded into a single bit. A regular computer bit is either a 1 or 0—on or off. A quantum state can be much more complex than that because as we know, things can be both particle and wave at the same time and the uncertainty around quantum states allows us to encode more information into a much smaller computer. That’s what exciting about quantum computing.

That’s not a terrible explanation, and even experts in the field, asked to match Trudeau’s explanation mostly resort to variations of this: a classical bit is either “0” or “1,” but a qubit can be an arbitrary superposition of “0” and “1,” which dramatically increases your options when calculating stuff. It’s not the whole story, though, and leaves many people with the impression that quantum computers are a logical means of extending “Moore’s Law” to continue making more powerful computers once we hit physical limits on classical chips. In fact, even when quantum computers are finally built, they’re likely to remain highly specialized instruments, for the simple reason that they really only offer an advantage for certain special kinds of problems. Why is that? Well, you can get some sense of the reason from one of the answers in that Maclean’s piece, from quantum computing theorist (and physics blogger) Scott Aaronson:

A quantum computer is a proposed device that exploits quantum mechanics to solve certain specific problems like factoring huge numbers much faster than we know how to solve them with any existing computer. Quantum mechanics has been the basic framework of physics since the 1920s. It’s a generalization of the rules of probability themselves. From day to day life, you’d never talk about a minus-20 per cent chance of something happening, but quantum mechanics is based on numbers called amplitudes, which can be positive or negative or even complex numbers. The goal in quantum computing is to choreograph things so that some paths leading to a wrong answer have positive amplitudes and others have negative amplitudes, so on the whole they cancel out and the wrong answer is not observed.

That’s maybe not as smooth as Trudeau’s explanation– it introduces some jargon terms, and seems to take a weird turn halfway through (though it makes sense by the end)– but it’s a more correct and complete explanation. And, more importantly, it points to why quantum computers are definitively better than classical computers for only a limited set of problems. Waves coming together in complicated ways. The key fact that Aaronson brings out, that’s often hidden by talk about qubits in superposition states, is that quantum computers are all about waves and probability. That’s fundamentally what lets your qubits be in a superposition in the first place– what you can predict is a probability of finding a particular outcome, and that probability comes from amplitudes that have wave-like properties and aren’t confined to a single state. So, in a sense, quantum computing is properly understood as a process of engineering the pattern of a complex set of waves, in hopes of channeling the flow toward the correct answer. Of course, this is vastly complicated by the fact that we generally don’t know what the answer is in advance, so it’s not just a simple matter of laying out a single channel, but trying to stir up a set of waves in the open ocean that somehow all come together to make one big splash. See the original article here

Advertisements

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