A Beautiful Math

by Tom Siegfried

  Personally, I find this to be an uncanny analogy. In game theory, your best strategy typically is not one predetermined move or set of moves, but a mix of several strategies chosen with some particular probability—say, Strategy A 70 percent of the time and Strategy B 30 percent of the time. In the math of quantum physics, the location of a particle cannot be definitively determined, but only described probabilistically—perhaps you will find it in Region A 70 percent of the time, and in Region B 30 percent of the time. Still, at first glance, you wouldn't expect this analogy to be very meaningful. There's no reason to believe that the math of molecules would be relevant to making choices in economic games. But it turns out that applying quantum math to game theory does allow new decision-making strategies, adding a whole extra dimension to game theory's powers.

  To be sure, some experts have doubted that quantum games offer any real benefits that could not be obtained in other ways. But other researchers have suggested that understanding quantum games could have ramifications for managing auctions, choosing better stock portfolios, and even improving the principles underlying democratic voting. And new technologies have begun to make experimental demonstrations of quantum games possible.

  VON NEUMANN RETURNS

  When you think about it, marrying quantum math to game theory is natural enough. In a way, the surprise is that nobody did it sooner. After all, John von Neumann, the originator of modern game theory, was also a pioneer in quantum mechanics. And the initial impetus for quantum games stemmed from the fact that von Neumann was also a pioneer in developing digital computers.

  When David Meyer, a physicist-turned-mathematician at the University of California, San Diego, was invited to give a talk about quantum computing at Microsoft in January 1998, his thoughts turned to von Neumann. "I was giving a talk to the whole research division and I wanted to come up with something new to talk about," Meyer told me when I visited him at his office on the UCSD campus in La Jolla. "So I was thinking, what could I talk about at Microsoft that they'll be interested in?"1

  Meyer's research had been focusing on quantum versions of computing, and he was naturally familiar with the fact that the standard version of quantum physics math had been developed by von Neumann. "And of course von Neumann is also responsible for the architecture of modern computers to a large extent, so that's relevant to Microsoft also," Meyer noted. "But then there's a third thing that von Neumann is known for—his invention of game theory, which is a big part of economics, and of course that's relevant to Microsoft also. So I thought, OK, how can I put these things together?" It seemed obvious that the thing to do was explore the possibility of a quantum version of game theory.

  Meyer found a place to begin simply by considering game theory terminology. Von Neumann had shown that in two-player zero-sum games each player could always have a "best" strategy, but that it was not always a pure strategy—making the same play (for given circumstances) every time. In some cases the best strategy is to choose from various pure strategies with a certain probability for each—that is, a probability distribution of strategies, or "mixed" strategy.

  "Now the fact that it's called a mixed strategy versus a pure strategy is not an accident," Meyer pointed out. "Von Neumann's responsible, as far as I can tell, for that vocabulary, and that vocabulary is the same vocabulary as in quantum mechanics. You have pure states and you have mixed states—mixed states are probability distributions over pure states. It has the same meaning."

  So Meyer's talk at Microsoft explored a way of bringing quantum theory's multiple "mixed state" realities to game theory. He wisely chose one of the simplest games possible, the penny-flipping game. It's a simple game where the idea is simply to outguess your opponent, since there is no particular logic involved in deciding whether to flip the penny or not. If, however, one player discerns a pattern in the choices of the other, that knowledge could be exploited in repeated sessions of the game.

  In a nonquantum or "classical" version of the game, Picard's best strategy would be to flip the coin half the time (in other words, he should flip a coin to decide whether to flip the coin), thereby making sure there will be no pattern to detect. Q, who gets two moves, should choose each of his four possible strategies one-fourth of the time (flip on both moves, flip on neither move, flip on the first move only, or flip only on the second move). If both players observe those strategies, they should each win half the time. Neither could do better by changing strategies, so it represents a Nash equilibrium.

  In Meyer's quantum scenario, Picard still must play classically. But Q is allowed to play a quantum strategy—that is, he can flip the coin not from heads to tails but into a quantum combination of both possibilities, a coin that is half-heads and half-tails, like an electron that is simultaneously here and there.

  In the lingo of quantum information physics, such a dual-valued head-tail combination is known as a qubit—short for a "quantum bit" of information. In traditional computing, bits are units of information corresponding to one of two possibilities— yes or no, heads or tails, 1 or 0. A classical coin must fall either heads or tails, but a quantum coin is permitted multiple possibilities, a mix of heads and tails at the same time. (I like to think of a qubit as a tossed coin while still spinning—it is neither heads nor tails until it is observed, sort of the way you don't know what a coin will show until it is caught or hits the ground.)

  In actual quantum information experiments, the "coin" is usually a particle of light—a photon—and heads or tails might correspond to how the photon is spinning (the direction in which its axis of spin is pointing). For practical reasons, such experiments more often rely on measuring the photon's polarization, the orientation of the light wave (or more technically, of the electric field component of the light wave). Filters (like the polarized lenses of sunglasses) can block or transmit polarized light depending on its orientation, usually designated as horizontal or vertical. If you imagine the filter as something like a picket fence, a vertically polarized photon would pass through; a horizontally polarized photon would be blocked. (Of course, you could also transmit a photon oriented in between vertical and horizontal—that is, tilted. In that case, the recipient of the photon could tilt the detector, too, and block a photon tilted to the left by tilting the detector to the right.)

  For Meyer's penny, turning it to heads or tails corresponds to setting the orientation of a polarizing filter—showing the head, say, but hiding the tail side of the coin.

  Meyer's math showed how quantum manipulation of the penny can always guarantee that it will end up heads—a win for Q. Since Q plays first, he can use his quantum magic to flip the coin into a 50-50 mix of heads and tails. (In this case, rather than thinking of it as a spinning coin, you could imagine the penny standing on edge.) Therefore it doesn't matter what Picard does on his next move. Whether he flips or not, the penny remains on its edge (mathematically speaking). Q can then perform a reverse quantum move that will return the coin to its original condition— heads up.

  If you'd like a more rigorous explanation, the coin-flipping game can be described in terms of the direction of the quantum coin's spin in a three-dimensional coordinate system (with the coordinate axes labeled x, y, and z). If you define heads as a spin pointing north on the z axis (in the "+z" direction), then tails would be pointing the opposite way (south, or the -z direction). A classical flip (the only move allowed to Picard) merely switches the direction of the spin, from +z to -z. Q, however, can perform a quantum twist to the spin, pointing it "east" (along the +x axis). If Picard then flips the coin from north to south, the spin still points east, so it doesn't matter what Picard does—Q's next move returns the spin to north, or heads, and Picard loses.2 Picard's strategy of flipping the coin half the time—guaranteed by classical game theory to be the best strategy he can play—turns out to be a worthless strategy against a quantum player.

  There's a significance to this point that is easy to miss. Game theory supposedly tells you the best strategy you can pla
y in a game. Meyer's discovery applies a huge asterisk to that statement. The footnote reads, in bold type, that game theory tells you the best strategy only if you are able to ignore the multiple possibilities of quantum physics. And since the world is, in fact, governed by quantum physics, it's more than possible that, in some circumstances at least, quantum games may someday be relevant to real-life situations.

  QUANTUM DILEMMAS

  Meyer's paper reporting the substance of his Microsoft talk was published in Physical Review Letters in 1999.3 Soon thereafter, a second version of a quantum game (focusing on the famous Prisoner's Dilemma) appeared independently of Meyer's work. And in the next few years, dozens of other papers began to explore a whole gamut of quantum games. Most suggested that the outcomes in standard games, such as the Prisoner's Dilemma, might be improved with quantum strategies. Some papers applied quantum game principles to economics, suggesting, for instance, that the multiple possibilities of quantum physics might be applied to selecting the best mix of stocks in a portfolio, or in making decisions about when and whether to buy or sell.

  It seems, though, that the original arguments that quantum strategies permit better outcomes in many games were not airtight. In some cases, merely allowing a "referee" to mediate between players, without any quantum magic, can achieve the same effects. If that were so, there would be nothing really inherently "quantum" about the games—they would just be different games, still classical, but with new rules. After thinking this through, however, Meyer concluded that there are still ways to make games truly quantum in character. "It's true that there are some aspects of quantum games which you can simulate by adding classical communication to what the players do," he told me. "But once you start thinking about adding classical communication … then for a fair comparison the quantum game should really be thought of as adding quantum communication to what the players do, and then there can be a difference." In other words, if the mediators or players are allowed to use quantum communication systems, quantum benefits may indeed be achieved.

  "It's not that hard now to send quantum bits from one place to another," Meyer said. "So it's not implausible that you could … have players in some sort of game-theoretic setting, and you have the referee, rather than classical information, sending them quantum information—the advantage being that the outcome is different and possibly better."4

  If so, he said, various real-life problems might be addressed with quantum game theory. Ways to make online voting both anonymous but verifiable, for example, might be possible with quantum information. Combinatorial auctions, such as the bidding by many companies for various licenses to be issued by the government, could perhaps be managed more efficiently by using quantum information to coordinate the bids.

  "It's quite conceivable to me that some of these things may be doable in a better way or at least a different way by exchanging quantum information," Meyer said. "There's a huge realm to play in here. It's something that should be explored … and it might even be practical at some point."

  QUANTUM COMMUNICATION

  Quantum communication is, in fact, already feasible on a small scale, using optical fibers to transmit particles of light carrying qubits, the quantum bits of information. Qubits can be used to transmit secret codes with uncrackable quantum protection from eavesdroppers, guaranteeing that the code cannot be intercepted without detection. Quantum signaling of this nature has been demonstrated through several miles of optical cable and even through open air. Quantum-coded signaling to military satellites is well within the realm of technological possibility within the future timeframe of Pentagon budget planning.

  To be practical, though, the more grandiose quantum game schemes would probably need a tool that is today only in the infancy of its development—a quantum computer. In fact, one of the neatest things about quantum games is that they could give quantum computers something to do.

  At the moment, quantum computers don't exist in any meaningful sense, although laboratory demonstrations of rudimentary quantum computation have been accomplished. If they can be scaled up to a useful size, quantum computers could exploit the multiple quantum realities to do many calculations simultaneously, thereby drastically shortening the time it takes to solve some very hard problems. So in theory, quantum computers could be enormously more powerful than today's supercomputers, but only for those special sorts of problems that lend themselves to quantum treatment. Massive database searching could be faster with a quantum computer, for example, and breaking secret codes is certainly something you wouldn't want to try without one.

  Today's secret codes, used in military, financial, and other sorts of confidential communications, rely on the difficulty of breaking large numbers down into their prime factors. For small numbers, that's easy to do: 15, for instance, is obviously the product of the two prime numbers 5 and 3; 35 is the product of the primes 5 and 7. But for a number, say, 200 digits long, the world's fastest supercomputer might churn for a billion years without discovering the two primes that were multiplied to produce it. The way secret coding systems are set up, you can encode a message if you know the long number, but decode it only if you know its two prime factors.

  This system seemed pretty secure, as it's unlikely anybody will care if your code gets broken a billion years from now. But in 1994, the mathematician Peter Shor showed that the primes could be discovered quickly—if you had a quantum computer at your disposal. The quantum computer could be programmed to explore all the prime possibilities at once; all the wrong answers would cancel themselves out, leaving a number that could be used to compute the primes easily. Designing and building a quantum computer is much simpler on paper than in practice, though, and it will doubtless be decades before you'll be able to buy one at Best Buy.

  Nevertheless, simple quantum computations can be performed now. In fact, factoring 15 has been achieved with a quantum computer based on the same technology used in MRI medical imaging. And in 2002 Chinese physicists reported an experimental demonstration of the quantum Prisoner's Dilemma game, using a simple quantum computer. In the following year, Chinese physicists Lan Zhou and Le-Man Kuang outlined how to set up a quantum game communication system using lasers and mirrors and other optical devices in a paper published in Physics Letters A.5

  QUANTUM ENTANGLEMENT

  The Zhou-Kuang design exploits one of the most mysterious features of quantum physics, a ghostly bond between particles that have emerged from a mutual interaction. When two particles of light (photons) are emitted simultaneously from the same atom, for example, they retain an ethereal connection—measuring one seems to affect the other even if it is meters, miles, or light-years away. This connection is called "entanglement," and it's one of the things about quantum mechanics that really bothered Einstein (he called it "spooky action at a distance").

  When two photons are entangled, they share quantum information in a peculiar way. If you think of them as spinning coins, they both keep spinning—becoming neither heads nor tails—until one of them is observed. And then the other one stops spinning, too! So suppose I possess two pennies, spinning within opaque boxes, entangled in such a way that if one is observed to be heads, the other will turn up tails. I send one box via FedEx to my sister in Ohio. She can't resist opening the package right away and discovers the penny on the bottom of the box, showing heads. The instant she sees it, the penny in my remaining box stops spinning and shows tails—whether I'm in Texas or California or on the International Space Station. Even if I don't look in my box, I know damn well that the penny shows tails (once my sister has called to tell me that hers is heads).6 Somehow, my sister's observation of her penny influenced the state of my penny, no matter how far away we are. The same thing happens for real with actual photons of light, when you measure not heads or tails but how the photon is spinning or the orientation of its polarization.

  This shared information between entangled particles can be exploited for many kinds of quantum communication purposes. In a quantum game, enta
ngled particles can carry information about a player's choice in such a way that one choice will influence another. Take the Prisoner's Dilemma game. In the classical game, the players typically choose to defect because they cannot be sure that their partner will cooperate. Overall, the pair's best strategy is for both to remain silent—that way they'll serve the least amount of time. But each individual prisoner's best strategy is to rat out the other (to avoid the risk of a much longer sentence). So the best choice for the individual turns out not to be the wisest choice for the team."We have a dilemma," write quantum game theorists Adrian Flitney and Derek Abbott, "some form of which is responsible for much of the misery and conflict throughout the world."7

  But suppose there was a way that both players could make their decision hinge on the decision of the other. That's what playing with entangled photons offers. As Zhou and Kuang showed, you can set up an apparatus that allows the choice of "defect" (rat out your partner) or cooperate (keep mum) to be transmitted by photons, passing through a maze of mirrors and other optical devices, ultimately to reach a detector signifying either defect or cooperate. You can shoot your photon into the maze in different ways—so that it would end up in the "defect" detector, for instance, or in the "cooperate" detector. There's nothing tricky about that. But the maze can be set up so that the photons from the two players become entangled, with the result that both will end up cooperating. That is, you can send your choice in such a way that your photon will send a signal to cooperate only if the other one does, too.

  This work shows that quantum game theory, at least in principle, could be used to alter in a deep and profound way the choices people make given the choices of others. Imagine, for instance, a quantum version of the "public goods" game discussed in earlier chapters. The idea is that a neighborhood group proposes building a project of public benefit, such as a park, to be paid for by voluntary contributions. Presumably people who want the park will contribute the most money to the fund drive. But standard game theory suggests that many people who want the park will contribute little or no money, reasoning that others will fork over enough to pay for it. Therefore it's hard to get donations, even for a park everybody desires, without the intervention of some outside agency (say, a tax collector).