Quantum Games

Science News, Nov 20, 1999 by Ivars Peterson

Taking advantage of quantum effects to attain a winning edge

Over a chessboard or in a diplomatic conference room, players strive for even the slightest advantage that would tilt a game's outcome in their favor. Reasoning, bullying, bluffing, and cheating can all come into play in the search for a winning strategy.

Game theory offers mathematical tools for analyzing simple games. Originally formulated in the 1940s, it provides a framework for deciding who wins under various circumstances and suggests optimal strategies for achieving certain ends.

Because researchers can interpret many human activities in terms of games, they've applied game theory to important issues in fields such as economics (SN: 3/28/98, p. 205), international relations (SN: 5/4/96, p. 284), and computer science and artificial intelligence (SN: 7/18/98, p. 40).

Until recently, however, the realm of games appeared far removed from the domain of physics and quantum mechanics, which governs the interactions of atoms and electrons. Now, theorists are poised to exploit peculiarities of quantum behavior to work out novel strategies for winning games.

It's like having a quantum penny, says mathematician David A. Meyer of the University of California, San Diego. An ordinary penny comes up either heads or tails. A quantum penny has the additional property that it can be put into a state that mixes both heads and tails.

The extra possibility of a mixed state permits quantum-game strategies that can theoretically be more successful than conventional ones in various games, Meyer contends.

In the light of quantum theory, coin tossing, chess, and perhaps even international negotiations take on a startling, new dimension. In some cases, using a hypothetical quantum computer in place of a conventional one should speed up searches to identify a winning strategy. In other instances, quantum logic changes the game itself.

Computers play a mean, brute-force style of chess. When chess computer Deep Blue triumphed over world champion Garry Kasparov in 1997, it relied heavily on extensive searches (SN: 5/17/97, p. 300). For a given arrangement of chess pieces, the computer simply looked ahead a fixed number of moves, evaluated the strength of each move, and selected the best one.

In principle, a chess computer can foresee a game's end by checking each possible path to its outcome. It can then choose an appropriate sequence of moves to ensure a win, maintain a draw, or delay a loss. In a game of 40 moves, however, the number of different board positions that can develop exceeds [10.sup.120]. There's no way even the fastest conventional computer can check every possibility to play a perfect game.

That's where quantum computers would help.

Ordinary computers rely on vast arrays of tiny transistors, arranged in logic units called gates, to perform their calculations. They typically use the presence or absence of certain amounts of electric charge to represent the 0s and 1s of a computer's binary code.

The hypothetical quantum computer replaces the 0s and 1s with entities called quantum bits, or qubits. Each qubit is encoded as a quantum state--a particular energy level of an atom, for instance. One energy level would correspond to the 0 state and another, to the 1 state. Unlike an ordinary bit, however, a qubit can also exist as a combination, or superposition, of those two states.

Computer scientists can, in principle, take advantage of superposition and the wavelike nature of quantum particles. They would set up calculations so that computational paths yielding undesirable results cancel each other out, while computational paths leading to the answer reinforce each other (SN: 1/14/95, p. 30). In effect, quantum interference allows them to zero in quickly on the relevant result.

In 1996, Lov K. Grover of Lucent Technologies' Bell Labs in Murray Hill, N.J., invented a quantum-based procedure that would significantly speed up searches of an unsorted list to find a desired item (SN: 8/31/96, p. 143).

Grover's search algorithm can itself be thought of as a kind of game, Meyer remarks. As in the game of 20 questions, which calls for "yes" or "no" answers to specific requests for information, Grover's procedure queries a database to learn whether one is on the right track to the answer.

David Deutsch and Artur Ekert of the University of Oxford in England have considered how a chess-playing quantum computer would use Grover's procedure. It could investigate a trillion possible continuations from a given position in the same number of steps as a conventional computer would need to check out a million. Quantum superposition allows the computer to cancel out a lot of unpromising possibilities that a conventional computer must look into one by one.

Several researchers, including Grover and Scott Aaronson of Cornell University, have investigated such potential improvements in performance. They discovered that the search speed-up in a game in which two players take turns looks especially promising it there is, at most, just one winning choice per move. Since then, Grover has generalized his quantum-search method to cover situations where there may be multiple solutions.