Quantum Games

Science News, Nov 20, 1999 by Ivars Peterson

So, if Deep Blue comes out of retirement someday, it might face a newfangled quantum computer and quite possibly a crushing defeat.

The results would be even more dramatically one-sided if a player were to stack the quantum deck. Such a surreptitious act could change a game of chance into one he or she can't lose.

Say the Starship Enterprise faces a dire emergency, and Captain Picard is preparing for the worst. Suddenly, Q appears on the scene. This all-powerful but malevolent being offers to help, provided that Picard can beat him at a childishly simple game involving a penny.

The adversaries start with a closed box containing a penny, heads up. Neither can see into the box at any time. Hiding his action from Picard, Q either flips over the box (and the penny) or leaves it as it is. Picard then takes a turn, after which Q gets a final chance. Q wins if the penny is heads up when the adversaries together open the box.

Q's penny-flip challenge is an example of a two-person, zero-sum game: What one player gains, the other loses.

Applying standard game theory, Picard figures that his chances of winning the game are 50:50. He agrees to play--but loses to Q, not just once but again and again.

Meyer invented this Star Trek scenario for his article in the Feb. 1 PHYSICAL REVIEW LETTERS. It illustrates what would happen if one player takes advantage of a quantum strategy and the other doesn't.

Picard doesn't know that the penny in question is a quantum coin--an object that can be both heads and tails at the same time. Q does, so he performs a quantum flip on the penny. Instead of swapping tails for heads, this particular move leaves the coin in a superposition of the two states, halt heads and half tails.

On his turn, Picard responds with a standard flip or does nothing. Neither choice, however, alters the penny's mixed state. Q then does another quantum move that unscrambles the superposition, bringing the coin back to heads to win the game.

The key to Q's success is that he has access to quantum moves unavailable to Picard, Meyer says. A quantum computer should have a similar advantage over a conventional computer.

Researchers are now looking closely at the sorts of problems that stump standard mathematical methods but can be solved efficiently by algorithms that take full advantage of quantum effects. So far, they've identified only a handful of such algorithms, including a method for factoring whole numbers (SN: 5/14/94, p. 308) and Grover's quantum-search technique.

A game-theory perspective may suggest new possibilities for efficient quantum algorithms, Meyer says. Meanwhile, he's looking for other games in which quantum strategies potentially offer an advantage.

It's also possible to imagine a quantum game with quantum players, in which everyone wins.

Consider the game called the Prisoners' Dilemma, which has been the subject of thousands of experiments and theoretical investigations in social science, psychology, and economics since it was invented in the early 1950s.