text:
# Superfluid–Insulator Transition in Commensurate Disordered Bosonic Systems: Large-Scale Worm-Algorithm Simulations

## Abstract

We report results of large-scale Monte Carlo simulations of superfluid–insulator transitions in commensurate 2D bosonic systems. In the case of off-diagonal disorder, we find that the transition is to a gapless incompressible insulator, and its dynamical critical exponent is $`z=1.65\pm 0.2`$. In the case of diagonal disorder, we prove the conjecture that rare statistical fluctuations are inseparable from critical fluctuations on the largest scales and ultimately result in the crossover to the generic universality class (apparently with $`z=2`$). However, even at strong disorder, the universal behavior sets in only at very large space-time distances. This explains why previous studies of smaller clusters mimicked a direct superfluid–Mott-insulator transition.

Quantum phase transitions in disordered systems remain a poorly understood phenomenon despite enormous interest in this field. The $`T=0`$ transition between the superfluid (SF) and insulating (I) phases is believed to determine properties of various condensed matter systems: 4He in porous media and aerogels Crowell9597 ; Reppy2000 , 4He on various substrates quartz1 ; Crowell9597 ; hydrogen1 , thin superconducting films Liu ; Valles ; Hebard ; Yazdani ; Goldman ; Kravchenko ; Sarachik , Josephson-junction arrays Zant , disordered magnets Read ; Vajk , etc.

There are strong arguments that the basic Hamiltonian which captures all the essential physics of the SF-I transition is the bosonic Hubbard model with disordered chemical potential Ma8586 ; Fisher89 ; Fisher91 ; Wallin94 . In the limit of large occupation numbers, the bosonic Hubbard Hamiltonian is equivalent to the system of coupled Josephson junctions. Fermionic systems map to this Hamiltonian under the assumption that Cooper pairs are preformed at finite temperature, and the transition is driven only by quantum fluctuations of the phase of the complex order parameter. To deal with granular superconductors one may also introduce disorder to hopping amplitudes.

It was suggested in Ref. Fisher89  that one has to consider only two competing insulating phases—the incompressible (gaped) Mott-insulator phase (MI), and the compressible gapless Bose glass (BG) phase. However, more recently it was argued that apart from the BG phase characterized as a compressible insulator with variable-range-hopping conductivity at finite temperature Fisher89 , there may exist other phases such as a Bose metal with finite conductivity in the $`T0`$ limit Phillips  and an incompressible Mott glass with the conductivity pseudogap Giarmarchi . Theoretical calculations for the strongly coupled SF-I critical point are notoriously difficult and are not based on well controlled approximations since localization and interaction effects cannot be separated Mukh ; Igor01 . Thus even the qualitative understanding of the phase diagram is still under debate. In particular, it was argued in Fisher89 ; Fisher91 ; Wallin94 ; Wen2 ; FM96  that MI and SF phases are always separated by the BG phase at any finite disorder. However experiments Crowell9597 , most Monte Carlo simulations Krauth91 ; Pai ; Kisker , and other theories Zhang ; Singh ; Pazmandi  present evidence in favor of a direct transition between MI and SF phases (in the case of commensurate filling of the lattice and not so strong disorder). In $`d=1`$ this contradiction was apparently resolved using arguments based on rare statistical fluctuations FM96  (Lifshitz-Griffiths-McCoy singularities Lifshitz ; Griffiths ; Coy ), renormalization-group equations Svistunov96 ; Igor98a , and quantum Monte Carlo simulations ourGlass ).

In this Letter, we numerically address the problem of the SF-I transition in a disordered commensurate 2D system. Our large-scale simulations based on the classical Worm Algorithm Worm  demonstrate the absence of the direct SF-MI transition. We clearly see, however, that—even at strong disorder—the universal asymptotic long-range behavior sets in only at large space-time distances. This result, on one hand, explains previous observations of the direct SF-MI transitions in simulations of much smaller clusters, and, on the other hand, implies that the superfluid stiffness and compressibility should obey generic scaling laws only in a very close vicinity of the phase transition point which may be hard to study experimentally.

The Worm algorithm (WA) Worm  is a high-performance universal Monte Carlo scheme applicable to any model with the configuration space of continuous paths. The principle of WA is to work in an extended configuration space combining the physical closed-path sector and the broken-path sector with two path endpoints. All updates in the extended configuration space are through the motion of the endpoints (or even just one of them), so that the configuration evolution looks like a creeping worm. Though the WA updating strategy is based on local Metropolis moves (which is a key issue for its universality), it has a remarkable efficiency equivalent to that of the best cluster algorithms worm2001 .

WA was introduced initially for the continuous-time path integral, or worldline, representation of lattice quantum systems Worm . More recently it was implemented within the Stochastic Series Expansion (SSE) method SSE , and generalized to classical lattice systems in the closed-path representations worm2001 . The optimal choice of WA depends on the problem being addressed; e.g. the quantum worldline scheme is best suited for ab initio simulations of bosons in optical lattices ourOlattice , while the SSE scheme has certain storage and computational advantages when simulating quantum models with a restricted Hilbert space, like spins and hard-core bosons Sandviklast ; DT . However, if one is interested in generic properties of quantum phase transitions, then the optimal choice is a $`(d+1)`$-dimensional classical scheme, which is algorithmically superior from all points of view. This approach was advocated in Ref. Wallin94 , and most recently, using WA, in Ref. AS .

The easiest way to derive the classical $`(d+1)`$-dimensional equivalent of the $`d`$-dimensional quantum model is to start from the lattice path integral for particle trajectories in imaginary time. The basic step is to “roughen” trajectories by replacing integrals over kink positions (particle jumps between lattice sites) in time by discrete sums. To this end one introduces a grid of imaginary times and requires that kinks occur only at time slices forming the grid. Bonds in the spatial direction of thus obtained $`(d+1)`$-dimensional lattice carry an integer charge—a spatial current equal to an algebraic sum of kinks associated with a given pair of sites and a time slice (the kink sign specifies its direction). The finite value of the time interval between slices, $`\mathrm{\Delta }\tau `$, makes the roughening procedure, generally speaking, not unique. Only in the physical limit of $`\mathrm{\Delta }\tau 0`$ the absolute values of spatial currents are either zero or unity. At strong roughening the constraint that the absolute value of the spatial bond charge is $`1`$ is no longer necessary. The maximal value now depends on how we roughen the original trajectories with more than one kink between a given pair of sites during the time interval $`\mathrm{\Delta }\tau `$—either as irrelevant rare events that are neglected, or by ascribing all such kinks to the same spatial bond of the $`(d+1)`$-dimensional lattice. Note, there is no qualitative difference between the two cases, and the choice is just a matter of convenience. Bonds in the temporal direction also carry an integer charge, equal to the occupation number of a given site between adjacent time slices. For the sake of symmetry, it is convenient to refer to the temporal-bond charges as temporal currents, so that each bond of the $`(d+1)`$-lattice carries an integer current, $`J`$. The conservation of the particle number imposes an obvious constraint on bond currents—the divergence of the $`(d+1)`$-current at any $`(d+1)`$-site is zero. Graphically, if one represents the bond currents by oriented lines (in accordance with the sign of $`J`$) then all contributions to the partition-function will have a form of closed-path configurations of such lines, while configurations for the Green-function will have two endpoints. WA simulates both quantities simultaneously, by switching between partition-function and Green-function sectors Worm ; worm2001 .

Let us denote by $`\{J_{𝐱,\alpha }\}`$ the bond current configuration where $`𝐱=(𝐫,\tau )`$ are discrete space-time coordinates, and index $`\alpha =\widehat{r}_1,\mathrm{},\widehat{r}_d,\widehat{\tau }`$ stands for unit vectors of axis directions, so that $`(𝐱,\alpha )`$ defines a bond in the direction $`\alpha `$, adjacent to the site $`𝐱`$. As usual, the configuration weight $`W[\{J_{𝐱,\alpha }\}]`$ may be formally written as a Gibbs factor $`\mathrm{exp}\{H/T\}`$ which for positive-definite $`W`$ defines the classical bond Hamiltonian $`H/T=\mathrm{ln}W`$. For models with on-site particle-particle interactions the configuration weight is simply given by the product of bond weights $`W_{𝐫\alpha }(J_{𝐱,\alpha })`$, and, correspondingly,

$$H=\underset{𝐱\alpha }{}H_{𝐫\alpha }(J_{𝐱,\alpha }).$$
(1)
The zero-divergence constraint can be written as $`_\alpha J_{𝐱,\alpha }+_\alpha J_{𝐱,\alpha }=0`$, where, by definition, the direction $`\alpha `$ is understood as opposite to $`\alpha `$ and $`J_{𝐱,\alpha }=J_{𝐱\alpha ,\alpha }`$.

In this paper, we are interested only in the universal critical behavior of the model (1), which is supposed to be insensitive to quantitative details of the Hamiltonian. This freedom may be used to make spatial and temporal directions symmetric with respect to each other. In the original quantum model, the temporal direction is not symmetric even with respect to its opposite because occupation numbers are always positive. Nevertheless, one may count them from some integer $`n_0`$, substitute $`J_{𝐱,\widehat{\tau }}J_{𝐱,\widehat{\tau }}n_0`$, and formally consider $`J_{𝐱,\widehat{\tau }}(\mathrm{},\mathrm{})`$. Alternatively, one may introduce a symmetric constraint, say, $`|J|1`$. The latter case, reminiscent of the mapping between bosonic and spin-1 systems, seems to be more natural and computationally economic. Historically, however, a model with $`J(\mathrm{},\mathrm{})`$, motivated by its derivation from the Josephson-junction array Hamiltonian Wallin94 , was adopted. To retain the possibility of a direct comparison with previous numeric studies, we work with the same model Wallin94 :

$$H/T=\underset{𝐱\alpha }{}\left[\frac{1}{2}J_{𝐱,\alpha }^2\delta _{\alpha ,\widehat{\tau }}\mu _𝐫J_{𝐱,\widehat{\tau }}\right]/K.$$
(2)
In terms of the underlying bosonic system, $`K`$ represents the particle hopping amplitude in units of the on-site repulsion, the discrete field $`\mu _𝐫=\mu _0+\stackrel{~}{\mu }_𝐫`$ involves the chemical potential $`\mu _0`$ and the white-noise diagonal disorder $`\stackrel{~}{\mu }_𝐫[\mathrm{\Delta },\mathrm{\Delta }]`$. In this study we are concerned with the commensurate filling of the lattice, i.e. $`n=J_{𝐱,\widehat{\tau }}=`$integer, where $`\mathrm{}`$ stands for the average over all lattice points, statistical and disorder fluctuations, and thus set $`\mu _0=0`$. \[An accurate study of the half-integer $`n`$ case has been reported recently by Alet and Sørensen AS \]. We also consider model (2) with the off-diagonal disorder introduced by letting the parameter $`K`$ to be dependent on $`𝐫`$ and spatial direction, and confine ourselves to the case of a broken-bond disorder, where for some randomly chosen $`𝐫`$ and $`\alpha ^{}=\widehat{r}_1,\mathrm{}\widehat{r}_d`$ we set $`K_{𝐫\tau \alpha ^{}}0`$ (equivalent to a rigid constraint $`J=0`$ on the corresponding bond). The phase diagram of the homogeneous system is shown in Fig. 1; the SF-I transition at the commensurate filling is located at $`K_c^{(0)}=0.33305(5)`$ AS . The value of the MI gap is defined as half the difference between the critical values of the chemical potential in Fig. 1, i.e. $`2E_{\mathrm{gap}}(K)=\mu _c^{(\mathrm{up})}\mu _c^{(\mathrm{down})}`$.

We start with the off-diagonal disorder case, and consider a system with a quarter of all bonds being broken. Typically, we include about $`10^3`$ disorder realizations into the statistics for system sizes $`L40`$, and $`4\times 10^4/L`$ for larger $`L`$. The critical point, $`K_c`$, and the dynamical exponent, $`z`$, may be obtained from the study of the Green function, $`G(𝐫,\tau )`$, naturally evaluated within the WA approach Worm . At the critical point one should see a power-law decay: $`G(r,0)r^{(z+\eta )}`$ as $`r\mathrm{}`$, and $`G(0,\tau )\tau ^{(1+\eta /z)}`$ as $`\tau \mathrm{}`$. This way we find (see Fig. 2, as well as Figs. 3, and 4)

$$K_c=0.3813(2),$$
(3)
$`z+\eta =1.37(8)`$, $`1+\eta /z=0.82(6)`$, i.e.

$`z`$ $`=`$ $`1.65(20),`$ (4)
$`\eta `$ $`=`$ $`0.3(1).`$ (5)
It is clear in Fig. 2 that the asymptotic behavior of the correlation function sets in only at sufficiently large space-time distances $`>10`$ lattice periods. Moreover, the short-range behavior of $`G`$ mimics the critical point of the SF-MI transition in the regular system, where $`z=1`$. This peculiar behavior implies that the curves for the superfluid stiffness, $`\rho _s`$, and compressibility, $`\kappa `$, will acquire their universal forms only in a very narrow region around the critical point. Away from this region, the form of $`\rho _s(KK_c)`$ and $`\kappa (KK_c)`$ curves should be essentially different, as suggested by the extended transient evolution of $`z`$ from $`1`$ to its true critical value. In Figs. 3 and 4 we indeed observe such a behavior. The anomalously narrow critical region makes it virtually impossible—even with our large cluster sizes—to reliably determine the correlation radius critical exponent $`\nu `$. Along with the dynamical exponent $`z`$ it is supposed to determine the critical behavior of the compressibility, $`\kappa (KK_c)^{\nu (2z)}`$ and superfluid stiffness, $`\rho _s(KK_c)^{\nu z}`$ Fisher89 . The data in Figs. 3 and 4 at best guarantee only the inequalities $`\nu (2z)<1`$ and $`\nu z>1`$, but do not allow us to test the Harris criterion Harris  $`\nu >2/d=1`$.

The finite-size scaling of the data for compressibility demonstrates no sign of saturation below $`K_c`$ and thus strongly suggests that in the insulating state the compressibility vanishes. Though the insulating state is incompressible, it is easy to prove that it is gapless and thus is qualitatively different from the conventional Mott insulator and Bose Glass states. Indeed, in an infinite system it is always possible to find an arbitrarily large cluster that is nearly uniform (in the sense that fluctuations of $`K`$ away from its cluster average value are arbitrarily small/rare). Taking into account that $`K_c`$ in the disordered system is larger than the ideal-system critical value $`K_c^{(0)}`$, we conclude that such clusters are nothing else but finite-size superfluid lakes. Hence, the gap associated with adding one more particle to the cluster scales as $`1/l^d`$, where $`l`$ is the cluster size. The absence of an upper bound on $`l`$ immediately implies the absence of the global gap in the system spectrum and finite optical conductivity.

The diagonal-disorder case is different. Previously reported data Kisker  for small clusters $`L\times L12\times 12`$ and disorder strength $`\mathrm{\Delta }=0.2`$ were interpreted as a direct SF-MI transition with $`z=1`$. We extended the study of the $`\mathrm{\Delta }=0.2`$ case to system sizes $`L\times L160\times 160`$ and did not find any deviations from the direct transition picture with vanishingly small compressibility below $`K_c(\mathrm{\Delta }=0.2)=0.325(1)`$. However, the value of the MI gap in the ideal system is almost three times smaller than $`\mathrm{\Delta }`$ at $`K=K_c`$, see Fig. 1. According to the argument/theorem of Refs. Fisher89 ; FM96 , the state with $`\mathrm{\Delta }>E_{\mathrm{gap}}`$ is a compressible (gapless) insulator, or BG, because in the infinite system one can always find arbitrary large regions with the chemical potential being nearly homogeneously shifted downwards or upwards by $`\mathrm{\Delta }`$ (and thus they are doped with particles or holes). Since the distance between such regions is exponentially large for $`\mathrm{\Delta }0`$, their effect is simply undetectably small for $`\mathrm{\Delta }=0.2`$.

Even if the state right below $`K_c`$ is a compressible insulator, the question remains whether Griffiths-McCoy singularities are inseparable from critical fluctuations and ultimately result in the crossover to the generic SF-BG transition, or they merely provide a regular background contribution to $`\kappa `$ on which a singular contribution $`\kappa _{\mathrm{sing}}`$ is superimposed. The latter scenario implies a cusp on the compressibility curve, and criticality different from SF-BG. To answer this question we performed simulations for disorder strength $`\mathrm{\Delta }=0.4`$. As before, the ideal MI gap at the transition point $`K_c=0.2910(5)`$ is about two times smaller than $`\mathrm{\Delta }`$, and $`\kappa `$ has to be finite at $`K_c`$.

In Figs. 5 and 6 we show the data for the compressibility and superfluid stiffness which away from the critical point mimic the ideal-system behavior (with the correlation length exponent $`\nu 0.7`$ and $`z1`$), but close to $`K_c`$ show a spectacular crossover to another universality class. Strong finite-size corrections to $`\kappa `$ for system sizes $`L20`$ saturate for $`L>20`$, and the thermodynamic curve clearly demonstrates finite, and non-singular dependence $`\kappa (KK_c)`$. At the same time, we observe a crossover in the $`\rho _s(kK_c)`$ dependence, and see that $`\rho _s`$ approaches zero with zero derivative, i.e. $`\nu z>1`$. From the decay of the Green function at the critical point we obtain

$`z`$ $`=`$ $`2.0(2),`$ (6)
$`\eta `$ $`=`$ $`0.11(2).`$ (7)
Unfortunately, the large-scale crossover did not allow us to determine the critical exponent $`\nu `$ from this set of data. Recent data for half-integer $`n`$ are best fit with $`\nu =1.15`$, but they also suffer from large finite-size corrections AS . Apparently, the best strategy in the future is to search for a classical model with the smallest crossover scale.

Within the WA approach one may directly visualize places where particles are added/removed at low temperature in a sample with a given disorder realization. The standard procedure of subtracting density maps obtained in canonical simulations $`n(i,N)n(i,N1)`$ is time consuming, and for large systems requires extremely high-precision data for $`n(i,N)`$. The new technique is based on the statistics of the Green function calculated at the chemical potential between the steps on the $`N(\mu )`$ curve, i.e. at $`\mu =E_G(N)E_G(N1)`$, where $`E_G(N)`$ is the ground state energy of the $`N`$-particle system. In the $`T0`$ limit we write $`G(N;𝐫,𝐫^{},\tau =\beta /2)=F(N;𝐫,𝐫^{})`$ and notice that only ground states with $`N1`$ and $`N`$ particles contribute to the answer. Thus $`F(N;𝐫,𝐫^{})\varphi _N(𝐫)\varphi _N(𝐫^{})`$ where $`\varphi _N(𝐫)`$ is given by the positive-definite groundstate-groundstate matrix element

$$\varphi _N(𝐫)=\mathrm{\Psi }_G(N)|b_𝐫^{}|\mathrm{\Psi }_G(N1),$$
(8)
and may be viewed as the added-particle “wavefunction”. Its localization length diverges at the SF-I transition. The two important parameters which characterize the structure of the normalized wavefunction are the localization radius

$$^2=\left[𝐫𝐫\right]^2=\underset{𝐫}{}\left[𝐫𝐫\right]^2\varphi _N^2(𝐫),$$
(9)
and the state “area”, or the number of sites over which $`\varphi `$ delocalizes,

$$𝒜=\frac{\underset{𝐫}{}\varphi _N^2(𝐫)}{_𝐫\varphi _N^4(𝐫)}.$$
(10)
The dependence of $`𝒜`$ on $``$ gives the fractal dimension of the state. It is also important to monitor correlations in the overlaps between different states, $`_𝐫\varphi _N(𝐫)\varphi _N^{}(𝐫)`$. For example, the percolation type scenario of the SF-I transition assumes large fractal superfluid “lakes” in the insulating phase; if so, then with the probability of order unity there must exist an almost complete overlap between a pair of states $`(\varphi _{N_a},\varphi _{N_b})`$ with $`N_a,N_b`$ from a narrow interval of width $`\delta NN`$ around $`N`$.

In Fig. 7 we show a typical map of $`_𝐫^{}F(N=1;𝐫,𝐫^{})`$ for the insulating state at $`K=0.288`$ and system size $`L\times L\times L_\tau =160\times 160\times 1000`$. One can clearly see isolated regions doped with particles.

In summary, we have performed large-scale simulations of the superfluid–insulator transition in the $`(2+1)`$-dimensional classical analog of the commensurate disordered 2D bosonic system. For diagonal disorder, our results suggest that commensurability is not relevant in the long-range limit, and the universality class of the transition (superfluid–Bose-glass) is the same for all filling factors. In particular, we unambiguously resolved the finite compressibility at the critical point originating from rare statistical fluctuations and demonstrated that they are responsible for the crossover in critical behavior. We believe that our results rule out the earlier-reported direct superfluid–Mott-insulator transition in this model.

In the off-diagonal disorder case, the compressibility vanishes at the critical point. The incompressible insulating phase, however, is gapless, and its universality class is characterized by the dynamical critical exponent $`z=1.65\pm 0.2`$.

A general observation is that even for large diagonal and off-diagonal disorder, the universal asymptotic long-range behavior sets in only at large space-time distances ($`20`$ lattice periods). This circumstance explains previous observations of the direct superfluid–Mott-insulator transition in small-size clusters and implies that the the superfluid stiffness and compressibility should obey generic scaling laws only in a very close vicinity of the phase transition point.

The authors are grateful to S. Sachdev for a fruitful discussion. This work was supported by the National Science Foundation under Grant DMR-0071767. BVS acknowledges a support from Russian Foundation for Basic Research under Grant 01-02-16508, from the Netherlands Organization for Scientific Research (NWO), and from the European Community under Grant INTAS-2001-2344.


format: text

text:
# A Practical Quantum Mechanism for the Public Goods Game

## I Introduction

Quantum information processing provides a variety of new capabilities with potentially significant performance improvements over conventional techniques. One example is quantum computation with its ability to rapidly solve problems, such as factoring Shor (1994), which appear to be otherwise intractable. However, implementing machines with enough bits and coherence time to solve problems difficult enough to be of practical interest is a major challenge. Another application, quantum cryptography, is feasible today for exchanging keys over distances of tens of kilometers. A third area, which potentially can come into practical use soon, is quantum economic mechanisms and games. Extending classical games into the quantum realm broadens the range of strategies Meyer (1999), and has been examined in the context of the Prisoner’s dilemma Eisert et al. (1999); Eisert and Wilkens (2000); Du et al. (2001, 2002) and the $`n`$-player minority game Benjamin and Hayden (2001). Quantum games do not require long sequences of coherent operations and hence are likely to be easier to realize than large-scale quantum computations.

In this paper, we present a quantum version of an important social dilemma: public goods. Provisioning for public goods is a well-studied social choice problem. A typical example is a group deciding whether to provide a common good, such as a park, in the face of potential free riders. The free rider problem Hardin (1968) cannot be solved with traditional means without either a third party to enforce agreements or a repeated game scenario in which participants can self-police. Government is one typical solution. While government is a good solution to public goods involving a large population such as national defense, it is inefficient to provide public goods in smaller groups such as neighborhood watch. Provision of these smaller scale public goods often relies on altruism and other weaker incentives. Invariably, contributions to these public goods are not at efficient levels.

Quantum mechanics offers the ability to solve the free-rider problem in the absence of a third party enforcer in a single shot game without repetition. With suitable design, simple mixed strategies almost entirely avoid the free rider problem and give expected performance close to the Pareto efficient value when the size of the group is large. In our case, the power of the quantum mechanism comes from entanglement. Quantum entanglement allows individuals to pre-commit to agreements where otherwise it would be individually rational to renege.

Three different quantum mechanisms with different degrees of entanglement are reported in this paper. These differ in their performance characteristics and ease of implementation. The results provide information about how one can best design a quantum mechanism to solve the free-rider problem.

Equal to the importance of its economics properties is whether a quantum mechanism can be built. This issue is addressed by restricting our attention to quantum systems that can be practically implemented by technologies that could soon be available. Creating and communicating highly-entangled states among $`n`$ players poses significant implementation challenges. The most readily implementable mechanisms are those that only require entanglement among pairs of states. Thus an interesting practical question for developing applications of quantum information processing is whether performance of the public goods game can be significantly improved with quantum mechanisms limited to using two-particle entangled states. We have developed a mechanism only requiring communication of two-particle entangled states among the players. This mechanism could be feasible to implement in the near future even for players at different locations.

The paper is organized as follows. Section 2 describes the general approach to “quantize” a classical game. Section 3 discusses the economics of the public goods game. Section 4 describes the quantum version of the public goods game and its solutions. Section 5 concludes with possible extensions to our mechanism.

## II Quantum Games

This section describes one approach to generalize conventional games to make use of entangled quantum states. We then discuss issues involved in their implementation, particularly the significant benefit for games restricted to use only two-particle entanglement.

### II.1 Creating Quantum Games

A game consists of a set $`S`$ of choices available to the players and an associated payoff to each player based on those choices. With $`s_kS`$ denoting the choice made by player $`k`$ and $`s=(s_1,\mathrm{},s_n)`$. A game is defined by the payoffs to the players depending on these choices, i.e., $`P_k(s)`$.

One approach Eisert et al. (1999); Benjamin and Hayden (2001) for generalizing these games to quantum operators considers superpositions of all possible choices $`_s\psi _s|s`$ summing over all choices in $`S`$ for each player. The quantum version of the game starts by creating an initial superposition. Subsequently each player is allowed to operate only on their corresponding part of the state. In the last stage, the final superposition is used to produce a definite choice for each player via a further joint operation followed by a measurement. The initial and final operations, acting on the full superposition, are fixed and known to the players.

To give a direct generalization of the original game, the player’s operations should include choices that correspond to the original choices. That is, the initial and final operations on the state should reproduce the payoff structure for the original game if all players restrict their individual operations to just those corresponding to the actions allowed in the original game.

More precisely, the game proceeds as follows:

* Starting with a particular initial superposition $`v`$, create the entangled state $`Jv`$, where $`J`$ is an entanglement operator that commutes with the classical single-player operators.
* Players select an operation to apply to their part of the superposition, giving $`v^{}=(U_1\mathrm{}U_n)Jv`$ where $`U_k`$ is operator used by player $`k`$.
* Finally undo the initial entanglement, giving $`\psi =J^{}v^{}`$. For a given game, i.e., choices for $`v`$ and $`J`$, the final superposition is a function of the players’ choices, i.e., $`\psi (U_1,\mathrm{},U_n)`$.
* Measure the state, giving a specific value for each player’s choice. The probability to produce choices $`s`$ (i.e., a particular assignment, 0 or 1, to each bit) is $`|\psi _s|^2`$.

The choice of $`J`$ determines the type and amount of entanglement among the players. The commutation condition on $`J`$ ensures that if each player selects the operator corresponding to one of the choices in the original game, the final result of the quantum game will, with probability 1, reproduce those choices.

### II.2 Implementing Entanglement for Many Players

Ideally, we would like our scheme to rely on the distribution of entangled states between distant players, implying that the qubits are encoded in the polarization states of photons transmitted throughout a fiber-optic network. Given a bright source of polarization-entangled photon pairs Kwiat et al. (1999), these qubits can be delivered by propagation through optical fibers, and purified using high-quality linear optical elements Pan et al. (2001a). In principle, maximally entangled $`n`$-photon states can be constructed from entangled two-photon states Bouwmeester et al. (1999); Pan et al. (2001b), and these states can be further manipulated using linear optical elements to perform universal gate operations Knill et al. (2001).

However, scaling a fully entangled game from 2 to $`n`$ players can be nontrivial even when linear optics is used. Suppose a trial between any two players succeeds with probability $`\beta `$ (incorporating the net efficiency with which entanglement can be created, distributed, purified, manipulated, and detected), so the mean number of trials needed to successfully register a mutual choice between two players is $`1/\beta `$. Because an accidental (or deliberately disruptive) measurement of a single qubit in the $`n`$-particle maximally entangled state destroys the entire state, we expect the number of trials needed to complete a maximally-entangled game for $`n`$ players will scale no better than $`\beta ^n`$. Suppose instead we implement the game by distributing entangled two-particle states between either all enumerated pairs of players or nearest neighbors, as described in Sec. IV.3 and Sec. IV.4, respectively. In these cases, we expect that the mean number of trials needed to complete the game will scale as either $`n(n1)/2\beta `$ or $`n/\beta `$, and are therefore relatively easier to implement for games with a large number of players.

For example, in the simplest near-term implementation, a single game system can be constructed at a central location, and players can travel to the game and individually specify the operators to be applied to their qubits. As the technology evolves, the necessary hardware for specification of qubit operations can be distributed to distant players, who then can apply their operators to photonic qubits transported to them over an optical network. In either case, entangled pairs can be generated and distributed consecutively until all players have successfully registered a choice for each pair in which they are a member. Although great strides continue to be made in multi-particle experiments Bouwmeester et al. (1999); Pan et al. (2001b), it is clear that — until $`\beta 1`$ — two-particle games are far more feasible, and could allow tests of quantum game theory to be performed in the near future.

Given some single-trial success probability $`\beta `$, the number of trials is limited by the rate at which two-particle entangled qubits can be provided. A bright source of entangled photon pairs has been constructed using an argon-ion laser and parametric down-conversion in BBO crystals, capable of producing 140 detected two-photon coincidences per second per milliwatt of Ar<sup>+</sup> pump power Kwiat et al. (1999). In principle, given an electrically-driven source of single photons Yuan et al. (2002), entangled photon pairs also could be generated in a compact all-solid-state system using down-conversion in periodically-poled lithium niobate waveguides Tanzilli et al. (2001); Mason et al. (2002). However, in the future it is possible that up to $`10^9`$ pairs per second could be produced using a single quantum dot embedded in a *p*-*i*-*n* junction surrounded by a microcavity Benson et al. (2000).

## III Public Goods Economics

### III.1 Overview

A pure market economy fails to provide efficient levels of public goods for two key reasons. By definition, a public good is non-excludable. Once the good is provided, there is no means of charging for it or restricting access to it. This creates the free rider problem in which people are tempted to use the public good without paying for it. The prisoner’s dilemma is a perfect illustration of this free-rider problem. In this two-person game, each player has the choice to “cooperate” and “defect”. Payoffs for both players are higher when both of them choose to cooperate instead of defect. However, each individual is better off by defecting.

Furthermore, even if there exists a third party (usually the government) to enforce contribution to the public goods, individuals have the incentive to hide their preferences on how much they value the public good. This information asymmetry makes it difficult to determine the efficiency of public goods distribution.

Some of these issues have been addressed in economics literature. For example, if the public good can be provisioned through a government, there exist mechanisms to reveal preferences of individuals Groves and Ledyard (1977). Also, experimental work on public goods Ledyard (1995) compares people’s actual behaviors to the predictions of game theory.

The free rider problem, however, is more difficult to overcome. In the absence of a benevolent dictator, self-motivation becomes the dominant factor. Luckily, two phenomena mitigate the effects of free riding. The first is the folk theorem Rasmusen (1989); Aumann and Hart (1992). If the game is played repeatedly within a relatively small group, the folk theorem suggests an efficient outcome may be enforceable through the strategy of punishing a defector. It is arguable whether this will work in practice because game theory rationality places a strong burden on the individuals to determine the correct strategies. The second phenomenon is individuals’ motivations may not be completely selfish: experimental evidence suggests people may be altruistic, at least in relatively small groups Ledyard (1995). However, ensuring an efficient outcome is not possible without the intervention of a third party.

### III.2 Formulating Public Goods Games

For simplicity in discussing the public goods game, we assume there is only one public good and one private good which players can use to contribute to producing the public good. It is easy to generalize to multiple goods.

There are $`n`$ players indexed by $`k`$. We make the following definitions:

amount of public good

initial endowment of private good of player $`k`$

contribution of player $`k`$

utility of player $`k`$ when consuming $`x`$ units of public good and $`y`$ units of private good

production function of the public good as a function of total contributions $`C=_kc_k`$

If contribution is voluntary and continuous, each individual would want to choose a contribution to maximize:

$$\underset{c_k}{\mathrm{max}}Q_k(g(c),y_kc_k)$$
(1)
which leads to

$$\frac{1}{dg/dc}=\frac{dQ_k/dx}{dQ_k/dy}$$
(2)
for all $`k`$ when evaluated at the maximizing choices with $`x=g(c)`$ and $`y=y_kc_k`$. These give $`n`$ equations for the $`n`$ contribution values $`\{c_k\}`$.

This condition says each person will contribute up to the point where the marginal rate of substitution is equal to the marginal benefit of his contribution in providing the public good.

We use the standard economic efficiency measure of Pareto optimality Kreps (1990). That is, there exists no other allocation such that one player is strictly better off while all others are at least as well off as before. In our context, Pareto efficiency requires Kreps (1990)

$$\frac{1}{dg/dc}=\underset{k}{}\frac{dU_k/dx}{dU_k/dy}$$
(3)
Let $`C`$ be the Pareto efficient level of total contribution and $`C^{}`$ be the equilibrium level of total contribution. The above two conditions mean that $`g^{}(C)<g^{}(C^{})`$.

For well-behaved $`g`$ with diminishing rate of return, $`C>C^{}`$. Thus the equilibrium level of contribution is less than the efficient level. This analysis assumes the players’ contribution choices are continuous. However, similar results follow if contributions are restricted to discrete levels. For less well behaved $`g`$, there may be multiple equilibria as well as contribution levels at the efficient levels.

### III.3 An Example

We use a simple example that illustrates the core issue of the free-rider problem. Assume $`Q_k(x,y)=x+y`$ for all $`k`$ and $`g(c)=aC/n`$ where $`a`$ is a parameter and $`C`$ is the total contribution level. That is, $`C=_kc_k`$.

It can be shown quite easily that the following characterizes the unique Nash equilibrium:

* If $`a<1`$, $`C=0`$ and this is the Pareto efficient outcome
* If $`1<a<n`$, $`C=0`$, but is an inefficient outcome. One efficient outcome in this case is $`c_k=y_k`$ but this is not an equilibrium since each player increases payoff by defecting, i.e., switching to $`c_k=0`$.
* If $`n<a`$, $`c_k=y_k`$ is the efficient outcome.

This analysis can be interpreted as follows. The production function $`g`$ multiplies the total contribution by $`a`$. The result is then equally divided back to the players. If $`a`$ is less than 1, there is no gain to produce the public good and so the efficient outcome is not to produce any. If $`a`$ is greater than $`n`$, then for each unit the player receives back more than the contribution, thus it is advantageous to contribute and the equilibrium will be efficient.

The interesting case, giving a social dilemma, is when $`a`$ is between 1 and $`n`$. In this case, the public good per person increases with contribution. However, the marginal benefit of each contribution is still smaller than 1. Thus a player receives only $`a/n`$ in benefit for a unit of additional contribution, which is a net loss. Therefore, it is rational not to contribute. However, failure to contribute is an inefficient outcome. Thus we have a social dilemma in that the group as a whole is better off if all contribute, but each person prefers not to contribute and hence their rational choices lead to no public good production. Moreover, this case has multiple Pareto efficient outcomes. For example, both total contribution and total contribution from all but one person are efficient outcomes.

### III.4 Heterogeneity and Asymmetric Information

In the case of total contribution, it is also easy to show that for some set of $`\{y_k\}`$, one or more individuals will be worse off than the case of no contribution.

Thus an efficient outcome may not be desirable for other reasons, such as voluntary participation constraints (some players do not want to play the game). To address this issue, we will focus our attention on a smaller set of efficient outcomes that also satisfy the voluntary participation constraints. Thus, in additional to Pareto efficiency, we also require $`Q_k(g(C),y_kc_k)Q_k(g(0),y_k)`$ for all $`k`$, i.e., each person will also be better off in this efficient outcome then the no contribution case. For our example, this implies

$$\frac{a}{n}\underset{j=1}{\overset{n}{}}c_jc_k$$
(4)
for all $`k`$. The following contribution profile is efficient and satisfies Eq. (4):

$$c_k=\{\begin{array}{cc}y_k\hfill & \text{if }y_k<C^{}\hfill \\ C^{}\hfill & \text{if }y_kC^{}\hfill \end{array}$$
(5)
where

$$C^{}=\frac{a}{nan+am}\underset{j=1}{\overset{m}{}}y_j$$
(6)
where $`y_k`$ is sorted in ascending order and $`m`$ is the largest integer less than $`n`$ for which $`C^{}y_k`$ holds for all $`k=1\mathrm{}m`$.

Under this additional constraint, if the distribution of wealth is narrow (specifically, $`a\overline{y}y_k`$ for all $`k`$ where $`\overline{y}=\frac{1}{n}_ky_k`$ is the mean value of the private goods), then everyone should contribute everything. If there is a wider distribution of wealth, then there is a cut-off point $`C^{}`$. Everyone should contribute everything if their wealth $`y_kC^{}`$ and contribute only up to $`C^{}`$ if their wealth is more than $`C^{}`$. Thus to maintain voluntary participation the rich should contribute more in absolute terms than the poor, but less in percentage terms.

If wealth is distributed narrowly, (satisfying Eq. (4) if individual contributes everything) then there is no need for asymmetric contribution. Therefore, it is sufficient to treat the problem as if wealth is equal.

However, if condition Eq. (4) is not satisfied, a new incentive issue arises. To be able to solicit the “correct” amount of contribution from every individual, we not only need to solve the free-rider problem, but also correctly identify the wealth level of every individual. Furthermore, individuals have incentives to pretend to be poorer than they are to minimize their contributions.

The following example illustrates these issues. Consider a population with two levels of wealth: $`m`$ individuals have initial wealth $`y`$ and $`nm`$ individuals have wealth $`\alpha y`$ where $`\alpha >1`$. We are interested in the issue of whether a mechanism can achieve an equilibrium that is not only efficient, but also satisfies the voluntary participation constraint. The only interesting cases are where the contribution strategy is asymmetric. That is, not every individual has to contribute everything in the desirable allocation. One interesting case is where $`m=n1`$ (with only one high-wealth individual). In this case, it can be shown that the desirable allocation is everyone with the lower wealth contributes everything. The person with wealth $`\alpha y`$ should not contribute everything if $`\alpha >\frac{a(n1)}{(na)}`$. He should contribute $`\frac{ay(n1)}{na}`$.

## IV A Quantum Mechanism for Public Goods Provisioning

We first characterize equilibria of the quantum game of the homogeneous version of the public goods game. This allows us to study several configurations, such as different entanglement and interpretation of the qubits, of the quantum game. Subsequently, the results in the simple homogeneous case will be extended to the heterogeneous case.

For the quantum mechanism, each player can choose either to contribute nothing ($`c_k=0`$, “defect”) or everything ($`c_k=y`$, “cooperate”). We can also consider an intermediate case in which players can select from a discrete range of contribution values, $`0,y/K,2y/K,\mathrm{},y`$ for various choices of $`K`$, but in our case allowing such intermediate contributions gives lower average payoffs for the strategies we present below.

Here is an example of the intermediate case. For $`n=3`$ players and using 3 bits to specify discrete choices: either contribute fully ($`c_k=y`$, “cooperate”) or contribute nothing ($`c_k=0`$, “defect”), there are 8 states. Suppose we let the value 0 correspond to “cooperate”. Then the payoffs to the three players are (using $`y=1`$)

$$\begin{array}{cccc}000& a& a& a\\ 001& 2a/3& 2a/3& 2a/3+1\\ 010& 2a/3& 2a/3+1& 2a/3\\ 011& a/3& a/3+1& a/3+1\\ 100& 2a/3+1& 2a/3& 2a/3\\ 101& a/3+1& a/3& a/3+1\\ 110& a/3+1& a/3+1& a/3\\ 111& 1& 1& 1\end{array}$$
(7)
The quantum version of the game is set up as follows: first create entangled qubits (with 0 and 1 representing cooperate and defect, respectively), allow the individuals to operate on their individual qubit, then combine the result (by undoing the initial entangling operation). To preserve the correspondence with the original game, the entanglement operator should commute with those quantum operations corresponding to the classical choices. The final measurement gives a definite value for each qubit, which then corresponds to the individuals’ choices.

In general, players are allowed to apply any operator to their qubit(s). We consider general single-qubit operators, given by

$$U(\theta ,\varphi ,\alpha )=\left(\begin{array}{cc}e^{i\varphi }\mathrm{cos}\frac{\theta }{2}& e^{i\alpha }\mathrm{sin}\frac{\theta }{2}\\ e^{i\alpha }\mathrm{sin}\frac{\theta }{2}& e^{i\varphi }\mathrm{cos}\frac{\theta }{2}\end{array}\right)$$
(8)
up to an irrelevant overall phase factor. (A further generalization would allow measurements on the single qubit. This gives no advantage in at least in some cases Benjamin and Hayden (2001).)

For $`n=2`$, this reduces to the Prisoner’s dilemma, which has a nice interpretation in terms of conventional mechanisms. Entangled states allow player 1 to affect the final outcome produced by the action of player 2 and vice versa. In a way, it allows for pre-commitment. Consider the following argument. Player 1 would love to tell player 2 that if player 2 commits to cooperate, then he would also cooperate. However, without playing a repeated version of the game, the ability to punish the other player or without a 3rd party to enforce the commitment, both players will realize immediately they are better off reneging their commitments. Entanglement allows the parties to commit without a third party to enforce the commitments.

The expected payoffs can be viewed as functions of the players’ choices and game definition: $`P_k(U_1,\mathrm{},U_n;J,a)`$ (where we take $`y=1`$ without loss of generality since it just rescales the payoffs).

### IV.1 Equilibria for the Quantum Public Goods Game

In this section, we characterize equilibria for three schemes of entanglement of the public goods quantum mechanism. If players are allowed to use any single qubit operators given by Eq. (8), there is no single pure strategy equilibrium. However, we found mixed strategy equilibria, with expected payoffs depending on the degree of entanglement provided in the initial state. In each case, we find multiple equilibria. These payoffs are superior to that produced by the classical game in which all players defect so no public good is produced.

We assume all individuals are risk-neutral expected utility maximizers. Player $`k`$’s expected payoff function is given by $`P_k(\psi )=_sP_k(s)|\psi (s)|^2`$ where $`P_k(s)`$ is the payoff for player $`k`$ given the choices specified by state $`s`$.

We use the Bayesian Nash equilibrium as the solution concept for the quantum game. Each individual will play a strategy (pure or mixed) such that they are mutually maximizing their expected payoff. None has the incentive to make a unilateral change to their strategy.

A single-player operator $`\widehat{u}`$ forms a symmetric Nash equilibrium if for any other choice $`u\widehat{u}`$

$$P_k(\psi (\widehat{u},\mathrm{},\widehat{u}))P_k(\psi (\widehat{u},\mathrm{},\widehat{u},u,\widehat{u},\mathrm{},\widehat{u}))$$
(9)
for all players $`k`$, with $`u`$ substituted for the $`k^{th}`$ player’s choice on the right-hand side. For homogeneous preferences, it is sufficient that this hold for just one player. More generally, asymmetric equilibria involve possibly different operations for each player.

Whether such an equilibrium exists, and if so whether it is unique and gives the optimum payoffs for the players, depends on the set of allowed operations, the amount and type of entanglement (specified by the choice of $`J`$) and the nature of the payoffs.

Our analysis includes mixed strategy equilibria since in many cases, particularly with respect to the quantum version of the public goods game, there is no pure strategy equilibria. The strategic space for quantum games are infinite. We limit our attention to finite mixed strategies. That is, we only allow individuals to randomly (with any probabilities assignment) choose within a finite set of operators. We also make the standard assumption that individuals have access to a perfect randomization process.

In the next three subsections, we report three different schemes of entanglement and their corresponding mixed-strategy Nash equilibrium.

### IV.2 Full Entanglement

A conceptually simple approach allows arbitrary entanglement among the players’ qubits. As one example, consider fully entangled states. The initial entangled state is $`(|00\mathrm{}0+i|11\mathrm{}1)/\sqrt{2}`$, using the $`2^n\times 2^n`$ entanglement matrix

$$J_n=\frac{1}{\sqrt{2}}(I+i\sigma _x\mathrm{}\sigma _x)$$
(10)
where the product in the second term consists of $`n`$ factors of $`\sigma _x`$, the $`2\times 2`$ Pauli matrix $`\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)`$.

Allowing general single-bit operators of Eq. (8), we find no pure strategy Nash equilibrium for the players. However, there are a variety of mixed strategy equilibria. As one example, let

$`u(0)`$ $``$ $`U(0,0,0)=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)`$ (11)
$`u(1)`$ $``$ $`U(0,\pi /2,0)=\left(\begin{array}{cc}i& 0\\ 0& i\end{array}\right)`$
Note $`u(0)`$ corresponds to the classical “cooperate” option. A mixed strategy consisting of each player randomly selecting $`u(0)`$ or $`u(1)`$, each with probability $`1/2`$, gives expected payoff of $`(1+a)/2`$. This is an equilibrium: if any one player switches to using a different operator, or different mixture of operators, the expected payoff for that player remains equal to $`(1+a)/2`$. While this payoff is less than the efficient outcome, it is substantially better than the classical outcome with payoff of 1 since all choose to defect.

Although this scheme is not practical with respect to implementation due to its use of highly entangled states, we include it as a comparison to other schemes.

### IV.3 Two-particle Entanglement

Full entanglement is difficult to implement as $`n`$ increases, particularly for qubits communicated over long distances. Thus we consider restricting entanglement to only pairs of qubits. In this case, we suppose each pair of players has a maximally entangled pair, so each player has $`n1`$ qubits.

The entanglement matrix for a case consisting of $`N=\left(\genfrac{}{}{0pt}{}{n}{2}\right)`$ pairs is

$$J_{\mathrm{pair}}(N)=J_2\mathrm{}J_2$$
(12)
with the product consisting of $`N`$ factors of the entanglement operator of Eq. (10) for the case of $`n=2`$, i.e., full entanglement among two qubits.

With multiple bits per player, we also need to specify how the final measured state is to be interpreted. One approach is to allow various amounts of contribution rather than all or none. That is, if $`z`$ of the $`n1`$ bits for player $`k`$ are 0, player $`k`$’s contribution is $`c_k=yz/(n1)`$, ranging from 0 to $`y`$. So instead of two choices, the player has a range of possible contributions. This choice gives the same result as the fully entangled case: the mixed strategies have expected payoff of $`(1+a)/2`$ and remain weak equilibria.

For example, $`n=3`$ uses six qubits corresponding to the pairs of players $`(1,2)`$, $`(1,3)`$ and $`(2,3)`$, as shown in Fig. 1. Thus, for example, the first player operates on the first and third qubit in this ordering of the bits. The state $`|0,0,0,1,1,1`$ has $`0,0`$ for the first and third qubit, so the first player has $`z=2`$ and contributes $`y`$. The second player, using the second and fifth bits, has $`0,1`$ with $`z=1`$ and contributes $`y/2`$.

An alternate interpretation of the bits provides higher payoffs while maintaining the same mixed strategy equilibria. Specifically, we again suppose contributions are all or nothing but now consider the player to contribute if any of the $`n1`$ bits equals 0. This simple change in the construction of the game gives expected payoff equal to

$$a2^{(n1)}(a1)$$
(13)
which, since $`1<a<n`$, is only slightly less than the highest possible payoff, $`a`$. As examples, the expected payoffs for $`n=3`$ and $`4`$ are, respectively, $`(1+3a)/4`$ and $`(1+7a)/8`$. As $`n`$ increases, the expected payoff approaches the optimal value.

We could also consider other interpretations, e.g., full contribution if a majority of the bits are 0, and otherwise no contribution.

Significantly, the mixed strategy remains an equilibrium even if a player applies different operators to each of the $`n1`$ bits.

### IV.4 Two-particle Entanglement with Neighbors

Two-particle entanglement among all possible pairs of players requires $`n(n1)/2`$ entangled pairs. While significantly easier to implement than entanglement among $`n`$-players, we can also consider behavior with even less entanglement. Specifically, consider the players in some arbitrary order and only provide an entangled pair between successive players in that order (with an additional pair between the first and last). This entanglement requires only $`2n`$ qubits.

This case maintains the same equilibrium mixed strategies. If we interpret the two bits of each player as allowing partial contributions, the expected payoff remains $`(1+a)/2`$. Using the all-or-none method, where a player contributes everything if at least one of the two bits equals 0, the payoff is $`(1+3a)/4`$ for all $`n`$. Note this is the same as the payoff of the full two-particle case, Eq. (13), for $`n=3`$ (as expected: for $`n=3`$ the neighbor pairs are the same as a two-particle entanglement between all pairs of players).

Again, the payoff is superior to the classical game Nash equilibrium. Unlike entanglement among all pairs, the payoff does not improve with larger $`n`$. Thus this result illustrates a tradeoff: lower performance when using fewer pairs.

### IV.5 Generalization to Heterogenous Individuals

The issue of heterogenous wealth is largely ignored in our analysis of the quantum game. If the distribution of wealth is narrow (as defined in Sec. III.4), an efficient quantum solution that assumes homogeneous wealth will also satisfy the voluntary participation constraints making heterogeneity a non-issue.

Furthermore, if the issue of adverse selection (incentive to hide information) is addressed by some other method, then the quantum mechanism can be used in tandem to address the general case. Specifically, in the case of heterogenous wealth, if every individual’s wealth is revealed to the mechanism, then the mechanism can be modified slightly by the following method to yield the desirable outcome. First calculate the optimal contribution for every individual based on the revealed wealth levels as described in Sec. III.4. Then the players play the quantum game with the knowledge that the final qubits are interpreted as follows: an individual contributes the optimal amount, not his total wealth, if one or more of his qubits are zero. Essentially, all the contribution levels are pre-determined and the issues reduce to just the free-rider problem.

## V Conclusion

Quantum mechanics can be used to develop new formulation of classical economics games which give arise to new solutions. In this paper, we have shown how a quantum mechanism can be constructed to solve the free-rider problem in the public goods game, without the need of third party enforcement nor repeated play. Implementation issues are also explored and addressed.

Most of the power of this new mechanism comes from entangled states, which in theory allow individuals to co-ordinate and commit in environments when classical means do not. Incidentally, entanglement is also the major issue determining whether a quantum mechanism is practical or not.

Three different schemes of entanglement are explored. We found that two-particle entanglement, which is feasible for the near future, can also solve the free-rider problem and achieve nearly efficient outcomes. Furthermore, we have also argued that the mechanism is robust with respect to limited amount of heterogeneity in the system if there is no adverse selection.

Game theoretic solutions (such as the Bayesian Nash equilibrium we discuss in this paper) are at best approximations of real human behavior. In this case, rationality dictates that each individual has a full understanding of the quantum mechanical implications of his choices. How well this describes the actual behavior of people involved in quantum games is an interesting direction for future work with laborabory experiments involving human subjects.

There are many natural extensions of this research. First, people may use criteria other than expected payoff, e.g., to minimize variance in payoff if they are risk adverse. Second, the case of heterogeneous players and adverse selection requires further analysis. This work also suggests experimental research, exploring the issues of practicality of implementation and human behavior with respect to manipulating quantum states.

## Acknowledgments

We thank Bernardo Huberman, Alan Karp, Phil Kuekes and Wim van Dam for helpful discussions.

## Appendix A Derivation of Mixed Strategy Payoff

This appendix derives Eq. (13) and shows the mixed strategy is indeed an equilibrium: no single player can benefit from deviating from the mixture. A similar derivation applies to the other cases with different entanglement (i.e., full or two-particle only among neighbors) and interpreting multiple bits per player as indicating partial contributions. For simplicity, we take the private good value to be $`y=1`$.

Consider the behavior of player 1, selecting operators $`u^{(2)},\mathrm{},u^{(n)}`$ while all other players select either $`u(0)`$ or $`u(1)`$ of Eq. (11) with equal probability for all their bits. The initial state $`J_{\mathrm{pair}}(N)(1,0,\mathrm{},0)`$ is

$$\frac{1}{\sqrt{2}}(1,0,0,i)$$

with one factor for each pair. Subsequent operations on each pair are independent. Consider the pair between players $`j,k`$. If these players use operators $`A`$ and $`B`$ respectively, the final state for their pair is

$$\psi _{\mathrm{pair}}(A,B)=J_2^{}(AB)\frac{1}{\sqrt{2}}(1,0,0,i)$$
(14)
Players other than the first use either $`u(0)`$ or $`u(1)`$. Evaluating the products in Eq. (14) for these cases gives

$`\psi _{\mathrm{pair}}(u(0),u(0))`$ $`=`$ $`(1,0,0,0)`$ (15)
$`\psi _{\mathrm{pair}}(u(0),u(1))`$ $`=`$ $`(0,0,0,1)`$
$`\psi _{\mathrm{pair}}(u(1),u(0))`$ $`=`$ $`(0,0,0,1)`$
$`\psi _{\mathrm{pair}}(u(1),u(1))`$ $`=`$ $`(1,0,0,0)`$
so players making the same choice produce a pair equal to $`\pm |00`$ (i.e., both cooperate), while those making opposite choices give $`|11`$ (i.e., both defect).

For a given instance of this mixed strategy, let $`t_k\{0,1\}`$ indicate the operator choice of player $`k=2,\mathrm{},n`$: $`u(t_k)`$. Then the final state for the pair involving players $`j`$ and $`k`$ is just $`\psi _{\mathrm{pair}}(u(t_j),u(t_k))`$. Thus the portion of the final state corresponding to pairs not involving player 1 is

$$\psi _{\mathrm{other}}=\underset{j,k}{}\psi _{\mathrm{pair}}(u(t_j),u(t_k))$$

with the tensor product over all pairs $`2j<kn`$. The nonzero components of this vector are all $`\pm 1`$, which have unit magnitude so do not affect the probabilities of the final measurement.

The pair involving players 1 and $`k`$ gives $`v^{(k)}(t_k)=\psi _{\mathrm{pair}}(u^{(k)},u(t_k))`$. For any choice of operator $`u^{(k)}`$, evaluating Eq. (14) using Eq. (11) gives

$`v_{0,0}^{(k)}(1)`$ $`=`$ $`v_{1,1}^{(k)}(0)`$ (16)
$`v_{0,1}^{(k)}(1)`$ $`=`$ $`v_{1,0}^{(k)}(0)`$
$`v_{1,0}^{(k)}(1)`$ $`=`$ $`v_{0,1}^{(k)}(0)`$
$`v_{1,1}^{(k)}(1)`$ $`=`$ $`v_{0,0}^{(k)}(0)`$
so, apart from some sign changes, player $`k`$ switching from $`u(0)`$ to $`u(1)`$ simply reverses the result of the two-particle interaction between players 1 and $`k`$.

The overall final state is the tensor product of these results for the individual pairs. The nonzero components of this state vector are specified by the values for the bits involving player 1. That is, the final state has the form

$$\underset{k=2}{\overset{n}{}}\left(\underset{x_k,y_k}{}v_{x_k,y_k}^{(k)}(t_k)|x_k,y_k\right)\psi _{\mathrm{other}}$$

with the $`x_k,y_k`$ each summed over 0 and 1.

Measuring this final state produces a state with definite values for the $`x_k,y_k`$, with probability $`\mathrm{Pr}(x,y,t)=_{k=2}^n|v_{x_k,y_k}^{(k)}(t_k)|^2`$. For this state, we determine the payoff to player 1 as follows.

First, the all-or-none interpretation of the bits means player 1 contributes $`1`$ if any of the $`x_k=0`$. Defining the indicator function $`\chi (p)`$ to equal 1 when the proposition $`p`$ is true and 0 otherwise, we can write this contribution as $`1_k\chi (x_k=1)`$.

The contribution for player $`k>1`$ is $`1`$ if it has a 0 bit in its pair with player 1 (i.e., $`y_k=0`$) or at least one player (other than players 1 or $`k`$) makes the same choice of operator as player $`k`$ (since then Eq. (15) shows that pair of players will have value $`|0,0`$ so, in particular, player $`k`$ will have at least one of its bits equal to zero). Let $`n_b`$ be the number of players $`2,\mathrm{},n`$ that select operator $`u(b)`$, for $`b=0,1`$. Note $`n_b`$ is the number of values in $`t_2,\mathrm{},t_n`$ equal to $`b`$, and $`n_0+n_1=n1`$. With these definitions, the contribution of player $`k`$ is $`\chi (y_k=0n_{t_k}=1)+\chi (n_{t_k}>1)`$.

Combining the contributions from all players, the payoff $`P_1(x,y,t)`$ to player 1 for this measured state, is then of the form $`\frac{a}{n}(1+A)+(1\frac{a}{n})B`$ with

$`A`$ $`=`$ $`{\displaystyle \underset{k}{}}\left(\chi (y_k=0n_{t_k}=1)+\chi (n_{t_k}>1)\right)`$
$`B`$ $`=`$ $`{\displaystyle \underset{k}{}}\chi (x_k=1)`$
In this expression, $`_k\chi (n_{t_k}>1)`$ can be written as $`_{t=0}^1\chi (n_t>1)_k\chi (t_k=t)=_tn_t\chi (n_t>1)`$.

The expected payoff for player 1 for the given choices of the other players (as specified by the $`t_k`$ values) is $`_{x,y}\mathrm{Pr}(x,y,t)P_1(x,y,t)`$.

Finally, the mixed strategy used by the other players means each of the $`2^{n1}`$ choices for the values of the $`t_k`$ is equally likely, and must be summed over to get the expected payoff of player 1 when the others use the mixed strategy: $`P_1=2^{(n1)}_{x,y,t}\mathrm{Pr}(x,y,t)P_1(x,y,t)`$.

In the sum over $`x,y`$, only the factor $`|v_{x_k,y_k}^{(k)}(t_k)|^2`$ in $`\mathrm{Pr}(x,y,t)`$ depends on $`x_k,y_k`$. Thus for terms involving player $`k`$, the remaining factors in $`\mathrm{Pr}(x,y,t)`$ sum to 1 since the $`v^{(k)}(t_k)`$ are normalized vectors.

Thus $`P_1`$ is a sum of three terms. The first is

$$2^{(n1)}\frac{a}{n}\underset{t}{}(1+n_0\chi (n_0>1)+n_1\chi (n_1>1))$$

or

$$\frac{a}{n}(1+(n1)(12^{2n}))$$

The second term is

$$2^{(n1)}\frac{a}{n}\underset{k,t,x_k,y_k}{}|v_{x_k,y_k}^{(k)}(t_k)|^2\chi (y_k=0n_{t_k}=1)$$

For $`n_{t_k}=1`$, the only terms contributing to the sum over $`t`$ are those for which $`t_jt_k`$, for all $`jk`$, i.e., there are just two cases: $`t_k=0`$ and the rest are 1, and vice versa. So this term becomes

$$2^{(n1)}\frac{a}{n}\underset{k}{}\underset{t=0}{\overset{1}{}}\underset{x_k}{}|v_{x_k,0}^{(k)}(t)|^2$$

The inner two sums give $`|v_{0,0}^{(k)}(0)|^2+|v_{1,0}^{(k)}(0)|^2+|v_{0,0}^{(k)}(1)|^2+|v_{1,0}^{(k)}(1)|^2`$ which, from Eq. (16), equals $`_{x,y}|v_{x,y}^{(k)}(0)|^2=1`$ since the $`v^{(k)}`$ vectors are normalized. Thus this term is $`2^{(n1)}\frac{a}{n}(n1)`$.

Similarly, Eq. (16) gives the third term equal to $`2^{(n1)}\left(1\frac{a}{n}\right)`$.

Combining these results, $`P_1`$ is $`a2^{(n1)}(a1)`$. This result is independent of the operators selected by player 1, i.e., the values of the $`v^{(k)}`$.

Other choices for the mixed strategy operators $`u(0),u(1)`$ are possible as well. They need only satisfy Eq. (15) (up to an overall phase factor) and also compensate for any choices made by the first player via Eq. (16), again up to overall phase factors.