You don't need a final answer at the quantum game show.So come on down says Adrian Cho,everyone's a winner.
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 brother 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. It 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.
'NOW THEY KNOW WHAT THEY'RE LOOKING FOR, RESEARCHERS MAY BE ABLE TO SPOT ATOMS ENGAGED IN QUANTUM CONTESTS'
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
Elsert of Imperial College, London, working with Martin Wilkens of the University
of Pots-dam 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 Elsert 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 (New Scientist, 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 oft 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 Hefel, China, used nuclear magnetic resonance to
force two nuclei in a molecule to play Elsert'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. It 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.