text:
# On the phase of oscillatory microwave photoresistance and zero-resistance states

(19 June 2003)

## Abstract

We present phenomenological analysis of the period and the phase of oscillatory microwave photoresistance (OMP) and zero-resistance states (ZRS) recently observed in 2D electron systems. The results demonstrate that as OMP evolves into ZRS with increasing magnetic field, the absolute value of the phase becomes progressively smaller, decreasing roughly as $`1/B`$. Virtually eliminating a phase-shift and resulting in different periodicities for the maxima and minima, such specific dependence is supported by a simple model based on oscillatory density of states. Finally, it follows that fine structures first reported in Ref. 3 can be viewed as an experimental evidence for multi-photon processes.

Using innovative microwave (MW) photoconductivity spectroscopy of 2D electron systems (2DES) originally employed in experiments on oscillatory microwave photoresistance (OMP), two research groups have recently reported on a series of “zero-resistance states” (ZRS) emerging from the OMP minima in ultra-high quality samples. Manifesting a novel dissipationless regime, such states appear when the MW frequency, $`\omega =2\pi f`$, somewhat exceeds the cyclotron frequency, $`\omega _c=eB/m`$, of the 2DES ($`m`$ is the effective electron mass) and are characterized by an exponentially small low-temperature resistance and a classical Hall resistance. More recently, experiments have been extended to probe dc conductivity in Corbino rings of 2DES revealing “zero-conductance states” (ZCS), in agreement with standard dc magneto-transport tensor relation. Discovery of ZRS has triggered a surge of theoretical interest and has been confirmed in independent experiments. As it was realized that even the mechanism of the original OMP lacks understanding, the first step forward was made by Durst et al who related the phenomenon to radiation-induced impurity-assisted scattering (in fact, similar ideas were proposed decades ago by Ryzhii.). Regardless of the microscopic nature of the OMP, it was established experimentally that the sample mobility favors OMP amplitude at the same time reducing background resistance. Therefore, one could intuitively expect that further improving sample quality would eventually lead to zero or even negative resistance at the OMP minima. As the later scenario is not experimentally realized, Andreev et al presented strong arguments showing that a negative resistance(conductance) state, regardless of its origin, is intrinsically unstable. This instability leads to formation of current(electric field) domains which give rise to ZRS(ZCS). As there are no new experiments available to date to test these or other theories, current understanding of the phenomenon appears far from complete. Furthermore, while there seems to be a consensus about the period of the ZRS, the value of the phase seems to be controversial, even experimentally. Since the majority of proposed OMP(ZRS) models seem to account for, and some \[see, e.g. Ref. 2\] even rely on a specific value of the phase, we feel that it would be useful to address the origin of this discrepancy.

In this paper we present detailed analysis of the period and the phase of the OMP/ZRS, which, we hope, complements original experimental findings. The results indicate that evolution of the OMP into ZRS with increasing magnetic field is accompanied by a dramatic reduction of the phase. We find that in the ZRS regime the phase decreases roughly as $`1/B`$ and such dependence virtually eliminates a “$`1/4`$-cycle” phase shift attributed to ZRS by the authors of Ref. 2. While a specific origin of such a dependence is not clear at this point, we show that, under reasonable assumptions, it is consistent with an idea that MW photoresistance roughly follows the derivative of the density of states (DoS). Finally, we show that fine structures first reported in Ref. 3 can be viewed as an experimental evidence for multi-photon processes.

One of the puzzles surrounding experimental reports is that, despite a great deal of similarity between the data presented in Ref. 2 and that of Ref. 3, conclusions regarding the phase of the ZRS were quite different. Mani et al have found the positions of the maxima/minima (<sup>±</sup>, respectively) of both the OMP and ZRS to be described by:

$$\epsilon _j^\pm =j1/4$$
(1)
where $`\epsilon \omega /\omega _c`$ and $`j`$ is a positive integer. According to Eq. (1) maxima(minima) appear blue(red)-shifted by a “$`1/4`$-cycle” from the cyclotron resonance harmonics, $`\epsilon _j=j`$, and the magnetoresistance can be viewed as a single-harmonic function with the phase, $`\varphi ^\pm =0.25`$.

On the other hand, Zudov et al have reported that major ($`j4`$) maxima can be roughly fitted to $`\epsilon ^+j`$. As far as the major minima are concerned, their positions, contrary to the maxima, are not well defined since ZRS span a wide range of the magnetic field. Naively one could take the ZRS center as its position but the higher temperature data and apparent asymmetry of the major maxima rule against such single-harmonic picture. Therefore, Zudov et al have proposed that ZRS could also be viewed as a roughly periodic (in $`1/B`$) sequence, with no apparent phase shift, although with a somewhat enhanced periodicity \[cf., Fig. 3 in Ref. 3\]. Here we summarize the observations of Ref. 3 as follows:

$$\epsilon _j^\pm =\alpha ^\pm j,j4$$
(2)
where $`\alpha ^\pm `$ is a constant close to unity. Higher-order ($`j4`$) OMP were found to conform to Eq. (1) although such approach required a somewhat reduced value of the effective mass ($`m_{\mathrm{lo}}=0.064m_0`$), as opposed to $`m_{\mathrm{hi}}=0.068`$ obtained using Eq. (2) for $`j4`$.

It immediately follows that, experimentally, the boundary of applicability of Eqs. (1) and (2), i.e., $`j4`$, seems to also separate the regimes of the OMP from that of the ZRS; being described by different equations MW photoresistance for $`j4`$ corresponds to the OMP regime, while ZRS appear at $`j4`$. To reconcile Eqs. (1) and (2) we propose the following expression

$$\epsilon _j^\pm =j+\varphi ^\pm ,$$
(3)
where $`\varphi ^\pm `$ is now allowed to vary with $`\epsilon `$, approaching $`0.25`$ as $`\epsilon `$ increases. In what follows, we analyse the phase, $`\varphi _j^\pm \epsilon _j^\pm j`$, extracted from our experimental data, as a function of $`\epsilon `$.

In Fig. 1(a) we present the experimental value of the phase, $`\varphi ^\pm `$, extracted from magnetoresistance traces (see inset) taken at $`T`$ = 0.9 K (solid circles) and $`T`$ = 2.7 K (open circles) for $`f=57`$ GHz. Horizontal dashed lines mark a “$``$1/4-cycle” phase-shift, which is readily observed in experiment for both maxima and minima at $`\epsilon 4`$. At $`\epsilon 4`$, positions of the minima at low temperature cannot be accurately determined and we limit our discussion to the maxima positions (as discussed later in the text, minima positions are expected to follow similar dependence). With decreasing $`\epsilon `$ we observe a dramatic reduction of $`|\varphi ^+|`$, roughly linear with $`\epsilon `$, i.e., $`\varphi ^+\beta ^+\epsilon `$, with $`\beta ^+6.4\times 10^21`$. We immediately note that, in agreement with earlier conclusions, such a dependence does not produce any phase-shift but affects periodicity \[cf., Eq. (2)\]. Indeed, substituting this result into Eq. (3) one obtains $`\epsilon ^+=j/(1+\beta ^+)(1\beta ^+)j`$ which is just Eq. (2). We can now relate the phenomenological parameter $`\beta ^+`$ to the difference between the effective masses extracted earlier from the maxima positions using Eq. (1) for $`j4`$ ($`m_{\mathrm{lo}}=0.064`$) and Eq. (2) (with $`\alpha ^+=1`$) for $`j4`$ ($`m_{\mathrm{hi}}=0.068`$). We note that completely ignoring the phase-shift results in an overestimation of the mass by approximately $`\beta ^+`$ %, consistent with the data of Fig. 1(a). While the minima positions at $`\epsilon 4`$ could be accessed at elevated temperatures, e.g. $`T`$ = 2.7 K, the extracted phase (open circles) does not seem to follow such a simple linear dependence on $`\epsilon `$. While the same is true for the maxima at this $`T`$, the origin of such enhancement of the phase remains unclear.

It is interesting to examine the extracted phase in terms of the recent theoretical proposals. Here we chose a “toy model” proposed by Durst et al who suggested that MW photoresistance roughly follows the derivative of the DoS taken at $`E=\mathrm{}\omega `$. The condition describing the positions of the maxima and minima in the OMP(ZRS) structure is then given by:

$$\frac{d^2N(E)}{dE^2}|_{E=\mathrm{}\omega }=0$$
(4)
Using a well-known fact that in weak magnetic field the oscillatory part of the DoS behaves as $`\mathrm{cos}(2\pi E/\mathrm{}\omega _c)`$, Eq. (1) is easily recovered. It is well known, however, that with increasing magnetic field, cyclotron energy will eventually exceed the Landau level (LL) width and DoS will no longer be described by a single-harmonic function. Due to this, in regular magnetotransport, Shubnikov-de Haas (SdH) effect evolves into a quantum Hall effect (QHE) with increasing magnetic field (or sample mobility). Intuitively, one could think that similar magnetic-field-driven transition might be responsible for the evolution of the OMP into ZRS. Qualitatively it is straightforward to see that as the DoS deviates from a sinusoidal form with increasing magnetic field, the phase will be reduced rendering Eq. (1) invalid and therefore irrelevant to the ZRS regime.

For quantitative comparison with experiment we assume that LLs have Lorentzian shape characterized by a field-independent width, $`\mathrm{\Gamma }`$. Then the DoS can be written as:

$$N(E)=\frac{1}{\pi ^2\mathrm{}_0^2}\underset{n}{}\frac{\mathrm{\Gamma }}{(En\mathrm{}\omega _c)^2+\mathrm{\Gamma }^2},$$
(5)
where $`n`$ denotes the LL index and $`\mathrm{}_0=\sqrt{\mathrm{}/eB}`$ is the magnetic length. Experimentally we are constrained to the case of very high LLs ($`\mathrm{}\omega E_F`$, $`E_F`$ is the Fermi energy), therefore, the summation can be taken over infinite limits yielding analytical solution. After introducing dimensionless units ($`\epsilon =E/\mathrm{}\omega _c`$, $`\gamma =\mathrm{\Gamma }/\mathrm{}\omega _c`$, and $`n(\epsilon )=N(E)\mathrm{}\omega _c\pi \mathrm{}_0^2`$), one obtains:

$$n(\epsilon )=\left[\mathrm{cos}^2(\pi \epsilon )\mathrm{tanh}(\pi \gamma )+\mathrm{sin}^2(\pi \epsilon )\mathrm{coth}(\pi \gamma )\right]^1$$
(6)
Substituting (6) in (4) (i.e., $`d^2n(\epsilon )/d\epsilon ^2|_{\epsilon =\omega /\omega _c}`$) and solving for $`\epsilon `$ one obtains Eq. (3) with the phase of the form:

$$\varphi ^\pm =\frac{1}{2\pi }\mathrm{arccos}\psi $$
(7)
where $`\psi =1/2y+\sqrt{y^2y+9/4}`$, $`y=\mathrm{cosh}^2(\pi \gamma )`$, and $`\varphi ^\pm `$ is the phase for the series of maxima/minima, respectively.

At lower magnetic fields ($`\gamma 1`$), $`y1`$, $`\psi y^11`$, so $`\varphi ^\pm 1/4`$ and Eqs. (3),(7) reduce to Eq. (1). One can also arrive at the same conclusion by noticing that in this limit, as mentioned earlier, the DoS becomes a single-harmonic function of $`\epsilon `$, i.e., $`n(\epsilon )=1+2\mathrm{exp}(2\gamma )\mathrm{cos}(2\pi \epsilon )`$.

More interesting results emerge at higher magnetic fields ($`\gamma 1`$), when LLs become well separated. In this limit, $`y1+\pi ^2\gamma ^2/2`$, $`\psi 1+2\pi ^2\gamma ^2/3`$, which leads to $`\varphi ^\pm \gamma /\sqrt{3}`$. One can also easily obtain the same result by considering an isolated Lorentzian line. We immediately note that the phase is decreasing as $`1/B`$, in agreement with experimental data plotted in Fig. 1(a), leading to $`j1/B`$ \[cf., Eq. (2)\]:

$$j=\frac{\mathrm{}\omega \pm \mathrm{\Gamma }/\sqrt{3}}{\mathrm{}\omega _c}.$$
(8)
A few comments are appropriate. First, Eq. (8) is consistent with our experimental observations regarding the positions of the major maxima and minima. Oscillation order $`j`$ for the maxima and minima scales linearly with $`\epsilon `$, with no apparent phase, but with different prefactors \[cf., $`\alpha ^\pm `$ in Eq. (2)\]; it is easy to see that since $`\gamma 1`$, $`\alpha ^\pm 1`$, as observed experimentally. Second, the asymmetry of the ZRS portion of the magnetoresistance trace can now be understood, since Eq. (8) dictates oscillations to appear as closely-spaced maximum-minimum pairs, centered about integer values of $`\epsilon =j`$. Third, since experimentally OMP ($`j4`$) and ZRS ($`j4`$) conform to different resonant conditions (Eq. (1) and Eq. (2), respectively) this model suggests that ZRS develop from the OMP minima as a result of a magnetic-field-driven transition taking place around $`\mathrm{}\omega _c/2\mathrm{\Gamma }1`$. Such a transition would roughly occur when $`\varphi ^\pm =\gamma /\sqrt{3}`$ reaches its low-field limit of $``$1/4. Indeed, it happens when $`\mathrm{}\omega _c/2\mathrm{\Gamma }=\sqrt{3}/21`$. Finally, it is interesting to mention that Eq. (8) provides a direct experimental method to probe $`\mathrm{\Gamma }`$, which is not directly accessible in standard magnetotransport, both in SdH ($`\gamma 1`$) and in QHE ($`\gamma 1`$) regime. We also mention that more detailed microscopic calculations within a self-consistent Born approximation predict similar reduction of the phase with increasing magnetic field.

Using Eq. (8) we can now relate the phenomenological parameter $`\beta `$ to $`\mathrm{\Gamma }`$, i.e., $`\mathrm{\Gamma }=\sqrt{3}\mathrm{}\omega \beta `$ 0.3 K ($`\mathrm{\Gamma }\mathrm{}\omega 2.7`$ K, as expected). We can also roughly estimate the number of developed ZRS, as $`\mathrm{}\omega /(2\mathrm{\Gamma })4`$, in agreement with experiment. Using Eqs. (3),(7) we now compute the maxima positions for the whole range of $`\epsilon `$ for comparison with experimental data. In Fig. 1(b) we present the results of such calculations shown by vertical lines along with experimental trace for $`f=57`$ GHz adopted from Ref. 3, but now replotted as a function of $`\epsilon `$. While it was shown before that Eq. (1) works well only for $`\epsilon 4`$ and Eq. (2) for $`\epsilon 4`$, Eqs. (3),(7) provide excellent agreement over the whole range of $`\epsilon `$, both in OMP and ZRS regimes. In Fig. 1(a) we now present $`\varphi ^\pm `$, calculated using Eq. (7) for $`m=0.064`$ and $`\mathrm{\Gamma }=0.3`$ K (solid lines), and again observe good agreement with low-temperature experimental data. Dashed lines crossing around $`\epsilon 4`$ represent asymptotes of Eq. (7), i.e., $`\varphi ^\pm \gamma /\sqrt{3}`$ ($`\gamma 1`$) and $`\varphi ^\pm 0.25`$ ($`\gamma 1`$). Experimentally, we observe that this crossing point roughly marks a transition from OMP to ZRS \[cf. Fig. 1(b)\]. An enhancement of the phase at higher $`T`$ can now be related to the thermal broadening of LLs.

Once we have established that OMP can be viewed as maximum-minimum pairs associated with integer $`j`$ and positioned around $`\epsilon =j`$, we can try to generalize Eq. (3) for the processes involving multiple photons. While it seems unlikely that such higher-order processes would be readily resolved experimentally, our data suggest that such a scenario deserve close examination, especially in light of recent theoretical comments. For the case of $`m`$-photon processes and $`\gamma 1`$, the maximum-minimum pairs are to appear roughly symmetrically around fractional $`\epsilon `$ and the expression (3) is modified as follows (here we do not attempt to calculate $`\varphi _{jm}`$):

$$\epsilon _{jm}^\pm =\frac{j}{m}\pm \varphi _{jm}$$
(9)
where $`m=2,3,4\mathrm{}`$ . For instance, two-photon processes ($`m=2`$) would reveal themselves as a series of maximum-minimum pairs close to half-integer values of $`\epsilon `$, e.g. 1/2, 3/2, 5/2,… . To prove the feasibility of such scenario, we present in Fig. 2(a) the magnetoresistance data taken under illumination with MW radiation of $`f=57`$ GHz but now plotted over the narrow range of $`\epsilon `$. Maximum-minimum pair centered at $`\epsilon =3/2`$ and marked by vertical arrows is clearly observed and similar structure seems to develop around $`\epsilon =5/2`$. While such secondary peaks appearing at $`\epsilon >1`$ may be possibly explained by other mechanisms, structures emerging at $`\epsilon <1`$ present stronger support for multi-photon transitions as these naturally allow to enter the region of $`\epsilon <1`$. In Fig. 2(b) we show magnetoresistance data for $`f=31.5`$ GHz and focus on the region of $`\epsilon <1`$. The structure centered around $`\epsilon =1/2`$ is comparable in amplitude to the primary single-photon structure around $`\epsilon =1`$. We notice that this feature is best observed at low MW frequencies and quickly disappears at $`f40`$ GHz as it gradually shifts into SdH regime. In addition, there appears yet another maximum-minimum pair close to $`\epsilon =2/3`$ which would suggest an even less-likely, three-photon process. Based on the good agreement of the positions, we believe that secondary peaks first observed in Ref. 3 are due to multi-photon processes as described by Eq. (9) for $`m=2`$. The test for such a conclusion would be the systematic power-dependence experiments which are deferred for future studies.

In summary, we have studied the period and the phase of the MW photoresistance over the wide range of $`\epsilon `$, covering both OMP and ZRS regimes. As OMP evolves into ZRS with increasing magnetic field we observe a dramatic reduction of the phase, which decreases roughly as $`1/B`$. Such a decrease results in different periodicities for the maxima and minima, but both exhibit no apparent phase-shift, in agreement with our earlier report. Assuming that MW photoresistance follows the derivative of the DoS, ZRS and OMP can be viewed as two different experimental regimes separated by the condition $`\mathrm{}\omega _c/2\mathrm{\Gamma }1`$. Despite obvious oversimplification, such an intuitive model seems to capture the behavior of the ZRS position/phase quite well but we do not rule out other explanations. Finally, we identify additional structures first reported in Ref. 3 as resulting from multi-photon processes taking place around fractional values of $`\epsilon `$, e.g. $`\epsilon 1/2,3/2,\mathrm{}`$ .

We would like to thank R. R. Du, V. A. Apalkov, and M. G. Vavilov for reading the manuscript and valuable remarks. This work is supported by DARPA.


format: text

text:
# Microscopic theory of the reentrant integer quantum Hall effect in the first and second excited LLs

## Abstract

We present a microscopic theory for the recently observed reentrant integer quantum Hall effect in the $`n=1`$ and $`n=2`$ Landau levels. Our energy investigations indicate an alternating sequence of $`M`$-electron-bubble and quantum-liquid ground states in a certain range of the partial filling factor of the $`n`$-th level. Whereas the quantum-liquid states display the fractional quantum Hall effect, the bubble phases are insulating, and the Hall resistance is thus quantized at integral values of the total filling factor.

Two-dimensional electron systems in a strong perpendicular magnetic field display the integer and fractional quantum Hall effects (IQHE and FQHE). perspectives  At certain values of the ratio $`\nu =n_{el}/n_B`$ of the electronic $`n_{el}`$ and the flux densities $`n_B=eB/h`$, one observes plateaus in the Hall resistance accompanied by a vanishing longitudinal magnetoresistance. The factor $`\nu `$ determines the filling of the highly degenerate Landau levels (LLs), which are due to the quantization of the electrons’ kinetic energy. At integral filling factors $`\nu =N`$ ($`N=2n`$ for the lower and $`N=2n+1`$ for the upper spin branch of the $`n`$th LL) the non-degenerate ground state, which consists of completely filled levels, is separated from the excited states by a finite gap. By increasing $`\nu `$ (e.g. via lowering $`B`$) the electrons, which are promoted to higher LLs, become localized due to residual impurities in the sample and therefore do not contribute to the electrical transport. This insulating behavior of electrons gives rise to plateaus of quantized Hall resistance at values $`R_{xy}=h/e^2N`$ (IQHE). A similar effect (FQHE) arises when the two lowest LLs $`n=0`$ and $`n=1`$ are partially filled with $`\overline{\nu }=\nu N`$. The effect is understood in terms of composite fermions (CFs), which experience a reduced coupling to the magnetic field $`(eB)^{}=eB/(2ps\pm 1)`$, where $`s`$ is the number of flux pairs carried by each CF and $`p`$ the number of completely filled CF-LLs. CF localization leads to a quantized Hall resistance at fillings $`\overline{\nu }=p/(2ps\pm 1)`$. However, contrary to the IQHE, the FQHE is entirely caused by electronic interactions. Recent experiments in the $`n=1`$ LL have revealed an intriguing reentrant IQHE (RIQHE): between the FQHE states at $`\overline{\nu }=1/5,1/3`$ and the even-denominator state at $`\overline{\nu }=1/2`$ with a quantized $`R_{xy}=h/e^2(N+\overline{\nu })`$, the Hall resistance jumps to values $`R_{xy}=h/e^2N`$, corresponding to the neighboring plateau of the IQHE. exp3  The effect is analogous to the RIQHE observed around $`\overline{\nu }=1/4`$ in the $`n=2`$ LL. exp2  One-particle localization is unlikely to be at the origin of this insulating phase at such high partial fillings. An alternative origin of the insulating phase is a pinned electron solid such as a charge density wave (CDW) or a Wigner crystal.

In this Rapid Communication we present energy calculations based on a microscopic theory, which show that the RIQHE is due to the formation of a triangular CDW ($`M`$-electron bubble phase) of electrons in the last partially occupied LL. The energy of the bubble phase is accurately calculated in the Hartree-Fock approximation (HFA) FKS ; moessner ; fogler  and is compared to the energy of the quantum liquid, which displays the FQHE, taking into account quasiparticle/quasihole excitations at fillings away from the “magical” factors $`\overline{\nu }_L=1/(2s+1)`$ with integral $`s`$.

In the high-magnetic-field limit, the Coulomb interaction between the electrons is smaller than the LL separation. Intra-LL excitations, which are possible at fractional filling factors, are therefore more important for the low-energy properties of the system than inter-LL excitations. The latter have been included in a random-phase-approximation calculation and lead to a screened Coulomb interaction in a certain wave vector range. AG  However, screening has only a minor influence on the physical properties as shown in Ref. 6, and completely filled LLs may therefore be considered inert. The electronic interactions thus remain as the only energy scale, and one obtains a system of strongly correlated electrons described by the Hamiltonian

$$\widehat{H}_n=\frac{1}{2}\underset{𝐪}{}v(q)\left[F_n(q)\right]^2\overline{\rho }(𝐪)\overline{\rho }(𝐪),$$
(1)
where $`v(q)=2\pi e^2/ϵq`$ is the two-dimensional Fourier transform of the Coulomb potential. Due to the Zeeman gap, the two branches of the levels $`n=1`$ and $`n=2`$ are completely spin-polarized.exp3 ; exp2  We therefore consider only interactions between spinless electrons within the $`n`$th LL described by the density operators $`\rho (𝐪)_n=F_n(q)\overline{\rho }(𝐪)`$, where $`\rho (𝐪)`$ is the usual electron density in reciprocal space. The factors $`F_n(q)=L_n(q^2l_B^2/2)\mathrm{exp}(q^2l_B^2/4)`$, with the Laguerre polynomials $`L_n(x)`$ and the magnetic length $`l_B=\sqrt{\mathrm{}/eB}`$, arise from the wave functions of electrons in the $`n`$th LL and may be absorbed into an effective interaction potential $`v_n(q)=v(q)[F_n(q)]^2`$. The latter may be interpreted as an interaction potential between electrons whose spatial degrees of freedom are given only in terms of their guiding-center coordinates. The non-commutativity of these coordinates leads to unusual commutation relations for the projected electron density operators, GMP

$$[\overline{\rho }(𝐪),\overline{\rho }(𝐤)]=2i\mathrm{sin}\left(\frac{(𝐪\times 𝐤)_zl_B^2}{2}\right)\overline{\rho }(𝐪+𝐤),$$
(2)
which together with the Hamiltonian (1) define the full model. We will set $`l_B1`$ in the following discussion.

The solution of the model in the HFA FKS ; moessner  has predicted a CDW ground state in higher LLs. The cohesive energy is a functional of the order parameter $`\mathrm{\Delta }(𝐪)=\overline{\rho }(𝐪)/n_BA`$, where $`A`$ is the total area of the system,

$$E_{coh}^{CDW}(n;\overline{\nu })=\frac{n_B}{2\overline{\nu }}\underset{𝐪}{}u_n^{HF}(q)|\mathrm{\Delta }(𝐪)|^2$$

with the Hartree-Fock potential $`u_n^{HF}(q)=v_n(q)u_n^F(q)`$. The Fock potential is related to $`v_n(q)`$ by $`u_n^F(q)=_𝐩v_n(p)\mathrm{exp}[i(p_xq_yp_yq_x)]/n_B`$, and one can derive an analytical expression for it,

$$u_n^F(q)\frac{4e^2}{ϵ\pi ^2n_Bq}\mathrm{Re}\left[K\left(\frac{1\sqrt{14(2n+1)/q^2}}{2}\right)\right]^2,$$

where $`K(x)`$ is the complete elliptic integral of the first kind. This formula becomes exact in the large-$`n`$ limit but scaling arguments have shown that this approximation gives sufficiently accurate results already for $`n=1`$ and $`n=2`$.goerbig2  Even if the HFA fails to describe the quantum liquid phases in the two lowest LLs, it gives correct energy estimates of states with a modulated density such as the electron-solid phases.

In order to describe the bubble phase (triangular CDW) with $`M`$ electrons per bubble, we use the ansatz $`\overline{\nu }(𝐫)=_j\mathrm{\Theta }(\sqrt{2M}l_B|𝐫𝐑_𝐣|)`$ for the local guiding-center filling factor, where the sum is over the lattice vectors of a triangular lattice. FKS  Fourier transformation of this filling factor yields the order parameter of the bubble phase

$$\mathrm{\Delta }_M^B(𝐪)=\frac{2\pi \sqrt{2M}}{Aq}J_1(q\sqrt{2M})\underset{j}{}e^{i𝐪𝐑_j},$$

where $`J_1(x)`$ is the first-order Bessel function. The cohesive energy of the $`M`$-electron bubble phase is thus

$$E_{coh}^B(n;M,\overline{\nu })=\frac{n_B\overline{\nu }}{M}\underset{l}{}u_n^{HF}(𝐆_l)\frac{J_1^2(\sqrt{2M}|𝐆_l|)}{|𝐆_l|^2},$$
(3)
where $`𝐆_l0`$ are the reciprocal lattice vectors.

The cohesive energy of the Laughlin states at $`\overline{\nu }_L=1/(2s+1)`$ can be expressed in terms of Haldane’s pseudopotentials haldane1

$$E_{coh}^L(n;s)=\frac{\overline{\nu }_L}{\pi }\underset{m=0}{\overset{\mathrm{}}{}}c_{2m+1}^sV_{2m+1}^n$$

with $`V_{2m+1}^n=2\pi _𝐪v_n(q)L_{2m+1}(q^2)\mathrm{exp}(q^2/2)`$. The expansion coefficients $`c_{2m+1}^s`$ may be obtained either from a fit of the pair-distribution function of the Laughlin states to Monte-Carlo calculations GMP ; laughlin ; levesque  or from a certain number of sum rules imposed on these coefficients, GMP ; girvin  which result in a system of linear equations. goerbig1  The latter method gives results for the energies of the quantum-liquid states which deviate less than $`1\%`$ from Monte-Carlo calculations. levesque  A systematic comparison between the Laughlin states and bubble phases in higher LLs has been published by Fogler and Koulakov. fogler  However, their analysis does not permit a comparison between the energies of the quantum-liquid and bubble phases away from $`\overline{\nu }_L=1/(2s+1)`$, and thus an explanation of the RIQHE is still lacking.

In order to investigate the energy of the quantum-liquid phase away from precisely these filling factors, one has to take into account the excited quasiparticles (for $`\overline{\nu }>\overline{\nu }_L`$) and quasiholes (for $`\overline{\nu }<\overline{\nu }_L`$). If the interactions between quasiparticles/quasiholes are neglected, one obtains for the cohesive energy of the quantum-liquid phases in the $`n`$-th LL

$$E_{coh}^{ql}(n;s,\overline{\nu })=E_{coh}^L(n;s)+[\overline{\nu }(2s+1)1]\mathrm{\Delta }^n(s),$$
(4)
where $`\mathrm{\Delta }^n(s)`$ is the energy of quasiparticles of charge $`1/(2s+1)`$ (quasiholes of charge $`1/(2s+1)`$) in units of the electron charge. $`\mathrm{\Delta }^n(s)`$ can be calculated analytically in the Hamiltonian theory recently proposed by Murthy and Shankar. MS  The Hamiltonian (1) is investigated in a CF basis using the “preferred” combination

$$\overline{\rho }^p(𝐪)=\overline{\rho }(𝐪)c^2\overline{\chi }(𝐪),$$

where $`\overline{\chi }(𝐪)`$ is the density operator of a vortex-like excitation of charge $`c^2=2ps/(2ps+1)`$ in units of the electron charge. The choice of the “preferred” combination respects the commutation relations (2) for small wave vectors, whereas the error at larger $`q`$ is suppressed by the Gaussian in the effective interaction potential. The ground state of this theory is characterized by the expectation value $`c_{n,m}^{}c_{n^{},m^{}}=\delta _{n,n^{}}\delta _{m,m^{}}\mathrm{\Theta }(p1n)`$, where $`c_{n,m}^{}`$ creates a CF in the $`n`$-th CF-LL with a CF guiding-center quantum number $`m`$. The quasiparticle energies are thus given by the expression

$$\mathrm{\Delta }_{qp}^n(s,p)=c_{p,m}\widehat{H}_nc_{p,m}^{}\widehat{H}_n,$$

and the quasihole energy is

$$\mathrm{\Delta }_{qh}^n(s,p)=c_{p1,m}^{}\widehat{H}_nc_{p1,m}\widehat{H}_n,$$

where one averages over the ground state with the help of Wick contractions. This yields

$`\mathrm{\Delta }_{qp}^n(s,p)`$ $`=`$ $`{\displaystyle \frac{1}{2}}{\displaystyle \underset{𝐪}{}}v_n(q)p|\overline{\rho }^p(𝐪)\overline{\rho }^p(𝐪)|p`$ (5)
$`{\displaystyle \underset{𝐪}{}}v_n(q){\displaystyle \underset{n^{}=0}{\overset{p1}{}}}|p|\overline{\rho }^p(𝐪)|n^{}|^2`$
and

$`\mathrm{\Delta }_{qh}^n(s,p)`$ $`=`$ $`{\displaystyle \frac{1}{2}}{\displaystyle \underset{𝐪}{}}v_n(q)p1|\overline{\rho }^p(𝐪)\overline{\rho }^p(𝐪)|p1`$ (6)
$`+{\displaystyle \underset{𝐪}{}}v_n(q){\displaystyle \underset{n^{}=0}{\overset{p1}{}}}|p1|\overline{\rho }^p(𝐪)|n^{}|^2`$
with the matrix elements

$`p|\overline{\rho }^p(𝐪)|n=\sqrt{{\displaystyle \frac{n!}{p!}}}\left({\displaystyle \frac{ql_B^{}c}{\sqrt{2}}}\right)^{pn}e^{q^2l_B^2c^2/4}`$
$`\times \left[L_n^{pn}\left({\displaystyle \frac{q^2l_B^2c^2}{2}}\right)c^{2(1p+n)}e^{q^2/2c^2}L_n^{pn}\left({\displaystyle \frac{q^2l_B^2}{2c^2}}\right)\right],`$
where $`l_B^{}=1/\sqrt{1c^2}`$ is the magnetic length for CFs. The expressions (5) and (6) are generalizations to an arbitrary LL of Murthy and Shankar’s results for $`n=0`$. MS  In $`n=1`$ and $`n=2`$, one obtains the energies of the quasiparticle excitations for the Laughlin series

| $`\mathrm{\Delta }_{qp}^n(s,p=1)`$ | $`s=1`$ | $`s=2`$ | $`s=3`$ | $`s=4`$ |
| --- | --- | --- | --- | --- |
| $`n=1`$ | 0.2267 | 0.1868 | 0.1550 | 0.1316 |
| $`n=2`$ | 0.1903 | 0.1728 | 0.1543 | 0.1376 |

and the energies of the quasihole excitations

| $`\mathrm{\Delta }_{qh}^n(s,p=1)`$ | $`s=1`$ | $`s=2`$ | $`s=3`$ | $`s=4`$ |
| --- | --- | --- | --- | --- |
| $`n=1`$ | -0.07172 | -0.07032 | -0.05887 | -0.04959 |
| $`n=2`$ | -0.07876 | -0.07853 | -0.06728 | -0.05765 |

in units of $`e^2/ϵl_B`$.

A comparison of the cohesive energies of the $`M`$-electron bubble (3) and the quantum-liquid phases (4) for $`n=1`$ and $`n=2`$ is shown in Figs. 1a, 2a. In the $`n=1`$ LL the quantum-liquid phases are energetically favorable at $`\overline{\nu }=1/3\pm 0.03`$ and below $`\overline{\nu }=1/5+0.02`$, whereas no liquid phase is found around $`\overline{\nu }=1/3`$ for $`n2`$. Note that we have neglected interactions with underlying impurities in the investigation of the bubble phases. Pinning and deformation of the CDW FL  makes these phases better adapted to follow an underlying electrostatic potential than is an incompressible, homogeneous liquid. The energy gain is more pronounced in the low-density limit, where the elasticity of the CDW is reduced due to a larger lattice constant. This leads to a shift of the curves to smaller $`\overline{\nu }`$. A detailed discussion of this effect will be published elsewhere. unpubl  At even lower filling factors, one-particle localization may also destroy the quantum-liquid phase.

These investigations explain the RIQHE, which was recently reported by Eisenstein et al. exp3  for $`n=1`$ (Fig. 1b) and which had been observed before by Cooper et al. exp2  in $`n=2`$ around $`\overline{\nu }=1/4`$ (Fig. 2b). The insulating behavior of electrons in the last LL, which is responsible for the RIQHE, may be caused by simple one-particle localization or by collective effects such as crystallization into an electron solid. Electrical transport in an electron-solid phase arises either by a collective sliding, which is suppressed by pinning due to residual impurities, or by the propagation of crystal dislocations, which is reduced in the limit $`T0`$. The observation of the RIQHE at rather high partial fillings, comparable to those at which the FQHE is found, indicates the relevance of Coulomb interactions. This favors an explanation in terms of the electron solid, i.e. $`M`$-electron bubble phases, as being responsible for the insulating behavior. This picture is supported by the energy investigations presented above.

In the $`n=1`$ LL the FQHE, as a property of the quantum-liquid phases, is observable at $`\nu =2+1/3`$ and $`2+1/5`$ (lower spin branch) and at $`\nu =3+1/3`$ and $`3+1/5`$ (upper spin branch, c.f. Fig. 1b), whereas between these FQHE states the energetically favored $`1`$-electron bubble phase gives rise to the observed RIQHE. At $`\overline{\nu }1/3+0.03`$, one observes again the RIQHE caused by a $`2`$-electron bubble phase (Fig. 1a) in perfect agreement with the experiment exp3  and recent numerical density-matrix-renormalization-group studies. shibata

In the $`n=2`$ LL, the RIQHE around $`\overline{\nu }=1/4`$ is due to the existence of a $`2`$-electron bubble phase and $`3`$-electron bubbles for $`\overline{\nu }0.35`$. The small maxima in the longitudinal magnetoresistance, which are observed at $`B=2.32`$T and $`B=2.65`$T corresponding to filling factors $`\nu =4+4/5`$ and $`\nu =4+1/5`$, exp2  may indicate an incipient quantum melting of the bubble phase. Such a quantum melting is expected from the energy investigations, which indicate a quantum-liquid ground state and thus a possible observation of the FQHE at $`\overline{\nu }=1/5`$ or $`1/7`$ in $`n=2`$ (Fig. 2a). goerbig2

In higher LLs $`n3`$ (results not shown), the bubble phases are of lower energy than the FQHE state at $`\overline{\nu }=1/5`$. One observes a general shift of the quantum-liquid phases to lower partial filling factors with increasing LL index $`n`$ in agreement with results from scaling investigations. moessner ; goerbig2

In conclusion, we have presented a mechanism for the appearance of the RIQHE in the $`n=1`$ and $`n=2`$ LLs based on the comparison between the energies of the different $`M`$-electron bubble and quantum-liquid phases. Whereas the energies of the bubble phases are calculated in the HFA, which gives reliable results for electronic states with a modulated density, the quantum-liquid phases are characterized by quantum correlations beyond the mean-field level. The energies of the Laughlin liquid are calculated to great accuracy in an approach based on physical sum rules, goerbig1  and the energies of quasiparticles/quasiholes, which are excited at fillings away from the “magical” factors $`\overline{\nu }_L=1/(2s+1)`$ are obtained in the framework of the Hamiltonian theory. MS  In a certain range of the partial filling factor, one finds an alternating sequence of $`M`$-electron-bubble and quantum-liquid ground states with first-order quantum phase transitions between them. Whereas the quantum-liquid states display the FQHE with a quantized Hall resistance $`R_{xy}=h/e^2\nu `$, $`\nu =N+\overline{\nu }_L`$, the bubble phases are insulating, and the electrical transport is thus entirely due to the completely filled lower LLs. This gives rise to the RIQHE with a quantized Hall resistance $`R_{xy}=h/e^2N`$ independent of the partial filling factor, as is observed experimentally. exp2 ; exp3

We acknowledge fruitful discussions with K. Borejsza, J. P. Eisenstein, R. Moessner, and V. Pasquier. This work was supported by the Swiss National Foundation for Scientific Research under grant No. 620-62868.00.


text:
# Cooperation and Self-Regulation in a Model of Agents Playing Different Games

## I Introduction

Game Theory constitutes a powerful and versatile approach to analyze the collective behavior of adaptive agents, from humans to bacteria and firms. In particular, the Prisoner’s Dilemma (PD) game plays in Game Theory a role similar to the harmonic oscillator in Physics. It’s been also referred to as the E. Coli of Social Sciences, allowing a very large variety of studies. Indeed, this game, developed in the early fifties, offers a very simple and intuitive approach to the problem of how cooperation emerges in societies of ”selfish” individuals i.e. individuals which pursue exclusively their own self- benefit. It was used in a series of works by Robert Axelrod and co-workers  to examine the basis of cooperation between selfish agents in a wide variety of contexts. Furthermore, mechanisms of cooperation based on the PD have shown their usefulness in Political Science -, Economics \- , International Affairs -, Theoretical Biology - and Ecology \- .

The PD game consists in two players, say $`i`$ and $`j`$, each confronting two choices: cooperate (C) or defect (D) and each makes its choice without knowing what the other will do. The four possible outcomes for the interaction of agent $`i`$ with agent $`j`$ are : 1) they can both cooperate (C,C) 2) both defect (D,D), 3) $`i`$ cooperates and $`j`$ defects(C,D) and 4) $`i`$ defects and $`j`$ cooperates (D,C). Depending on the situation 1)-4), the agent $`i`$ ($`j`$) gets respectively : the ”reward” $`R(R)`$, the ”punishment” $`P(P)`$, the ”sucker’s payoff” $`S`$ (the ”temptation to defect” $`T`$) or $`T(S)`$. These four payoffs obey the following chain of inequalities:

$$T>R>P>S;$$
(1)
for instance the four canonical PD payoffs are: $`R=3,S=0,T=5`$ and $`P=1`$. Clearly it pays more to defect: if one of the two players defects -say $`i`$\- , the other who cooperates will end up with nothing. In fact, even if agent $`i`$ cooperates, agent $`j`$ should defect, because in that case he will get $`T`$ which is larger than $`R`$. That is, independently of what the other player does, defection D yields a higher payoff than cooperation and is the dominant strategy for rational agents. This is equivalent to say, in a more technical language that, the outcome (D,D) of both players is the Nash equilibrium  of the PD game. The dilemma is that if both defect, both do worse than if both had cooperated: both players get $`P`$ which is smaller than $`R`$.

One can assign a payoff matrix MRSTP to the PD game given by

$$\text{M}^{RSTP}=\left(\begin{array}{cc}(R,R)& (S,T)\\ (T,S)& (P,P)\end{array}\right),$$

which summarizes the payoffs for row actions when confronting with column actions.

The emergence of cooperation in prisoner’s dilemma (PD) games is generally assumed to require repeated play (and strategies such as Tit for Tat (TFT) , involving memory of previous interactions) or features (”tags”) permitting cooperators and defectors to distinguish one another .

In this work, I consider a simple model of selfish agents, possessing neither memory nor tags, to study the self-organized cooperative states which emerge when they play an extended PD game with arbitrary payoffs, i.e. payoffs which do not necessarily fulfill inequalities (1). The taxonomy of 2x2 games (one-shot games involving two players with two actions each) was constructed by Rapoport and Guyer , and showed that there exist exactly 78 non-equivalent games.

There are $`N_{ag}`$ agents, with one variable assigned to each agent at the site or cell $`k`$ and at time $`t`$: his probability of cooperation $`p_k(t)`$. Pairs of agents, $`i`$ and $`j`$, interact by playing the PD game at each time step $`t`$. I use a Mean Field (MF) approach, in which all the spatial correlations in the system are neglected, and thus agent $`i`$ and $`j`$ are chosen at random. After playing the PD the players update their probability of cooperation $`p_i(t)`$ and $`p_j(t)`$ according to the same definite ”measure of success” which does not vary with time. Thus all agents follow a universal and invariant strategy defined by a measure of success plus an updating rule to transform $`p_i(t)`$ and $`p_j(t)`$ into $`p_i(t+1)`$ and $`p_j(t+1)`$.

After a transient, the system self-organizes into a state of equilibrium characterized by the average probability of cooperation $`\overline{p}_{eq}`$ which depend on the payoff matrix.

Payoff matrices can be classified into sub-categories according to their dominant strategy. Let us call $`M_D`$ the class of those matrices such that:

$$T>R,\text{and}P>S,$$
(2)
for which the dominant strategy is D. This class comprises, for instance, the canonical matrix M3051 and M1053, etc. A second class $`M_C`$ corresponds to

$$R>T,\text{and}S>P,$$
(3)
for which the dominant strategy is C, examples of this class are the matrices: M5310 and M3501. The remaining matrices do not comply with equation (2) or (3) and produce situations , a priori, not dominated by (D,D) or (C,C).

One might wonder why bother to study matrices which imply no dilemma and are unrealistic in order to model the social behavior of the majority of individuals. There are several reasons. First, this ”unreasonable” payoff matrices can be used by minorities of individuals which depart from the ”normal” ones (assumed to be neutral). For instance, ”antisocial” ”always D” individuals, which cannot appreciate any advantage of cooperation, or ”altruistic” ”always C” individuals. Second, it seems interesting to test the robustness of cooperation under changes in the payoff matrix. In particular, we will se that even payoff matrices which imply a dilemma can produce either $`\overline{p}_{eq}=0.5`$ or $`\overline{p}_{eq}=0`$. Third, arbitrary payoff matrices could be also of importance in other contexts different from societies. One might envisage situations in which a definite value of $`\overline{p}_{eq}`$ is required or is desirable in the design of a system or is the one which optimizes the functioning of a particular mechanism, etc. For example, to understand how a market of competing firms attains self-regulation. Or for instance in the traffic problem, where the damage suffered from mutual D (crash) exceeds the damage suffered by being exploited (turn away), which is more appropriately described by the so-called chicken game for which $`T>R>S>P`$.

Fourth, we will show results for these payoff matrices which, at first glance, defy our intuition. For example, payoff matrices which, at least in principle, one would bet that favor defection and indeed produce a not so low degree of cooperation.

## II A Mechanism to produce Cooperative Equilibrium States

Among the weaknesses of major approaches that have been considered to answer the question about the emergence of cooperation two are often remarked. The first criticism is about the over-simplification in the behavior of agents: they either always cooperate (C) or always defect (D). Clearly, this is not very realistic. Indeed, the levels of cooperation of the individuals seem to exhibit a continuous gamma of values. The second objection is concerning the deterministic nature of the algorithms which seem to fail to incorporate the stochastic component of human behavior.

Both problems can be overcome by assigning to each agent $`k`$ a probability of cooperation $`p_k(t)`$ (a real number in the interval ) instead of definite behaviors like C or D. Concerning the first objection, $`p_k(t)`$ reflects the existence of a ”gray scale” of levels of cooperation instead of just ”black” and ”white”. Regarding the second objection, the proposed algorithm is clearly non deterministic: agent $`k`$ plays C with probability $`p_k`$ and D with probability 1-$`p_k`$.

Now, let us describe the dynamics. The pairs of interacting partners, by virtue of the MF treatment, are chosen randomly instead of being restricted to some neighborhood. The implicit assumptions are that the population is sufficiently large and the system connectivity is high i.e. the agents display high mobility or they experiment interaction at a distance (for instance electronic transactions). In this work the population of agents will be fixed to $`N_{ag}=1000`$ and the number of time steps will be of order $`t_f=10^510^6`$ in such a way that both assumptions be also consistent with the fact that agents have no memory.

Starting from an initial state at $`t=0`$ taken as $`p_k(0)`$ chosen at random (in the interval ) for each agent $`k`$, the system evolves by iteration during $`t_f`$ time steps following these procedure.

* 1) Selection of players: Two agents, located at random positions $`i`$ and $`j`$, are selected to interact i.e. to play the PD game.
* 2) Playing pairwise PD: The behavior, C or D, of each player $`k`$ ( $`k`$=$`i`$ or $`k`$=$`j`$ ) is decided generating a random number $`r`$ and if $`p_k(t)>r`$ then he plays C and, conversely, if $`p_k(t)<r`$ he plays D.
* 3) Assessment of success: Each of the two players compares his utilities $`U_k(t)`$, which is one of the four PD payoffs: $`R`$, $`S`$, $`T`$ or $`P`$, with an estimate $`ϵ_k(t)`$ of his expected utilities. If $`U_k(t)ϵ_k(t)`$ ($`U_k(t)<ϵ_k(t)`$ ) the agent assumes he is doing well (badly) and therefore its level of cooperation is adequate (inadequate).
* 4) Probability of cooperation update: If player $`k`$ is doing well he keeps his probability of cooperation $`p_k(t)`$. On the other hand, if player $`k`$ is doing badly he decreases (increases) his probability of cooperation $`p_k(t)`$ if he played C (D) choosing an uniformly distributed value between $`p_k(t)`$ and 1 ( between 0 and $`p_k(t)`$).

In order to introduce a simple and natural estimate $`ϵ_k(t)`$ let us consider two players $`i`$ and $`j`$ which cooperate, at time $`t`$, with probabilities $`p_i(t)`$ and $`p_j(t)`$ respectively (and defect with probabilities $`1p_i(t)`$ and $`1p_j(t)`$ ), thus the expected utilities for the player $`i`$, $`U_{ij}^{RSTP}(t)`$, are given by:

$$U_{ij}^{RSTP}(t)=Rp_i(t)p_j(t)+Sp_i(t)(1p_j(t))+T(1p_i(t))p_j(t)+P(1p_i(t))(1p_j(t)),$$
(4)
while the expected utilities for the player $`j`$, $`U_{ji}^{RSTP}`$, are obtained by interchanging $`i`$ and $`j`$ in the above equation.

This implies that, given the average probability of cooperation $`\overline{p}(t)`$, an arbitrary agent, say number $`k`$, can estimate his average expected utilities as:

$$U_k^{RSTP}(\overline{p}(t))=R\overline{p}(t)p_k(t)+Sp_k(1\overline{p}(t))+T(1p_k(t))\overline{p}(t)+P(1\overline{p}(t))(1p_k(t)).$$
(5)
However, it turns out that, in general, the value of $`\overline{p}`$ is unknown by the agents. Hence a simpler estimate that can be used agent $`k`$ for his expected utilities $`ϵ_k(t)`$ is obtained by replacing in equation (5) $`\overline{p}`$(t) by his own probability of cooperation $`p_k(t)`$:

$$ϵ_k^{RSTP}(t)Rp_k^2(t)+(S+T)p_k(1p_k(t))+P(1p_k(t))^2$$

$$=(RST+P)p_k^2(t)+(S+T2P)p_k(t)+P.$$
(6)
In other words, agent $`k`$ adopts the simplest possible extrapolation i.e. that he is a ”normal” individual whose probability of cooperation is representative of the average value ***Considering more sophisticated agents, which have ”good information” on the population (for instance the value of $`\overline{p}`$ at time $`t`$), does not change substantially the main results obtained with these naive agents..

The rule each player follows to update his probability of cooperation is quite natural and of the type ”win-stay” and ”lose-shift”. That is, if the player’s utilities $`U_k`$ are larger than his estimate he keeps his probability of cooperation. On the other hand, if the utilities are smaller than his estimate he changes his probability of cooperation: a) increasing it if he played D or b) decreasing it if he played C. From eq. (6) the update of $`p_k(t)p_k(t+1)`$ is governed by the sign of $`U_k(t)ϵ_k^{RSTP}(t)`$ i.e. by the following inequations:

$$(S+TRP)p_k^2(t)(S+T2P)p_k(t)+\left(\begin{array}{c}R\\ S\\ T\\ P\end{array}\right)P\begin{array}{c}>\\ <\end{array}\mathrm{\hspace{0.33em}\hspace{0.33em}0};$$
(7)
in the case $`>0`$ ($`<0`$) $`p_k`$ is increased (decreased).

In the next section we will see that the strategy which results from the combination of the proposed measure of success and update rule for $`p_k`$ -the steps 3) and 4)- , produces, for a wide variety of payoff matrices, cooperative states with $`\overline{p}_{eq}>0`$.

Let us end this section with a remark about the problem addressed here and its relation with the evolution of cooperation. In this approach, there is no competition of different strategies, all the agents follow the same universal strategy which does not evolve over time. However, the system is adaptive in the sense that the probabilities of cooperation of the agents do evolve.

## III RESULTS

Depending on the payoffs $`R,S,T`$ and $`P`$ the system self-organizes, after a transient, in equilibrium states with values of $`\overline{p}_{eq}`$ ranging from 0 to 1. The equilibrium asymptotic states can be lumped into 3 groups according to the degre of cooperation attained: highly cooperative ($`\overline{p}_{eq}>0.5`$), moderately cooperative ($`\overline{p}_{eq}0.5`$) and of poorly cooperative ( $`\overline{p}_{eq}<0.5`$). The outcomes for any arbitrary payoff matrix MRSTP can be understood in terms of the updating rule for the cooperation probability and the corresponding estimate $`ϵ^{RSTP}`$ i.e. from the inequalities (7).

The payoff matrices which imply a dilemma -those which comply with the chain of inequalities (1)- lead either to $`\overline{p}_{eq}=\frac{1}{2}`$ or to $`\overline{p}_{eq}=0`$. From (7) it emerges that $`\overline{p}_{eq}=0.5`$ occurs in the case when $`ϵ^{RSTP}P`$ has no roots in the interval (0,1\] ($`p=0`$ is always one of the two roots) and $`\overline{p}_{eq}=0`$ in the opposite case.

Some other matrices not belonging to class $`M_D`$ exhibit a tension between C and D and give rise to $`\overline{p}\frac{1}{2}`$. The matrices which do not embody such trade-off produce the situations which depart most from $`\overline{p}_{eq}\frac{1}{2}`$.

It is illustrative to consider, for a moment, the restricted subset of 24 payoff matrices obtained from permutation of the four canonical payoff values because it covers the three groups with different cooperation levels mentioned above. In fact, the system self-organizes into equilibrium states with seven values of $`\overline{p}_{eq}`$: 2 matrices (M3501 and M3510) produce $`\overline{p}_{eq}=1`$, 2 matrices (M1053 and M0153) produce $`\overline{p}_{eq}=0`$. The remaining 20 matrices produce intermediate values: $`\overline{p}_{eq}0.72`$ (M5301) , $`\overline{p}_{eq}0.62`$ (M3510), $`\overline{p}_{eq}0.38`$ (M0135), $`\overline{p}_{eq}0.28`$ (M1035) and $`\overline{p}_{eq}=0.5`$ (the other 16 matrices and among them the canonical payoff matrix). The 24 measures are performed over 500 simulations. Fig. 1 show the average probability of cooperation for different payoff matrices vs. time for the 50,000 first time steps.

The mirror symmetry with respect to he value $`\overline{p}=0.5`$ between the curves for $`\overline{p}(t)`$ corresponding to a given matrix MRSTP and its palindrome MPTSR is due to the symmetry of the game when interchanging $`RP`$ and $`ST`$ simultaneously with cooperators C by defectors D. That is,

$$\overline{p}^{RSTP}(t)=\overline{(1p)}^{PTSR}(t).$$
(8)
A particular interesting case study is provided by payoff matrix M0135 with $`\overline{p}_{eq}0.38`$. This result seems, at first sight, counter-intuitive: an intermediate cooperation level attained with 0 reward (and very low sucker’s payoff) ! Nevertheless, let us show how the updating rule for the cooperation probability explains this outcome. The estimate for this matrix, given by the parabola

$$ϵ_k^{0135}=p_k^26p_k+5,$$
(9)
plotted as a solid curve in Fig.2 (the horizontal lines at $`S=1`$ and $`T=3`$ cut the parabola at abscises $`p_S=3\sqrt{5}`$ and $`p_T=3\sqrt{7}`$, respectively). The cooperation update rule tells us the agent $`k`$ increases his probability of cooperation when he plays D and gets $`T=3`$ if $`p_k`$ is less than $`p_T=3\sqrt{7}<0.5`$, i.e. this temptation is not enough ($`T<ϵ_k^{0135}(p_k)`$). On the other hand, he decreases his probability of cooperation when he plays C and gets $`R=0`$, independently of the value of $`p_k`$, or when he gets $`S=1`$ if $`p_k`$ is less than $`p_S=3\sqrt{5}>0.5`$. In the remaining situations the player keeps his probability of cooperation. Thus a value of $`\overline{p}_{eq}`$ between 0 and 0.5 is not surprising after all, rather it is the result of given the two competing probability of cooperation flows. All this analysis for payoff matrix M0135 works also for any set of payoffs obeying the inequalities:

$$P>T>S>R,$$
(10)
the only thing that changes is the value of $`\overline{p}_{eq}`$. We will come back over this particular payoff matrix to illustrate how $`p_{eq}`$ changes under arbitrary variations of the payoffs.

The Effect of changing payoffs

We are now going to analyze the effect of changing the payoff matrix in order to go beyond the 24 permutations of the canonical payoffs.

We have seen that the sign of $`U_kϵ_k`$ controls the update of $`p_k`$. From the definition of $`ϵ_k`$, as an estimate of utilities of agent $`k`$, it is clear that it is bounded from above and from below by the largest and smallest of the four payoffs, respectively. Thus, $`U_kϵ_k`$ may have different signs, depending on the value of $`p_k`$, only for the two intermediate payoffs. Let us denote by $`p_1`$ the value of $`p_k`$ such that the estimate $`ϵ_k`$ becomes equal to the larger payoff, $`p_2`$ the value of $`p_k`$ such that the estimate becomes equal to the second larger payoff, and so on. Therefore, it is easy to see that the change in $`\overline{p}_{eq}`$ is controlled by the displacements of $`p_2`$ and $`p_3`$ (for instance, for M0135, $`p_2p_T`$ and $`p_3p_S`$). If $`p_2`$ or $`p_3`$ correspond to the cooperative payoffs, $`R`$ or $`S`$, then its displacement to the right (left) decreases (increases) the proportion of C-agents for whom $`U_k>ϵ_k`$ which are, on average, the ones who remain C after playing the game. This in turn decreases (increases) $`\overline{p}_{eq}`$. On the other hand, if $`p_2`$ or $`p_3`$ correspond to the non cooperative payoffs, $`T`$ or $`P`$, then its displacement to the right (left) decreases (increases) the proportion of D-agents for whom $`U_k>ϵ_k`$ which are, on average, the ones who remain D after playing the game. This in turn increases (decreases) $`\overline{p}_{eq}`$.

The payoff matrix M0135 will serve to illustrate the effect the changes in the values of the payoffs have on $`p_{eq}`$. We will proceed by modifying one of the four payoffs at a time and keeping fixed the remaining three in such a way that he chain of in-equalities (10) is preserved. This variation of a quantity that results when the payoff $`X`$ is modified and the other three payoffs remain fixed is denoted by $`\delta _X`$. The estimates that result from these changes are the curves shown in Fig.2. Let us consider first the changes $`\delta _{S^+}`$, produced by an increment in the sucker’s payoff from $`S=1`$ to $`S=2`$ (which transforms M0135 into M0235), $`\delta _S^{}`$, produced by a decrease from $`S=1`$ to $`S=0`$ (which transforms M0135 into M0035). For M0235, $`p_3`$ is the abscise of the point $`ϵ_kS=2`$ (filled up triangle in Fig. 2(A)) and for M0035, $`p_3`$ is the abscise of the point $`ϵ_kS=0`$ (filled down triangle in Fig. 2(A)), while the corresponding $`p_2`$ are the abscises of the points $`ϵ_kT=3`$ (filled triangles: up for M0235 and down for M0035 in Fig.2(A)). We can see that increasing (decreasing) the sucker’s payoff, from $`S=1`$ to $`S=2`$ ($`S=0`$), produces a displacement of $`p_2`$ to the right (left), from $`3\sqrt{7}0.354`$ to 0.4 (to $`\frac{7\sqrt{3}3}{4}0.314`$), and of $`p_3`$ to the left (right), from $`3\sqrt{5}0.764`$ to 0.6 (to 1). Hence, both changes point in the same direction increasing (decreasing) $`p_{eq}`$ as can be observed in Fig. 3 (dotted lines vs. solid lines). In other words,

$$\delta _{S^+}(p_2p_3)(0.40.354)(0.60.764)=0.21>0$$

$$\delta _S^{}(p_2p_3)(0.3140.354)(10.764)=0.276<0$$
(11)
Similarly, we denote by $`\delta _{P^+}`$ the variations produced by an increment in the punishment, from $`P=5`$ to $`P=6`$ (which transforms M0135 into M0136), and by $`\delta _P^{}`$ the variations produced by a decrease in the punishment, from $`P=5`$ to $`P=4`$ (which transforms M0135 into M0134). For both matrices, the corresponding $`p_2`$ and $`p_3`$ are the abscises of the points $`ϵ_kT=3`$ and $`ϵ_kS=1`$ (non filled triangles in Fig.2: up for M0136 and down for M0134 ), respectively. Also in Fig. 2(A) we see that changing the punishment, from $`P=5`$ to $`P=6`$ ($`P=4`$), produces a displacement of $`p_2`$ to the right (left), from $`3\sqrt{7}0.354`$ to $`\frac{4\sqrt{1}0}{2}0.419`$ (to 0.25) , and of $`p_3`$ to the right (left), from $`3\sqrt{5}0.764`$ to $`\frac{4\sqrt{6}}{2}0.775`$ (to 0.75), hence the two changes point in opposite directions: the first tends to increase (decrease) $`p_{eq}`$ and the second to decrease (increase) it. As the first displacement is larger it dominates, and the net result is an increase (decrease) of $`p_{eq}`$ as can be observed in Fig. 3 (dot-dashed lines vs. solid line). That is:

$$\delta _{P^+}(p_2p_3)(0.4190.354)(0.7750.764)=0.054>0,$$

$$\delta _P^{}(p_2p_3)(0.250.354)(0.750.764)=0.09<0.$$
(12)
On the other hand, let us consider the variations produced by the increment of the temptation $`\delta _{T^+}`$, from $`T=3`$ to $`T=4`$ (which transforms M0135 into M0145), and by its decrease $`\delta _T^{}`$, from $`T=3`$ to $`T=2`$ (which transforms M0135 into M0125). For M0145, $`p_2`$ is the abscise corresponding to the point $`ϵ_kT=4`$ (non-filled up triangle) and for M0125, $`p_2`$ is the abscise of the point $`ϵ_kT=2`$ (non-filled down triangle), while the corresponding $`p_3`$ are the abscises of the points $`ϵ_kS=1`$ (non-filled triangles: up for M0145 and down for M0125). In Fig. 2(B) we can see that increasing (decreasing) the sucker’s payoff, from $`T=3`$ to $`T=4`$ ($`T=2`$), produces a displacement of $`p_2`$ to the left (right), from $`3\sqrt{7}0.354`$ to 0.2 (to 0.5) and of $`p_3`$ to the right (left), from $`3\sqrt{5}0.764`$ to 0.8 (to $`\frac{7\sqrt{1}7}{2}0.719`$). Hence both changes point in the same direction decreasing (increasing) $`p_{eq}`$ as can be observed in Fig. 3 (dashed lines vs. solid line). That is:

$$\delta _{T^+}(p_2p_3)(0.20.354)(0.80.764)=0.19<0$$

$$\delta _T^{}(p_2p_3)(0.50.354)(0.7190.764)=0.19>0$$
(13)
With a similar argument one realizes that increasing (decreasing) the reward $`R=0`$ $`p_{eq}`$ decreases (increases).

In summary, for payoff matrices like M0135, which obbey the chain of in-equalities (10), we found two expected results: a higher value of $`p_{eq}`$ can be reached by increasing the sucker’s payoff $`S`$ (which makes C-agents more altruistic) or decreasing the temptation $`T`$ (reducing the incentives to free ride). Additionally we found two, a priori, unexpected results: a higher value of $`p_{eq}`$ can also be reached by increasing the punishment $`P`$ or decreasing the reward $`R`$. By an inspection of Fig. 2(A) the effect of an increment of $`P`$ can be understood as rising the expectations of the D-agents which in turn diminishes the fraction of agents that are satisfied after playing the game. Similarly, from Fig. 2(B) we can see that an decrease of $`R`$ makes the C-agents less ambitious and increase the fraction of altruists.

It is worth remarking that, for the case of payoffs obeying (10), something which at first seems as innocent as to interchange the two non cooperative payoffs $`T`$ and $`P`$ has a dramatic consequence: it transforms a system with an intermediate level of cooperation into one with null cooperation. This can be understood by comparing the estimate (9) for payoff matrix M0135 to the one for M0153 which is given by

$$ϵ_k^{0153}=3p_k^2+3.$$
(14)
Both estimates have maximum value of $`P`$ (5 and 3, respectively, at $`p_k=0`$) but the important difference is that in the first case $`P`$ is the maximum payoff while in second one $`P<T`$. Thus in this second case, only the agents which play C can do badly, and then the only possible change for $`p_k`$ (according to its update rule) is a reduction till it reaches zero value.

Finally, let us include a note regarding the efficiency to attain cooperative regimes. The state of maximum cooperation $`\overline{p}_{eq}=1`$ is reached for payoff matrices such that $`SR>\mathrm{max}\{T,P\}`$ plus the condition that equation

$$(S+TRP)p^2(S+T2P)p+RP=0,$$
(15)
has no roots in the interval  different from $`p=1`$ (which is always a root of (15)). This condition on the roots is because in the opposite case, when there is a root $`p_x`$ in-between 0 and 1, it follows easily from the inequations (7) that $`\overline{p}`$ converges to the semi-sum of $`p_x`$ and 1. It can be checked by elemental algebra that this is the case of, for instance, payoff matrices M3501, M3510.

## IV CONCLUSIONS

The success of the strategy to attain cooperative regimes for a wide variety of games (payoff matrices) - mainly those which implies dilemmas or clearly favor D - relies on the combination of the proposed measure of success and update rule for the probability of cooperation. Basically it works by tuning the agent’s cooperation guided by a trade-off between efficiency (increase of utilities) and equity (indirect reciprocity). If the agent is doing well he maintains his probability of cooperation otherwise he changes it. When he is doing badly playing D he becomes more cooperative, i.e. he increases his probability of cooperation attempting to change to behavior C and explore this alternative behavior. Conversely, if he is doing badly playing C then he decreases his probability of cooperation attempting to change to behavior D and see what happen.

An interesting extension of the model would be to allow competition of different strategies to promote their evolution i.e. players which imitate the best-performing ones in such a way that lower scoring strategies decrease in number and the higher scoring increase.

Another possibility would be to allow the use of distinct payoff matrices. For instance, individuals inclined to cooperate (defect) might be represented by agents using the payoff matrix M5301 (M1035) while ”neutral” ordinary agents by those using the canonical payoff matrix M3051. This would make possible to study if mutants inclined to D can invade a group of neutral individuals or individuals inclined to C and drive out all cooperation.

Here I considered a MF approximation which neglects all the spatial correlations. One virtue of this simplification is that it shows the model does not require that agents interact only with those within some geographical proximity in order to sustain cooperation. Playing with fixed neighbors is sometimes considered as an important ingredient to successfully maintain the cooperative regime ,. However, the quality of this MF approximation depends on the nature of the system one desires to model, and varies whether one deals with human societies, viruses , cultures of bacteria  or market of providers of different products. In order to consider situations in which the effect of geographic closeness cannot be neglected, an alternative version of this model, might include a spatial PD game, in which individuals interact only (or mainly) with those within some geographical proximity. In that case, the study of spatial patterns seems an interesting issue to address. Work is in progress in that direction.

Acknowledgments.

I thank R. Axelrod for valuable opinions and R. Donangelo for useful discussions and criticism.


text:
# Experimental requirements for Grover’s algorithm in optical quantum computation

## I Introduction

In the next few years, we can expect to see demonstrations of basic quantum gates in several implementations of quantum computation. With this in sight, it is natural to look ahead to what interesting quantum circuits can be built out of a small number of one- and two-qubit gates acting on a few qubits, as these circuits will provide milestones on the way to full-scale quantum computation QIS (2002).

Grover’s search algorithm Grover (1996, 1997) is a good candidate for such a milestone. It is a quantum algorithm identifying one of $`N`$ elements, marked by an oracle, with order $`\sqrt{N}`$ uses of the oracle. When the search space consists of 4 elements, the algorithm is guaranteed to produce the marked element after one use of the oracle, compared to the 2.25 uses expected in a classical search. We will see that it can be implemented using only 7 one-qubit gates and 2 two-qubit gates, which makes it an excellent target once one- and two-qubit gates have been mastered. Not surprisingly, it was one of the first algorithms to be experimentally implemented in nuclear magnetic resonance quantum computing (Chuang, Gershenfeld, and Kubinec Chuang et al. (1998) and Jones, Mosca, and Hansen Jones et al. (1998)).

A promising quantum computing technology is the *linear optical quantum computation* (LOQC) scheme of Knill, Laflamme, and Milburn Knill et al. (2001a) (see Gottesman, Kitaev, and Preskill Gottesman et al. (2001) for an alternative approach). In this scheme, one-qubit gates are relatively straightforward. While implementing a scalable universal two-qubit gate such as a cnot remains a challenge, such a gate is likely to be demonstrated in the next couple of years. Already, a non-scalable cnot has been approximately implemented by Pittman et al. Pittman et al. (2003). For these reasons, it is important to establish some specific LOQC milestones on the path toward building a large quantum computer, in the form of some simple algorithms on a few qubits.

This pursuit is dogged by conceptual difficulties associated with quantum algorithms on a very small number of qubits, summed up in the question: What is the criterion for “quantumness”? A reasonable criterion, particularly in the context of Grover’s algorithm, is to require a “speed-up” over the best classical algorithm. However, this notion can be hard to make sense of when the number of steps is on the order of ten, rather than millions, and the problem can easily be done by hand (not to mention by a GHz classical processor). Furthermore, sometimes the reduction in the number of steps can be achieved in an implementation whose physical requirements grow exponentially with the number of qubits, trading off time for space. The question of whether or not this counts as “quantum” has received much attention (see, for example, Kwiat et al. Kwiat et al. (2000), Bhattacharya, van den Heuvell, and Spreeuw Bhattacharya et al. (2002)).

Perhaps the best solution to this problem is a pragmatic one. In the quest to build a quantum computer large enough to provide a genuine advantage over classical computers, two things must be achieved. First, a fine level of quantum control must be demonstrated for both single qubits and pairs of qubits. Second, it will be necessary to show that the number of components (qubits and gates) in a circuit can be increased without insurmountable increases in difficulty. In particular, we must avoid exponential increases in the amount of resource usage (either time or space) — the implementation must be *scalable*111Blume-Kohout, Caves, and Deutsch Blume-Kohout et al. (2002) give a general characterization of the requirements for scalability..

Therefore, the importance of an experimental achievement of an early milestone (such as the four-element Grover’s algorithm) should be measured primarily on these criteria. A demonstration that Grover’s algorithm finds the marked item in fewer steps than is possible with a classical computer is an important goal, but it is less important than the fine level of quantum control that it implies. At this early stage of development of quantum computers, any such demonstration is a significant achievement, while a demonstration of such control in a scalable manner is likely to be significantly more difficult and consequently more impressive.

This is illustrated by the experiment of Kwiat et al. Kwiat et al. (2000), which demonstrated the ability to implement the search algorithm in a quantum optical system, but using an encoding that is not scalable — as they point out, the number of optical elements that they require grows exponentially in the number of qubits in their system. Thus, although their techniques might be successfully extended to a few qubits, they are not practical as the basis for an approach to building a quantum computer.

In contrast, we are explicitly concerned with developing experimental milestones on the path toward full-scale quantum computation in optical systems. We show that Grover’s algorithm on four elements provides several experiments that gradually increase in complexity. The simplest version requires little more than a single, coincidence-basis cnot gate together with a source of entangled photon pairs, while the most complex version requires two scalable cnot gates and six photons.

Before describing these experiments and their requirements, we give a brief description of Grover’s algorithm (Section II) and LOQC (Section III). Since the original proposal of LOQC, there have been many simplifications and improvements to the scheme. We give a concise description of the basics of LOQC making full use of these simplifications, focusing on a variant of the original scheme that uses polarization-encoded qubits. In Sections IV and V, we describe and compare several optical circuits, all implementing Grover’s algorithm on four elements. In Section VI we briefly discuss appropriate figures of merit for Grover’s algorithm, and we conclude in Section VII.

## II Grover’s algorithm on four elements

Grover’s algorithm Grover (1996, 1997) (see also Nielsen and Chuang Nielsen and Chuang (2000) for an elementary treatment on which much of this section is based) is a quantum algorithm that can speed up the solution to certain types of oracle-based computations. We will say more about oracles and their implementation after describing Grover’s algorithm.

### II.1 Grover’s algorithm

Suppose our search space consists of $`N2^n`$ elements, of which one is a solution to a given problem. Grover’s algorithm identifies the solution (with high probability) using $`n+1`$ qubits according to the following algorithm:

1. Prepare the state $`|0^n|1`$.
2. Apply $`R^{n+1}`$, where $`R=\frac{1}{\sqrt{2}}\left[\begin{array}{cc}1& 1\\ 1& 1\end{array}\right]`$ is the one-qubit Hadamard gate. (We use the symbol $`R`$ instead of the usual $`H`$ to avoid confusion with the horizontal polarization state.)
3. Apply the oracle, which flips the ancilla qubit conditional on the other qubits being in the state corresponding to the solution.
4. Apply $`R^{n+1}`$.
5. Apply a phase shift to the data qubits conditional on not being in the state $`|0^n`$, described by the unitary operator $`2|00|^nI_n`$ where $`I_n`$ is the identity operation on the data qubits.
6. Apply $`R^n`$.
7. Repeat steps (3) to (6) a specified number of times, then measure the qubits in the computational basis.

The number of repetitions (which is also the number of uses of the oracle) that maximizes the probability of obtaining the correct answer is the nearest integer to

$$\frac{\mathrm{arccos}\sqrt{1/N}}{2\mathrm{arccos}\sqrt{(N1)/N}}$$
(1)
(Boyer et al. Boyer et al. (1998), see also Nielsen and Chuang (2000)). This number is bounded above by $`\pi \sqrt{N}/4`$, hence the claim that Grover’s algorithm uses $`𝒪(\sqrt{N})`$ oracle calls, compared to the $`𝒪(N)`$ oracle calls required in the classical case.

For the remainder of this paper, we restrict our attention to the case where the number of elements in the search space is $`N=4`$. In that case, the number of repetitions specified by Eq. (1) is exactly one. A simplified circuit based on the algorithm described above is shown in Fig. 1. It can be verified directly that this circuit, using only one oracle call, gives the correct answer with probability 1, compared to the average of 2.25 oracle calls that must be made with a classical circuit. For example, if the solution is 10, then the output of the circuit is $`a=1`$ and $`b=0`$.

### II.2 Implementing the oracle

An oracle is a quantum circuit that *recognizes* solutions to a given problem. For example, suppose we wish to solve a version of the traveling salesman problem, where the goal is to find a route visiting a given collection of cities that is shorter than some specified length $`L`$. Although it is in general hard to find such a route, it is easy to recognize whether a proposed route solves the problem: simply add up the total distance the salesman would travel on the proposed route, and compare it to $`L`$.

Specifically, an oracle is a circuit that, given an input consisting of a potential solution to a problem, flips the sign of an ancilla qubit if and only if the input is a solution to the problem. Since the only action of the oracle is to recognize solutions, its internal structure is unimportant in a test of the algorithm itself. Thus, for our purposes, the choice of oracle is arbitrary, and may be chosen to be as simple as possible.

Although the internal workings of the oracle are unimportant for the purposes of testing the algorithm, the complexity of implementing *some* oracle must be included to characterize the difficulty of performing the experiment. A simple implementation of an oracle marking one of four states is a Toffoli gate, with the control qubits negated where necessary to specify any of the states 00, 01, 10, or 11 (see the left-hand side of Fig. 2 for the example where the marked state is 10).

If the marked state is 10, the action of the oracle on the three qubits is to take the state $`(|00+|01+|10+|11)(|0|1)`$ to

$$\begin{array}{c}\hfill (|00+|01+|11)(|0|1)+|10(|1|0)\\ \hfill =(|00+|01|10+|11)(|0|1)\end{array}$$
(2)
(omitting the normalization). Thus the oracle simply has the effect of flipping the sign of the marked state. The ancilla is not used again, so it can be discarded at this point.

Toffoli gates are difficult to implement in LOQC because there is no known way to implement one without using several cnots. However, for our purposes, a full Toffoli gate is not required because the ancilla qubit plays such a limited role. The two-qubit circuit on the right-hand side of Fig. 2 illustrates this for the case where the marked state is 10. A single controlled-$`Z`$ (csign) gate that flips the sign of the $`|11`$ state, followed by $`X`$ gates to move the minus sign to the appropriate state, has the same action as the original oracle.

A simplified circuit to implement the four-element Grover algorithm is given in Fig. 3. This is the circuit that we will work with for the remainder of this paper.

## III LOQC with polarization encoding

In LOQC, qubits are encoded in *dual rail logic* Knill et al. (2001a): Two modes $`A`$ and $`B`$ are used, and logical $`|0`$ and $`|1`$ are encoded as $`|1_A|0_B`$ and $`|0_A|1_B`$, respectively. The modes may represent two different *spatial* modes, or two different *polarization* modes of a single spatial mode.222A good introduction to LOQC in spatial encoding is provided by a set of lectures of Knill, available online at http://online.itp.ucsb.edu/online/qinfo01/.

In practice, it is likely that polarization-encoded qubits will be used, so that logical $`|0`$ and $`|1`$ are encoded as $`|H`$ and $`|V`$, respectively, where $`H`$ and $`V`$ refer to horizontal and vertical polarization one-photon states of the same spatial mode. The main reasons for this are (1) it significantly simplifies the implementation of the cnot gate (see below), (2) it allows one-qubit gates to be implemented using only waveplates and phase delays rather than beamsplitters and interferometers, and (3) it reduces the effects of noise by ensuring that, unlike with spatial encoding, both states follow the same path on the quantum wires between gates. In this section we describe in some detail the construction of one-qubit gates and cnots in polarization-encoded LOQC.

### III.1 One-qubit gates

To our knowledge, no complete description of how to implement basic quantum gates with polarization encoding has been given in the literature, so we provide one here. For one-qubit gates, waveplates and phase delays are sufficient. A waveplate with slow axis $`|H^{}`$ and fast axis $`|V^{}`$ has action

$$\begin{array}{cc}\hfill |H^{}& e^{i\varphi }|H^{}\hfill \\ \hfill |V^{}& |V^{},\hfill \end{array}$$
(3)
where $`\varphi `$ is the resulting relative phase difference. Special cases in common use are the half and quarter waveplates, with $`\varphi `$ equal to half and a quarter of a wavelength, respectively. Now suppose $`|H^{}`$ is rotated counter-clockwise (with respect to the direction of travel of the light) by an angle $`\alpha `$ from $`|H`$. If the input state is $`\left[\begin{array}{c}h\\ v\end{array}\right]h|H+v|V`$, then the output is given by

$$\left[\begin{array}{cc}e^{i\varphi }\mathrm{cos}^2\alpha +\mathrm{sin}^2\alpha & (e^{i\varphi }1)\mathrm{cos}\alpha \mathrm{sin}\alpha \\ (e^{i\varphi }1)\mathrm{cos}\alpha \mathrm{sin}\alpha & e^{i\varphi }\mathrm{sin}^2\alpha +\mathrm{cos}^2\alpha \end{array}\right]\left[\begin{array}{c}h\\ v\end{array}\right].$$
(4)
Special cases of this transformation for common one-qubit gates are set out in Table 1. The Hadamard and $`\pi /8`$ gates, labeled $`R`$ and $`T`$ in the table, are a universal set for one-qubit quantum computation (Boykin et al. Boykin et al. (2000)), and so any one-qubit gate can be obtained by a sequence of waveplates, although it is convenient to allow phase delays as well. In the Grover circuit, the only one-qubit gates used are the $`R`$, $`X`$, and $`Z`$ gates, and thus we only require half waveplates.

### III.2 Two-qubit gates

Since the publication of the original LOQC scheme of KLM Knill et al. (2001a), many simplifications of their csign gate have been developed, with varying trade-offs between simplicity and functionality. The different types may be divided into two classes, those that are scalable and those that are not. In this section, we describe both types. (Note that the cnot and csign gates are related by conjugation by Hadamards on the target bit, i.e. $`\text{cnot}=(IR)\text{csign}(IR)`$. Therefore, in the context of LOQC where one-qubit gates are relatively straightforward, these two gates are practically equivalent, and we will use the two almost interchangeably.)

#### III.2.1 Scalable two-qubit gates

The KLM scheme Knill et al. (2001a) has two properties that at first appear contradictory: the LOQC csign is non-deterministic, but it is used to do computations in a scalable manner. The non-deterministic nature of the KLM csign is essential to engineer a two-photon interaction without using highly nonlinear materials, but it poses a problem: if its success probability is $`ϵ<1`$, then the success probability of a circuit with $`n`$ csigns is $`ϵ^n`$ — it decreases exponentially with $`n`$. A solution to this problem is the technique of *gate teleportation* described by Nielsen and Chuang Nielsen and Chuang (1997) and Gottesman and Chuang Gottesman and Chuang (1999). This technique allows the gates to be prepared as an offline resource, and then “teleported in” whenever required for a computation. KLM showed that the teleportation step can be made near-deterministic using a sufficiently large number of repetitions. This technique is unlikely to be used in early experiments, however, because the extra difficulty involved in teleporting gates will more than cancel out the advantages of increasing the success probability when the number of csigns is small.

An essential feature required to make this work is that it must be possible to determine when the gate has succeeded. The KLM cnot has this property — although it only succeeds 1 time in 16, whether or not it has succeeded is determined by the outcomes of measurements on ancilla photons. We use the term *scalable* to describe a csign (or cnot) that has the property that it is known when it succeeds.

In this paper, we will not work directly with the KLM csign since there are simpler alternatives, such as the closely related simplification proposed by Ralph et al. Ralph et al. (2002a) and the substantial modification proposed by Knill Knill (2002). There is also a promising alternative approach using entangled ancillas discovered by Pittman, Jacobs and Franson Pittman et al. (2001) that we will not consider further here. We focus on the csign of Ralph et al., shown in Fig. 4.333Recent numerical work by Lund, Bell, and Ralph Lund et al. , shows that the simplified KLM csign of Ralph et al. (2002a) is more resilient to detector and ancilla inefficiencies than the other two, perhaps because it acts symmetrically on the two qubits. For example, the fidelity of this gate (calculated as the fidelity of the actual output with the ideal output, minimized over input states) is larger than the fidelities of the other two gates for detector efficiencies up to approximately 95%. However, it remains to be seen what effects other sources of error, such as mode-matching errors, and imperfect beamsplitter reflectivities, will have on the relative merits of each gate.

In fact, there is a further, substantial simplification to this circuit that is achieved by making fuller use of the polarization encoding, resulting in the circuit in Fig. 5. This gate still requires two ancilla photons. However, it uses fewer detectors, beamsplitters, and polarizing beamsplitters, and eliminates two interferometers. Its effect on qubit states is unchanged, up to an unimportant overall phase of $`1`$. If we denote the beamsplitter reflectivities as $`\eta _153\sqrt{2}`$ and $`\eta _2(3\sqrt{2})/7`$ (which are approximated as $`\mathrm{cos}40.8^{}`$ and $`\mathrm{cos}76.9^{}`$ in the diagram), then the action of the gate is the following:

$$\begin{array}{cc}& |00\sqrt{\eta _1\eta _2}(2\eta _21)|00=\sqrt{p}|00\hfill \\ & |01\eta _1(3\eta _2^22\eta _2)|01=\sqrt{p}|01\hfill \\ & |10\sqrt{\eta _1\eta _2}(2\eta _21)|00=\sqrt{p}|10\hfill \\ & |11\eta _2|11=\sqrt{p}|11\hfill \end{array}$$
(5)
where the success probability $`p`$ is given by $`p\eta _2^2=(116\sqrt{2})/490.05`$. Thus the gate works approximately 1 out of every 20 attempts. For the remainder of this paper, we will refer to this gate simply as a “scalable csign”.

#### III.2.2 Coincidence-basis two-qubit gates

An even simpler, but non-scalable cnot was discovered by Hofmann and Takeuchi Hofmann and Takeuchi (2002) and Ralph et al. Ralph et al. (2002b). It succeeds 1 time in 9, but it only works in the *coincidence basis*, i.e. when the results of the whole computation are selected to contain an allowed distribution of photons among detectors. We call this a *coincidence-basis cnot*. See Fig. 6. This circuit has been designed so that if exactly one photon is measured in the top rail (in either polarization), and one in the bottom rail, it has worked with certainty. Otherwise, the result is discarded and the experiment is repeated. It cannot in general be followed by further two-qubit gates, as it is possible for a later gate to mask a failure. Thus it cannot be used to do scalable quantum computation.

The useful purpose served by this gate (as well as the coincidence-basis gate of Pittman et al. (2003)) is as a simpler intermediate step before the full complexity of a scalable cnot. In a general circuit, it may be possible to replace one or more scalable cnots with a coincidence-basis cnot, thereby significantly reducing the complexity of circuits containing a few cnots. In the following sections on constructing optical circuits to perform the four-element Grover algorithm, we will see some of these ideas in action.

## IV The two-qubit Grover in LOQC

A simplified circuit for the four-element Grover algorithm was given in Fig. 3. In Fig. 7, this circuit is translated directly into an optical circuit, using the prescriptions and circuits of the previous section.

The circuit, which succeeds one time in approximately $`180=20\times 9`$ (the product of the number of attempts per success for each cnot), uses 10–12 half waveplates,444Note that the $`90^{}`$ and $`67.5^{}`$ halfwave plates cannot be combined into a single waveplate: their product $`\frac{1}{\sqrt{2}}\left[\begin{array}{cc}1& 1\\ 1& 1\end{array}\right]`$ has terms of opposite sign in the off-diagonal terms, while the waveplate equation (Eq. (4)) has these entries equal. 5 beamsplitters (2 of which must be modematched), 9 polarizing beamsplitters (4 of which must be modematched), 4 photons that must be simultaneously produced in desired polarization states, and 7 single-photon detectors. The second cnot can be done in the coincidence basis since there are no interactions between the two qubits following it. Therefore, if the final measurement contains an allowed distribution of photons (exactly one in the top two detectors and one in the bottom two detectors), we know that the second cnot worked, which is sufficient for our purposes here.555A small but potentially useful simplification is to remove the $`40.8^{}`$ beamsplitter, as described in Lund et al. . They show that, until detector and source efficiencies of up to approximately 99.5% are reached, the fidelity of the gate can be substantially increased by removing this beamsplitter and adjusting the reflectivity of the $`76.9^{}`$ beamsplitter. Given that beamsplitter reflectivities are imperfect, removing this beamsplitter is likely to decrease that source of error, while also decreasing the complexity of the circuit by removing a detector. There is a catch, however: the probability of success decreases by a factor of 4–5 for efficiencies of 80%–95%.

However, it is important to note that the output of this circuit (before the measurement) could not be used to do further calculations because of the uncertainty in the outcome of the second cnot. If, for example, there were two photons in the top rail after the second cnot, the system’s state would no longer be in the “qubit space”. A third cnot might bring the system back into the qubit space, but it is unlikely to have performed the transformation we expected. In this case, the overall circuit fails, but we have no way of detecting the failure (except to compare with the answer that we can calculate by hand for this simple case).

To ensure reliability for further calculations, the second cnot should be replaced by a scalable cnot. The optical circuit for this case would work one time in 400, and would contain on the order of 14–16 waveplates, 8 polarizing beamsplitters (6 of which would be modematched), 4 ordinary beamsplitters (2 of which would be modematched), 6 photons produced in desired polarization states simultaneously, and 10 single-photon detectors. This would be considerably more difficult to achieve experimentally. Since we are (in principle) guaranteed to be in the qubit space at the end of this circuit, the output of each pair of detectors should contain exactly one photon. Therefore, it is possible to simplify the final detection process by simply blocking out one of the polarizations (horizontal, say), and then looking to see if a photon is detected. This would reduce the number of polarizing beamsplitters to 6 and the number of detectors to 8, at the cost of introducing two polarization filters. However, in practice the number of photons at the output will sometimes be incorrect. Thus, the increase in simplicity would have to be weighed against the failures that would go undetected.

## V Simplifications

By far the most difficult aspect of the experiments just described is implementing the scalable csigns. However, the csign in the oracle is only used in a very restricted way, and it turns out that we can replace it with a much simpler circuit. Since only one input state is ever used, namely $`(|H+|V)(|H+|V)`$, only one state is ever output from the csign, namely $`|HH+|VH+|HV|VV`$. (We will continue to neglect normalization constants.) If a source of entangled input states were available, then the csign could be replaced. In optics, such a source is in fact readily available: a parametric down conversion source can be used to produce the state $`|HH+|VV`$, which can be converted into our desired state by a Hadamard gate on the first qubit, $`|H|H+|V`$, $`|V|H|V`$. Using this fact, a much simplified version of Grover’s algorithm is presented in Fig. 8.

The simplicity of this circuit compared with the previous one is emphasized by comparing the number of components. This circuit works one in every 9 attempts, and requires 6–8 waveplates, 6 polarizing beamsplitters (of which 2 must be modematched), 3 ordinary beamsplitters (1 of which must be modematched), 2 photons which are produced as the output of a parametric down-conversion source, and 4 single-photon detectors.

What have we traded for this enormous gain in simplicity? It turns out that we have compromised the versatility of the algorithm. Most significantly, the oracle is no longer easily replaceable. In principle, the oracle should be a ‘”plug-in” component able to have many different forms corresponding to different potential problems. In this simplified scheme, however, we have obscured the line between the oracle and non-oracle parts of the circuit, making it difficult to see how to make the circuit solve a problem using a different oracle. In Fig. 8, a dashed box outlines the “oracle” part of the circuit for comparison with the previous diagrams, but there is in fact no clear line dividing the oracle from the earlier part of the circuit.

This change affects how the circuit could be used. One example is demonstrating the variation in the success probability of Grover’s algorithm as a function of the number repetitions of steps (3)–(6) described in Sec. II. In the circuit in Fig. 7, the oracle can be reused with some small changes.666The oracle on the right-hand side of Fig. 2 is designed to work with inputs that are equal superpositions of computational basis states. If the oracle is used twice in the same circuit, then it is unlikely that the input state will always be the same. In order to make the oracle work for an arbitrary input state, it is necessary to simply duplicate the $`X`$ gates following the csign, before the csign. For the example in Fig. 2, where the oracle marks the state $`|01`$, the oracle should consist of the following: an $`X`$ gate acting on the bottom qubit, followed by the csign, followed by the $`X`$ acting on the bottom qubit. On the other hand, in Fig. 8, this is not possible — the “oracle” can only be used once777For a more speculative example, Grover’s algorithm can be used to obtain upper bounds on an entanglement monotone called the *Groverian entanglement*, as described by Biham, Osborne and Nielsen Biham et al. (2002). The basic idea is that if an $`n`$-qubit state $`\rho `$ (possibly mixed) is used as input rather than $`|0^n`$, the square root of 1 minus the success probability gives a good measure of the entanglement of $`\rho `$. This application requires input states with varying degrees of entanglement, and thus is not possible in the simplified circuit..

## VI Figures of merit

An important question that has so far not been addressed is what the appropriate figures of merit are for this experiment. There are two related but distinct notions of success here. The first is to what extent the actual goal of Grover’s algorithm has been achieved, i.e. how successfully the experiment distinguishes between the four different oracles. The second is how similar the actual operation of circuit is to the ideal operation. This second notion is important for using these experiments as tests of the ability to combine the basic elements of quantum computation. It is clearly related to the first — if the experiment cannot reliably distinguish between the oracles, then the actual behavior of the circuit must be very far from the ideal operation.

In order to be able to compare experiments (and also to optimize the performance of a particular experimental setup), we need to be more precise about how to measure the success of these experiments. We suggest calculating figures of merit reflecting each of the two notions of success described above. The first is simply to measure the distinguishability of the distribution of measurement results output by the circuit for different oracles. For example, suppose that for the oracle marking the state $`00`$, the results $`00`$, $`01`$, $`10`$, and $`11`$ occur with probabilities $`p_{00}\{0.9,0.04,0.02,0.04\}`$, while the corresponding results when the oracle marks state $`10`$ are $`p_{10}\{0.01,0.08,0.8,0.11\}`$. A simple indicator of the distinguishability of these two distributions is their fidelity

$$F(p_{00},p_{10})\underset{x}{}\sqrt{p_{00}(x)p_{10}(x)}$$
(6)
where $`x`$ ranges over the measurement outcomes $`00,\mathrm{},11`$ and $`p_{ab}(x)`$ is the probabilities of obtaining result $`x`$ given that the oracle marked state $`ab`$. This quantity has the property that it is 1 precisely when the two distributions are identical and 0 precisely when the two distributions are non-overlapping, that is, when the set of results for which the first distribution is non-zero has no elements in common with the set of results for which the second distribution is non-zero.

In the context of Grover’s algorithm, it is desirable to make the fidelity between the distributions arising from each pair of oracles as large as possible. (For an introduction to the fidelity, see, for example, Fuchs (1996); Nielsen and Chuang (2000). The relationship of the fidelity to distinguishability is explored in Wootters Wootters (1981) and Fuchs (1996).)

The second figure of merit is related to the similarity of the actual operation implemented $``$ to the desired unitary $`U`$. $`U`$ is obtained by simply multiplying together the circuit elements in Fig. 3. $``$, on the other hand, must be determined experimentally. Ideally, $``$ should be determined precisely using a method such as quantum process tomography (Chuang and Nielsen Chuang and Nielsen (1997) and Poyatos, Cirac, and Zoller Poyatos et al. (1997)). Although process tomography can be done using only product-state inputs and one-qubit measurements, it requires an enormous number of runs of the experiment since the output states resulting from 16 different input density matrices must be determined via quantum state tomography.

A less stringent, but much more easily calculated, criterion is that the probability distributions for each oracle should be close to the ideal distributions. Again, it is desirable to have the fidelity of the actual distribution to the ideal distribution for each oracle as close to 1 as possible.888Knill et al. Knill et al. (2001b) have a useful discussion of these issues where they advocate the *entanglement fidlelity* to measure the quality of an experimental implementation of the five-qubit code. They describe a simple way of measuring the entanglement fidelity that could be easily generalized to the setting of Grover’s algorithm.

## VII A hierarchy of experiments

This collection of different implementations of the same algorithm could be used as the basis for a series of experiments, each building on the last, each more complicated than the last, each demonstrating improved quantum control. For example, once a basic coincidence-basis cnot is working, it would be relatively simple to add a small number of waveplates and a source of entangled photons to do the circuit in Fig. 8. Once a scalable cnot is achieved, these two different cnot circuits could be combined to do the more complicated implementation of Grover’s algorithm in Fig. 7, demonstrating the ability to combine a scalable cnot with further non-trivial quantum computations. Finally, in the more distant future, the implementation using two scalable cnots would make a good testing ground for techniques for combining LOQC components.

###### Acknowledgements.

JLD thanks Jeremy O’Brien, Geoff Pryde, and Andrew White for providing insight into the world of experiments, Alexei Gilchrist and Geoff Pryde for a careful reading of the manuscript, Andrew Doherty for help in understanding waveplates, Michael Nielsen for helpful discussions on Grover’s algorithm, and Paul Cochrane and Alexei Gilchrist for help using their program for drawing quantum circuits (http://pyscript.sourceforge.net), which produced all of the diagrams in this paper. JLD and GJM thank the Institute for Quantum Information for their hospitality. This work was supported in part by the National Science Foundation under grant EIA–0086038, and by the Australian Research Council and ARDA.