Tomorrow Elephant

By now, pretty much everybody has heard of quantum computing, that arcane science of replacing ones and zeroes that power today’s computers with qubits (Schrödinger’s Cat versions of bits). Really usable quantum computers do not yet exist, but once they do, they will be able to do things like break the RSA encryption algorithm and simulate quantum systems effectively. (Paranoids, take note: NSA is well up to speed on this.) It also looks like quantum computation and quantum information theory will be an interesting new paradigm for physics in general: a historical precedent for this is the way classical information theory was used to reformulate thermodynamics.

The first rule of speculating about the future is to expect magic, and while the implications of quantum information processing mentioned above are exciting and potentially earth-shaking, they are hardly magical. The really magical things will transform the way we think and interact, and I’m starting to feel that one of these things may be quantum game theory. Basically, the lesson is that game theory gets very interesting if you allow the players to use quantum technology. This has potentially extremely disruptive consequences in economics and other multi-agent systems, probably down to things like dating. I’m going to give a brief, non-technical discussion with some science-fictional speculation: if you are looking for a serious review of the field, check out Azhar Iqbal’s PhD thesis.

Here’s a simple example (swiped from Marginal Revolution, an excellent economics blog) of how quantum players can outperform classical ones.

You and I are each asked a single question, either “Do you like cats?” or “Do you like dogs?”. Our questions are determined by independent coin flips. We both win if our answers differ, unless we’re both asked about dogs, in which case we both win if our answers match.

Here’s a pretty good strategy we could agree on in advance: We’ll contrive to always differ. Whatever we’re asked, I’ll say yes and you say no. That way we win 3/4 of the time. Classically, we can’t do any better than this. There is, however, a quantum version of this game. In this game, all we need is a pair of entangled particles, easy enough to create in the laboratory. If I get the cat question, I’ll measure my particle’s spin (which is either up or down) and answer “yes” or “no” accordingly. If I get the dog question, I’ll do the same thing, but first I’ll rotate my measuring apparatus by 90 degrees. You do the same, but start with your measuring apparatus rotated 45 degrees from mine.

The thing about entangled particles is that the outcomes of these measurements are correlated in a very particular way, and remain so forever, even if the particles are separated. In particular, our answers will differ about 85% of the time unless we both make “dog” measurements, in which case they’ll agree about 85% of the time. Overall, then, we’ll have about an 85% win rate! The explanation for this, of course, is that we are playing a different game than the original: introducing the quantum operations allows for a much bigger space of strategies.

Amazingly, this approach generalises to classic games such as Prisoner’s Dilemma and the so-called public goods problem (which can be thought of as a kind of multiplayer version of Prisoner’s Dilemma). I find the latter especially interesting, although the generality of Prisoner’s Dilemma (which can be used to model many, many situations ranging from trench warfare to cigarette advertising) suggests that the implications of quantum games could be very far-reaching. But just to begin with, solving the public goods problem in a new way could make traditional forms of economy and governance obsolete…

A typical example of a public goods problem —- or “tragedy of the commons” involves a group deciding whether or not to provide a common resource while there are potential free riders around. One solution to this is to punish the free riders —- but this requires a third party to act as an enforcer, typically a government. Especially for small-scale cooperative efforts (neighborhood watch) this is pretty inefficient, and that’s why community efforts often fail.

The details of the quantum version of the public goods game are a bit involved, but basically quantum entanglement allows individuals to pre-commit to agreements where otherwise it would be individually rational to renege. The overall solution is much more efficient than the classical one and eliminates free-riders automatically.

The cool thing about this is that mechanisms allowing quantum public goods systems to be created are actually a lot easier than building full-blown quantum computers. Unline quantum computers, quantum games don’t require repeated quantum operations on the qubits (something that causes so-called decoherence —- interaction with the environment that spoils the quantum properties of the system). The only thing a quantum economy requires is rapid exchange of entangled qubits, something that could be implemented via nonlinear optics and perhaps some sort of central server. People have actually worked out various schemes to implement this in practice, and technologically such setups are probably only years or at most a decade away.

A research group at HP Labs recently ran tests with people with no formal training in quantum mechanics, making them play an iterated quantum Prisoner’s Dilemma via a very intuitive interface. (The test setup was based on simulated quantum mechanics —- HP does not yet have an entangled photon exchange service in place.) The subjects achieved the cooperation results predicted by the theory!

I’m thinking that the practical implications of this will be two-fold. One, we will start to see a lot of automatic multi-agent systems that use quantum game theory for optimisation. There are already automatic trading agents that maintain your stock portfolio for you —- quantum agents would just do it better. (Quantum portfolio management has already been discussed in the literature.) Ditto for e.g. multi-agent systems that people are researching for managing microgeneration of power (using the wind turbine in your back yard to trade power with the local grid). Or in a military setting you could have swarming battlefield robots using quantum strategies (which might be handy since they would probably be using quantum cryptographic links to communicate anyway). Or traffic management, or whatever. The consequences of all this would probably be invisible to most people, just black box improvements to existing systems.

But exploring “quantum communism” as a new way of thinking/social interaction might be more fun from a science-fictional point of view, which of course is what I’m mainly interested in. One might think that it would be hard to integrate the rather abstruse quantum operations into everyday life — but things like low-level programming languages can be pretty counter-intuitive as well, yet 12-year-olds these days pick them up effortlessly. And there are new games-based learning paradigms that might make understanding the quantum world easier — playing Quantum Duck Hunt, for example. (Try Greg Egan’s cool quantum soccer applet to get an idea of what it could be like.)

So it’s likely that the generation that grows up with quantum computing will take to quantum thinking like fish to water. The hyperwired teenagers of, say, 10-15 years from now will create their own quantum economies on their mobile phones or equivalent devices thereof (probably not physical devices but some sort of personal desktop that one can summon from ambient computing machinery wherever one happens to be, like YouOS but anyway). There are social versions of the public goods problem where using automated agents to allocate resources would not make sense —- assigning tasks in an open-source programming project, say —- but which could benefit from the quantum approach. The common element in all the quantum games seems to be that they encourage cooperation and eliminate free riders so they could be important in creating big collective projects like Wikipedia. I’m sure one could come up with other examples, like some weird polyamorous dating system…

So, in 2030 (say) my personal AI will use quantum game theory to keep my house warm and manage my stock portfolio without me being any wiser, but my children use it to run their love life. (Besides asking me for credits to clone a body for their virtual sex robot.)

I’ve also been thinking that a quantum public goods algorithm could be one way to implement Eliezer Yudkowsky’s “coherent extrapolated volition” for creating Friendly AIs — it’s sort of like Asimov’s Three Laws on steroids. But more radical post-Singularity implications of quantum game theory are left as an exercise to the reader…

Perhaps there is a parallel universe where young Lenin met young Erwin Schrödinger and we got properly working communism instead of this chaotic capitalist mess that goes crazy whenever a Wall Street trader treads on a butterfly. And who knows, maybe the next step after a quantum economy is a many-worlds economy…