Quantum Computing and Chess Problems

In which I steal an analogy from Joe Emerson to explain the limits of quantum computing.

------------

As previously noted, a couple of weeks ago I went to Canada for the opening of the University of Waterloo's new Quantum Nano Center (their photo gallery includes one picture of me being interviewed, along with lots of more interesting pictures from the day). One of my events there was a panel discussion about the new center and what it will mean, which included me, Raymond Laflamme, the director of the Institute for Quantum Computing, and Mike Lazaridis, the founder of Research in Motion, who gave the university the money for the center.

The last question asked of the panel was to imagine what great breakthroughs might be celebrated at the 50th anniversary of the center's opening in 2062. I had to go first, and said that while I think it highly unlikely that people in the future will be using quantum computers on a daily basis, connecting to the quantum internet to receive quantum spam from evil squirrels in Nigeria, the development of quantum computing might enable new breakthroughs based on simulations of inherently quantum systems that are hard to handle with a classical computer. I'm not entirely sure what those might be, but I threw out high-temperature superconductivity as a possibility, because why not?

I thought that was a reasonable and measured answer. Ray Laflamme was next, and said "I want to be quantum teleported!" Thus making me look like a boring stick in the mud. Sigh.

Mike Lazaridis teased me about that a bit after the panel, but you know, I'm an experimentalist by training. I'm not very good with wild flights of fantasy, but prefer to keep my speculations grounded in reality. And the fact is, it's not clear that quantum computers will ever be all that widely useful-- while Moore's Law gets invoked a lot in discussions of what quantum computing means, it's not useful for everything. A quantum computer can do certain types of problems much faster than a classical computer, but for lots of other problems, it's no faster than a classical computer, and in fact the overhead required to maintain the quantum-ness of the computation probably means it would run more slowly than a classical computer.

Later that night, I had dinner with Joe Emerson from the IQC, who used an analogy that I really like, and thus will totally steal. He made an analogy between computational problems and chess problems, the sort of thing shown at the top of this post-- White has a rook and three pawns, Black has a kinght and a bishop, White to checkmate in four moves. You can think of a lot of computational approaches as being like the search for the minimum possible number of moves to win the game-- there's probably a way for White to win in six moves that's easy to see, but with a bit more work, you can find a four-move solution.

Quantum computing brings a powerful new resource into play for these problems-- the ability to use quantum superposition and entanglement in the course of the computation. This is sort of like replacing one of the pawns in the chess problem with a queen, the most powerful of the chess pieces (in some sense, anyway).

Now, for a lot of chess problems, replacing a pawn with a queen will make a huge difference, and might enable you to win in two moves, rather than four. But for a lot of other chess problems, adding the queen might not make any difference. There are even some where adding the queen would slow things down-- once, long ago, when dinosaurs roamed the Earth and I played chess regularly, I saw one where promoting a pawn to a queen actually made things worse. In order to win that particular game, you needed to promote the pawn not to a queen, but to some other piece-- a knight, I think it was.

Quantum computing is the same way. For certain types of problems-- factoring large numbers, or database searching-- you can get a big speedup over classical algorithms. The quantum computation for these problems requires fewer steps than the classical version, and thus will run faster, given two computers with a fixed operating rate.

Other types of problems, though, don't run any faster on a quantum computer than a classical one. These include most of the things we routinely use computers for. And given the fragility of quantum systems, the operation rate for a quantum computer is likely to be slower than a classical computer for a long, long time, due to the things you need to do to protect the quantum nature of the systems you use as qubits. That's why I say we're unlikely to ever use quantum computers to filter quantum spam-- the extra overhead just isn't worth the bother.

A big part of quantum computing research lies in trying to figure out which problems benefit from quantum approaches, and how much you can win. The list of known quantum algorithms is not terribly long, and more probably remain to be found. Tracing out the boundaries that separate those from the problems that don't improve with quantum computing is an important area of activity.

So, that's how chess explains why I don't expect quantum computers to be in general use fifty years from now. If a technique is developed to make large-ish quantum computers feasible-- something that this year's Nobel laureates have worked toward-- we may very well have a world someday where specialized quantum modules are coupled with ordinary classical computers to solve those problems where quantum techniques are truly beneficial. But I don't think that quantum mechanics really represents a solution to the problem of extending Moore's Law for general purpose computing. I'd be happy to be proved wrong, though...