91av

IF YOU want to get ahead then you should stab your best mate in the back. At
least that’s what mathematicians would say. For decades they’ve studied simple
games in which players can either cooperate or turn against one another, and
they’ve found that logic often demands ruthless betrayal—even if it
sometimes means everyone loses.

But it doesn’t have to be that way. Spice up game theory with a dash of
quantum mechanics—the strange principles that govern the behaviour of
molecules, atoms and subatomic particles—and lose-lose contests can become
win-win. In a classical game, players must choose between cooperating and
betraying. But, paradoxically, quantum mechanics allows players to do both at
the same time. What’s more, a spooky quantum connection called entanglement
means each player’s choice can secretly affect everyone else’s.

All this weirdness can make players pull together, even as each strives to
get the best deal. “Even though you still behave rationally and selfishly, you
don’t end up in a nasty state,” says Simon Benjamin, a physicist at Oxford
University.

Such quantum games are not just esoteric exercises. They could form part of
the longed-for quantum technologies of tomorrow, such as ultra-fast quantum
computers. They might even help traders construct a crash-resistant stock
market. And quantum games could provide new insights into puzzling natural
phenomena such as high-temperature superconductivity.

To see why quantum mechanics changes things so much, consider one
version of a game called the Prisoners’ Dilemma. Suppose you and your gang
have been arrested for armed robbery. If you all stick together and stonewall
the police, you each get a couple of years in prison. But if you snitch on the
others, you go free while everyone else gets 20 years. And if everyone turns on
everyone else, you’ll all get sentences nearly as long as that. The precise
options and consequences can be spelled out in a “pay-off table” that displays
the sentences to be handed down for each possible combination of moves by you
and your accomplices.

Of course, you don’t need a mathematician to tell you that you’ll all
probably be banged up for a long time. Each of you will soon realise that, no
matter what the others do, you can improve your lot by betraying them. So
however much you talk it over, everyone will grass on everyone else.

But, Hayden and Benjamin say, this unpleasantness can be avoided if you play
the game quantum-mechanically. They studied a three-player Prisoners’ Dilemma
game where each player had a “qubit”. This is a quantum bit, rather like a
computer’s zero or one binary digit, but with an important difference: a qubit
can be in two different states at the same time.

That qubit might be a single electron whose tiny magnetic field can point
either “up” or “down”. Being quantum-mechanical, the electron can also be in a
“superposition” of these states, pointing both up and down at the same time. The
bizarre superposition of states is fragile and persists only until someone tries
to measure which way the particle’s field is actually pointing. When that
happens the superposition “collapses” to one or other of the states.

Benjamin and Hayden imagined that the three players start with their qubits
pointing down, representing their supposed solidarity—regardless of
whether they intend to stick together. They then allow their qubits to be
entangled. This creates a link between them and puts the group in a
superposition that will yield “all down” or “all up” if the qubits are measured.
Only one of the qubits needs to be measured: if one is found to be pointing up,
then entanglement means the other two instantaneously take on the “up” state,
even if they’ve been carted off to the other side of the prison.

With this entanglement in place, any moves the players make can change the
relationships observed when the qubits are measured. If, say, the first prisoner
flips, the entanglement means the qubits are then put into a superposition of
“one up, two down” and “one down, two up”.

Once the qubits are entangled, each player adjusts the state of their qubit
according to their intended tactics, either leaving it as it is to remain true
to the others, flipping it to betray them, or doing some combination of both at
the same time. Finally, the entangling procedure is reversed, and the jailers
measure the state of the qubits. If, as above, the first player flips and the
other two do nothing, then the measurement will show either the first player’s
electron pointing up and the other two pointing down, or theirs pointing down
and the other two pointing up.

Benjamin and Hayden used mathematical elbow grease and a bit of computer help
to examine the many possible combinations of states of the three prisoners’
qubits. The researchers then read off the prisoners’ sentences from the pay-off
table. If the final state of the three qubits was a superposition, then the
sentences were a weighted average of two or more outcomes from the table.

In the classical game, selfishness makes the players betray each other, no
matter how much they talk it over beforehand. All three go to jail for a long
time. They can do the same in the quantum game, although it would not be the
rational thing to do. They can do much better because superposition and
entanglement provide far more appealing outcomes. And no one player can improve
their own fate by changing their move alone. “The ultimate fates of the players
are entwined in a way that they’re not in a classical game,” Hayden says.

Short stretch

The three do best when one does nothing, another betrays, and the third
enters a half-and-half superposition. The prisoner who does nothing and the one
who betrays both receive light sentences, and the one who does the combination
goes free. Remarkably, even though the pay-off is not the same for all three
players, there is no better option for any one of them to take in this quantum
prison. So it’s just a matter of deciding who plays which move, perhaps by
drawing straws or cutting cards. Once that’s determined, everyone does best to
play along.

But while entanglement enforces a kind of unavoidable teamwork, it isn’t a
necessary ingredient of every quantum game. Indeed, you can gain huge advantages
from superposition alone, says David Meyer, a mathematician at the University of
California, San Diego. Meyer has devised a contest between two characters from
the television show Star Trek: The Next Generation.

In Meyer’s game, Captain Jean-Luc Picard and Q, the omnipotent alien, agree
to flip a coin to decide who gets control of the starship Enterprise. They put
the coin heads-up in a box into which neither can see. First Q reaches into the
box to manipulate the coin, then Picard reaches in to either flip it or leave it
as it is. Finally, Q manipulates the coin once more. They then open the box, and
if the coin shows tails, Picard wins.

Picard reckons his chances of winning are 50 per cent, so he’s not too
surprised when he loses the first game. But then he loses the second game, and
the third, and the fourth. In fact, he loses every time. That’s because they’re
playing with a quantum coin—and only Q knows it.

Q uses his first move to put the coin in a half-and-half superposition of
heads and tails. Picard then either leaves the coin alone or flips it. But
flipping the coin simply exchanges heads for tails and vice versa, leaving the
coin in the same heads-and-tails state, much as interchanging black and white
squares leaves a chequerboard a chequerboard. After Picard has made his
completely ineffectual move, Q simply performs the inverse of his first move.
This returns the coin to the original heads-up state.

Q can use his quantum powers to do more than win a coin-toss. He can use the
same principles to beat million-to-one odds. If Picard picks a number in a
specified range—say one to 1,000,000—Q can guess it every time as
long as Picard agrees to encode his choice in qubits that Q has already put into
a superposition, like his coin. The same routine of first making, then finally
undoing, a superposition of these qubits means that Picard will leave telltale
signs of his chosen number in the state of the qubits.

Meyer’s games may sound like entertaining but useless quantum parlour tricks,
but the lessons they teach us could be crucial in the emerging field of quantum
computing. Indeed, musings about the guess-a-number scenario have already helped
reveal a method for factoring very large numbers. This is the key step in
cracking coded messages, one of the major tasks awaiting these machines. And in
Meyer’s games, Picard can only make classical moves, while Q’s are quantum, so
their contests also resemble the interactions between a non-quantum human and a
quantum computer that can perform super-fast computations. Such games hint at
how best to program a quantum computer. “Thinking about specific games and
quantum strategies may lead to techniques for new quantum algorithms,” Meyer
says.

Moreover, Meyer’s games do not require the bits to be entangled, so they
might even help answer one of the fundamental questions in quantum computing: do
the qubits in a quantum computer have to be entangled for it to work at all?
“The pick-a-number game is certainly a counter-example to the statement that
quantum speed-up comes from entanglement,” he says.

Quantum moves don’t always improve a game’s outcome. It depends on how many
players are involved, and what they are allowed to do. Two years ago, Jens
Eisert of Imperial College, London, working with Martin Wilkens of the
University of Potsdam and Maciej Lewenstein of the University of Hanover,
pioneered the quantum approach to prisoner games. Using just two prisoners, they
showed that they could find a better solution to the dilemma than the
back-stabbing scenario if both played a particular quantum move.

But Eisert and colleagues did not allow for the full variety of
superpositions and entanglements that are possible in the quantum game. And
Benjamin and Hayden have shown that if more moves are allowed, then no matter
what the first prisoner does, the second prisoner can always make a move that
puts them in the clear and lands the other with the longest possible sentence.
“Anything you can do, I can undo, if there are just two qubits,” Benjamin says.
Of course, the first player can also undo whatever the second attempts. So in
the end neither player can anticipate what the other will do and there can be no
cooperation.

Even if quantum mechanics isn’t the answer to all such dilemmas, it could be
useful. Researchers are applying it to games that simulate evolution, stock
markets—and even game shows. Last year Adrian Flitney and Derek Abbott
from Adelaide University investigated a quantum version of the Monty Hall game
show. Here, a contestant called Bob chooses which of three doors he thinks is
hiding the prize, and then Monty Hall, the host, stirs up the odds by opening
one of the wrong doors and asking the contestant if he’d like to switch his
choice. Classically—and counterintuitively—Bob’s best bet is to
switch, but that still only gives him a 66 per cent chance of finding the prize.
If the contestant can use entanglement, however, he can win every time.

It’s hard to imagine a quantum game show ever making it to television,
despite the fact that Flitney and Abbott’s research was sponsored by the South
Australia Lotteries Commission and a major supplier of gaming equipment. But
other studies may prove surprisingly practical. For example, researchers are
developing methods to use photons as qubits to encode and transmit secret messages
(91av, 2 October 1999, p 28).
Meyer says you can think of such “quantum cryptography”
as a game played by the sender, the receiver and a would-be
spy. “From that perspective,” he says, “quantum game
theory describes something that people are trying to do.”

It may even be possible to use techniques from quantum cryptography to
construct a quantum stock market in which traders encode their decisions to buy
or sell in qubits. In such a market, entanglement might make traders cooperate
and avoid crashes—the equivalent of everyone losing in game theory.

These applications may be a long way off, but physicists have recently taken
a first step towards them. Spurred by the work of Eisert and colleagues,
physicist Jiangfeng Du and colleagues at the University of Science and
Technology in Hefei, China, used nuclear magnetic resonance to force two nuclei
in a molecule to play Eisert’s two-player version of the Prisoner’s Dilemma.
They found the nuclei behaved as Eisert’s team had predicted.

Even if quantum games never prove technologically useful, these experiments
might at least tell us about how the world works on the quantum level, Hayden
says. “The more interesting possibility would be to look into nature and see it
playing a quantum game,” he says. “I don’t think anyone has done that yet.”

Researchers have seen viruses and bacteria playing classical games
(Nature, vol 398, p 441), and now that they know what to look for, they may
be able to spot atoms and electrons engaged in even funkier quantum contests. In
some situations, atoms or electrons have to choose between two equally
advantageous states—a dilemma formally known as “frustration”. Quantum
games might help frustrated particles resolve such dilemmas, and physicists
believe that frustration is involved in some striking “emergent” phenomena, such
as high-temperature superconductivity. If they can see the particles at play, it
may help them understand and perhaps control the game. And all without a single
stab in the back.