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…

Comments

  1. #1 Jonnan
    Indiana
    October 16, 2012

    I think you forget something fundamental – some of the problems quantum physics is good for (Pathfinding for example) are useful in games.

    I thoroughly believe the difference between a quantum chip too expensive for anyone’s practical use and mass production will be faster than you imagine because nothing is more irritating than escorting an NPC across the map in orc country and watching them continually try to go between two rocks they can’t fit through.

  2. #2 Chad Orzel
    October 16, 2012

    I thoroughly believe the difference between a quantum chip too expensive for anyone’s practical use and mass production will be faster than you imagine because nothing is more irritating than escorting an NPC across the map in orc country and watching them continually try to go between two rocks they can’t fit through.

    That sounds like the starting point for a Cory Doctorow story.

  3. #3 John H
    October 16, 2012

    Chad – many of the things we do come down to database searches. Even spam filtering employs databases. It’s such a ubiquitous technique that faster searches alone would almost certainly drive wide adoption of QC, if it enables them. Of course the cost / benefit of using it will determine where and how, but predictions about it’s utility at this point seem a bit sketchy. Rarely do the creators of new information technology correctly predict how it will end up being employed.

  4. #4 William Hyde
    October 16, 2012

    The “Complete book of Chess” by Horowitz and Rothenberg contains a number of composed positions in which having a queen loses, but having another piece, even a pawn, wins.

    Long ago someone composed a position for gambling purposes. While one side seems to be winning handily, the other side, by promoting to a knight, can mate in three. True, only the very gullible would not smell a rat here, but apparently there was no shortage of such.

  5. #5 ToSeek
    October 16, 2012

    There’s actually an example of successful underpromotion between two top grandmasters just last month:

    http://scienceblogs.com/evolutionblog/2012/09/10/underpromotion/

    P.S. And you didn’t offer a solution to the problem at the top! I’m thinking Qf1, but I’m not positive.

  6. #6 proximity1
    October 17, 2012

    W Pawn 2b –> 3b, B King in check, W Queen sacrificed.

  7. #7 proximity1
    October 17, 2012

    OOoops. That ought to have read B Queen sacrificed.

  8. #8 ToSeek
    October 17, 2012

    “W Pawn 2b –> 3b”

    That’s not a legal move since it exposes the White King to the Black Queen.

  9. #9 MPL
    October 17, 2012

    @JohnH

    Grover’s algorithm only gives a significant speed up to unordered databases, which doesn’t reflect most (well designed) queries. Even if you do have an unordered database, loading it into memory is O(n), so you might as well just do it the slow way.

    On the other hand, it would be great for inverting arbitrary functions, which is also a ubiquitous problem.

  10. #10 proximity1
    October 18, 2012

    RE :
    ToSeek @ October 17, 10:15 pm

    That’s not a legal move (i.e. : “W Pawn 2b –> 3b” ) since it exposes the White King to the Black Queen.”

    Uh, as I read it, you have the pieces incorrectly identified. If I’m not mistaken, the “King” is the black piece @ 5e and the Queen, (White) is at 1a. That means the move, “W Pawn 2b –> 3b” indeed “exposes” one of those pieces to the other–that is the whole point: to put the Black King in check.

    Until proof to the contrary.

  11. #11 Rick Pikul
    October 18, 2012

    @proximity1:

    You are mistaken. The ‘crown with cross’ is the king and the ‘multipoint crown’ is the queen.

    http://en.wikipedia.org/wiki/Chess_piece

  12. #12 proximity1
    October 19, 2012

    “to seek” & Rick:

    Thank you for the correction; in that case, I think I’d recommend 4c –> 6a, the White Queen taking the Black Castle. This assumes that the other pieces are pawns, not Bishops. But, if they’re Bishops, then I’d have reconsider.

  13. #13 ToSeek
    October 19, 2012

    Um, that’s a pawn at 6a. The black rook/castle is at 7e.

  14. #14 Eric Lund
    October 19, 2012

    1 Qf1 as suggested above is correct. The threat is 2 Qf8 for checkmate. Black’s best response is 1 … Qg7, after which White plays 2 Ra8+ Qg8 3 Rxg8+ Kxg8 exchanging his rook for Black’s queen. The other possible Black responses are to push the h pawn, resulting in 2 Qf8+ Kh7 3 Rxe7+ Qxe7 4 Qxe7+ netting a free queen for White; 1 … Qb2 Rxe7 which is a free rook for White; or 1 … Re8 2 Qf7 and Black cannot defend against both 3 Qg7 and 3 Qxh7, both of which are mate.

  15. #15 ToSeek
    October 19, 2012

    I ran this through a chess program on my iPad, and it went with:
    1. Qc8+ Kg7
    2. Qe8!
    Black at best loses his queen for White’s rook and a pawn:
    2 … Qb2+
    3 Kxb2 Rxa7

    The only other choice is:
    1 Qc8+ Re8
    2. Qb7
    Threatens mate with Qxh7 or Qg7. The only saving move is
    2. … Qe7
    which leaves black with one pawn against white’s rook and two pawns.

    In response to Qf1, the program prefers Kg8 to Qg7.

  16. #16 rlaing
    November 9, 2012

    I like Qb4. Mate is threatened if the Rook moves, and the King can’t get there fast enough to provide a second defender.

  17. #17 rlaing
    November 9, 2012

    And if the rook moves to e8, Qf7 takes over the 7th rank, and black’s situation is hopeless.

  18. #18 rlaing
    November 9, 2012

    Rats. Black can defend himself Rg7. No, it looks like ToSeek iPad has the best idea.