text:
# Local Rigidity in Sandpile Models

## I Introduction

The concept of Self Organized Criticality (SOC) btw ; jen ; review\_braz  has been proposed as a unifying theoretical framework to describe a vast class of driven systems that evolve “spontaneously” to a stationary state characterized by power law distributions of dissipation events. While originally SOC systems were associated to the absence of tuning parameters, it is now clear vz97 ; review\_braz  that most of the proposed systems show a critical behaviour only in the limit of an infinite separation of time scales, i.e. if some suitable parameter (e.g. the dissipation and the driving rate in sandpile models vzl96 , the temperature in some growth models verg , etc.) is set to zero. These results suggested a new definition of SOC gcp  as the theory of dynamical processes that lead a system to the critical steady state if the critical value of the control parameter is zero.

The stabilizing effect of a threshold caf  in the class of sandpile models is discussed by introducing a *local rigidity* defined as the ratio between the critical energy and the amplitude of the external perturbation, $`r\epsilon _c/\delta \epsilon `$. A finite rigidity allows the system to assume a large number of metastable configurations and this let the process show a power law distribution of avalanches. In caf  it has been shown by means of numerical simulations that in the limit $`r0`$ the system becomes a diffusive one characterized by only infinite avalanches. In this paper we show how, in the framework of the so-called Dynamically Driven Renormalization Group (DDRG) pvz94 ; ddrg , a finite rigidity in the microscopic dynamics is crucial in order for the system to reach spontaneously a critical stationary state instead of a diffusive one. The basic idea is that at large scale the value of the rigidity does not depend on the microscopic value and that this “coarse grained” value allows for a non ambiguous distinction between a diffusive and a SOC system.

## II The renormalization of the rigidity

In Sandpile Models we assign an integer variable (“energy”) $`\epsilon _i`$ on each site $`i`$ of a $`d`$-dimensional hypercubic lattice. At each time step an energy grain is added on a randomly chosen site, and then the system is allowed to relax according to a particular stability criterion depending on a fixed threshold (e.g. the energy, or the slope -defined as the difference between the energy of two nearest neighbours- exceeding a critical value). Infinite slow driving, i.e. an infinite separation of time scales, is built into the model: during the updating process the external input stops. The original BTW sandpile model btw  is a critical height model with $`\epsilon _c=4`$ and external input $`\delta \epsilon =1`$.

We consider a generalized sandpile model with critical height $`\epsilon _c`$ and external perturbation $`\delta \epsilon `$ for the microscopic dynamics. If $`\epsilon _i>\epsilon _c`$ at time $`t`$ then $`\epsilon _i=0`$ at time $`t+1`$ and the $`q`$ nearest neighbours of site $`i`$ increase their value of $`\epsilon _i/q`$. At the generic scale these quantities have the values $`\epsilon _c^{(k)}`$ and $`\delta \epsilon ^{(k)}`$. The height of the stable sites is less than $`\epsilon _c^{(k)}\delta \epsilon ^{(k)}`$, for the critical sites the energy lies between $`\epsilon _c^{(k)}\delta \epsilon ^{(k)}`$ and $`\epsilon _c^{(k)}`$ while for unstable sites it is larger than $`\epsilon _c^{(k)}`$. We study the behaviour of $`\epsilon _c^{(k)}`$ and $`\delta \epsilon ^{(k)}`$ under the renormalization flow of the DDRG which could be formally written as:

$`\epsilon _c^{(k+1)}`$ $`=`$ $`f(\epsilon _c^{(k)},\delta \epsilon ^{(k)};\rho ^{(k)},𝐏^{(k)})`$
$`\delta \epsilon ^{(k+1)}`$ $`=`$ $`g(\epsilon _c^{(k)},\delta \epsilon ^{(k)};\rho ^{(k)},𝐏^{(k)})`$
where $`\rho ^{(k)}`$ (density of critical sites) and $`𝐏^{(k)}(p_1^{(k)},p_2^{(k)},p_3^{(k)},p_4^{(k)})`$ ($`p_n`$ is the probability that in a toppling the energy is distributed exactly to $`n`$ nearest neighbours) are the parameters characterizing the state at the generic scale $`k`$. In principle we have to couple these two equations to those that determine the renormalization of $`\rho ^{(k)}`$ and $`𝐏^{(k)}`$; for sake of simplicity, having extended the parameters space, we assume that the flow of the new parameters is orthogonal to the space defined by the old ones. We then accordingly fix $`\rho ^{(k)}`$ and $`𝐏^{(k)}`$ to their fixed point values $`\rho ^{}`$ and $`𝐏^{}`$ as computed in ref.. Their values are $`\rho ^{}=0.468`$ and $`𝐏^{}=(0.240,0.442,0.261,0.057)`$. The validity of this approximation will be checked by numerical simulations. Our transformation will have the form:

$`\epsilon ^{(k+1)}`$ $`=`$ $`f(\epsilon _c^{(k)},\delta \epsilon ^{(k)};\rho ^{},𝐏^{})`$
$`\delta \epsilon ^{(k+1)}`$ $`=`$ $`g(\epsilon _c^{(k)},\delta \epsilon ^{(k)};\rho ^{},𝐏^{})`$
The symbols used are shown in Fig. 1 and 2.

Let us consider now a single path as an example of the transformation we want to obtain. We have a $`2\times 2`$ cell characterized by a label $`\alpha `$ specifying the number of critical sites. The $`\alpha =1`$ configuration is not considered because of a *spanning rule* that imposes the exclusion of those processes that do not relax within the cell before they transfer energy outside. Every configuration $`\alpha `$ has a mean height $`\epsilon _\alpha `$ that we calculate in the next section. One of the possible evolution from the configuration $`\alpha =3a`$ state is shown in Fig. 3.

This means that at the scale $`k+1`$ the mean height of the considered cell is critical with probability

$$\pi w_{\alpha =3}^{(a)}(\rho ^{})\frac{1}{6}p_2^{}\frac{1}{4}p_3^{}\frac{1}{6}p_2^{}$$
(3)
As a matter of fact, the cell has a probability $`\pi `$ to be a critical site at the scale $`k+1`$. The complete renormalization flow is therefore a sum over all the configuration and over all the possible paths of terms like $`\pi \epsilon _{\alpha =3}^{(k)}`$. In the same process we observe that with probability $`\pi `$ the quantity given outside of the cell, $`\delta \epsilon ^{(k+1)}`$, is $`3/2\delta \epsilon ^{(k)}`$. $`3`$ flows of energy $`\delta \epsilon ^{(k)}`$ are lost outside the cell passing through $`2`$ sides. It means that for this transformation we have to distinguish paths transferring the same energy through a different number of sides. The general transformations are

$`\epsilon _c^{(k+1)}`$ $`=`$ $`{\displaystyle \underset{\alpha }{}}w_\alpha (\rho ^{})\left[\epsilon _\alpha ^{(k)}{\displaystyle \underset{i}{}}P_{i,\alpha }(𝐏^{})\right]`$
$`\delta \epsilon ^{(k+1)}`$ $`=`$ $`{\displaystyle \underset{\alpha }{}}w_\alpha (\rho ^{})\left[{\displaystyle \underset{i}{}}P_{i,\alpha }^{n,m}(𝐏^{}){\displaystyle \frac{n}{m}}\delta \epsilon ^{(k)}\right]`$
where $`P_{i,\alpha }`$ are the probabilities relative to time evolutions that transfer energy outside of the cell, while $`P_{i,\alpha }^{n,m}`$ refers to a process that let $`n`$ quanta going through $`m`$ sides.

We compute now the average energy per site in all the configurations. We generalize the simple mean field argument described in ref., making the simpler non trivial assumption for the probability distribution of the energy: $`P(\epsilon )=a+b\epsilon `$. The normalization

$$_0^{\epsilon _c}𝑑\epsilon P(\epsilon )=1$$
(5)
implies that $`b=2(1a\epsilon _c)/\epsilon _c^2`$.

The average energy is then expressed in term of the parameter $`a`$:

$$\epsilon _0^{\epsilon _c}𝑑\epsilon \epsilon P(\epsilon )=\frac{2}{3}\epsilon _c\frac{1}{6}a\epsilon _c^2.$$
(6)
Following ref. we find that $`a0.277/\epsilon _c`$. The average energy of stable and critical sites is then:

$`\epsilon _{stable}`$ $``$ $`{\displaystyle \frac{\underset{0}{\overset{\epsilon _c\delta \epsilon }{}}𝑑\epsilon \epsilon P(\epsilon )}{\underset{0}{\overset{\epsilon _c\delta \epsilon }{}}𝑑\epsilon P(\epsilon )}}={\displaystyle \frac{\underset{0}{\overset{\epsilon _c\delta \epsilon }{}}𝑑\epsilon \left(a\epsilon +\frac{2}{\epsilon _c^2}\epsilon ^2(1a\epsilon _c)\right)}{\underset{0}{\overset{\epsilon _c\delta \epsilon }{}}𝑑\epsilon \left(a+\frac{2}{\epsilon _c^2}\epsilon (1a\epsilon _c)\right)}}`$ (7)
$`=`$ $`{\displaystyle \frac{\frac{2}{3}\frac{1}{6}a\epsilon _c\frac{\delta \epsilon }{\epsilon _c}\left(\frac{4}{3}\frac{5}{6}a\epsilon _c\right)+O(\delta \epsilon )^2}{\frac{1}{\epsilon _c}\left[1\frac{\delta \epsilon }{\epsilon _c}\left(1a\epsilon _c\right)\right]}}`$
$`=`$ $`\epsilon {\displaystyle \frac{2}{3}}\delta \epsilon \left(1{\displaystyle \frac{1}{4}}a^2\epsilon _c^2\right)+O(\delta \epsilon )^2`$
$`\epsilon _{critical}`$ $``$ $`{\displaystyle \frac{\underset{\epsilon _c\delta \epsilon }{\overset{\epsilon _c}{}}𝑑\epsilon \epsilon P(\epsilon )}{\underset{\epsilon _c\delta \epsilon }{\overset{\epsilon _c}{}}𝑑\epsilon P(\epsilon )}}={\displaystyle \frac{\underset{\epsilon _c\delta \epsilon }{\overset{\epsilon _c}{}}𝑑\epsilon \left(a\epsilon +\frac{2}{\epsilon _c^2}\epsilon ^2(1a\epsilon _c)\right)}{\underset{\epsilon _c\delta \epsilon }{\overset{\epsilon _c}{}}𝑑\epsilon \left(a+\frac{2}{\epsilon _c^2}\epsilon (1a\epsilon _c)\right)}}`$ (8)
$`=`$ $`{\displaystyle \frac{\epsilon _c(2a\epsilon _c)\delta \epsilon \left(2\frac{7}{2}a\epsilon _c\right)}{(2a\epsilon _c)\left[1\frac{\delta \epsilon }{\epsilon _c}\frac{1a\epsilon _c}{2a\epsilon _c}\right]}}`$
$`=`$ $`\epsilon _c\delta \epsilon {\displaystyle \frac{1\frac{5}{2}a\epsilon _c}{2a\epsilon _c}}+O(\delta \epsilon )^2`$
If we put $`a=0.277/\epsilon _c`$ in these expressions we obtain

$$\epsilon _{stable}=0.6205\epsilon _c0.539\delta \epsilon $$
(9)
$$\epsilon _{critical}=\epsilon _c0.1785\delta \epsilon $$
(10)
The average energy per site for different configurations can now be calculated as

$$\epsilon _{\alpha =2}=\frac{1}{4}\left[2\epsilon _{critical}+2\epsilon _{stable}\right]=0.810\epsilon _c0.359\delta \epsilon $$
(11)
$$\epsilon _{\alpha =3}=\frac{1}{4}\left[3\epsilon _{critical}+\epsilon _{stable}\right]=0.905\epsilon _c0.269\delta \epsilon $$
(12)
$$\epsilon _{\alpha =4}=\epsilon _{critical}=\epsilon _c0.1785\delta \epsilon $$
(13)
Equations for the renormalization flow have the form

$$\{\begin{array}{ccc}\hfill \epsilon _c^{(k+1)}& =& a\epsilon _c^{(k)}b\delta \epsilon ^{(k)}\hfill \\ \hfill \delta \epsilon ^{(k+1)}& =& c\delta \epsilon ^{(k)}\hfill \end{array}$$
(14)
where the coefficients $`a,b`$ and $`c`$ obviously depend on the fixed point parameters. If we divide the two equations, recalling the definition of the rigidity, we obtain

$$r^{(k+1)}=\frac{a}{c}r^{(k)}\frac{b}{c}.$$
(15)
The fixed point of the rigidity corresponds to setting $`r^{(k+1)}=r^{(k)}=r^{}`$:

$$r^{}=\frac{b}{ac}.$$
(16)
Next section deals with the calculation of the coefficients $`a,b`$ and $`c`$.

## III Analytical results

To calculate the coefficients $`a,b`$ and $`c`$ we have to distinguish between $`4`$ different kind of configurations, each one with the relative weights $`w_\alpha (\rho )`$ as calculated in ref..

$``$ $`\alpha =2`$

We consider at time $`t`$ one of the toppling represented in Fig. 4 and possible developments at time $`t+1`$ in Fig. 5.

All the paths described transfer energy outside the cell, the associated probabilities are given in captions. Configuration $`\alpha =2`$ then contributes with the term

$$\epsilon _c^{(k+1)}=w_{\alpha =2}(\rho )\epsilon _{\alpha =2}^{(k)}(\frac{1}{4}p_1+\frac{1}{2}p_2+\frac{3}{4}p_3+p_4)\times $$

$$\times \left(\frac{1}{2}p_1+\frac{5}{6}p_2+p_3+p_4\right)+\mathrm{}$$
(17)
to the renormalization of the critical energy. Moreover, each of the described paths transfer only a quantum of energy outside of the cell, so

$$\frac{\delta \epsilon ^{(k+1)}}{\delta \epsilon ^{(k)}}=w_{\alpha =2}(\rho )(\frac{1}{4}p_1+\frac{1}{2}p_2+\frac{3}{4}p_3+p_4)\times $$

$$\times \left(\frac{1}{2}p_1+\frac{5}{6}p_2+p_3+p_4\right)+\mathrm{}$$
(18)
The details of the calculations regarding paths from configurations $`\alpha =3a,\mathrm{\hspace{0.17em}3}b`$ and $`4`$ are given in the appendix.

The final result is obtained by summing all these contributes that we have explicitly calculated with the respective weights. We find for the coefficients the following values:

$$a=0.26\pm 0.03b=0.10\pm 0.02c=0.26\pm 0.05$$
(19)
We finally obtain that $`a`$ and $`c`$ are equal, even though the errors associated are relatively large. These errors are related to the parameters of the fixed point. Since they have only $`3`$ significant digits, that results an error of order $`10^3`$.

We then find that the fixed point spontaneously reached by a sandpile model corresponds to an infinite value of the rigidity. It means that every finite value for the microscopic dynamics renormalizes to an infinite one on a large scale.

The difference with a diffusive system is now clear: in the diffusive case a particle added from outside can always goes out of the system from the boundaries, while in a SOC system this is avoided by the value of the rigidity as bigger as observed from a large scale.

## IV Numerical Results

We present here the results of simulations made on BTW btw  and Zhang zh  models. We have measured for these systems the critical energy and the average flow transferred from the boundaries at a generic scale $`k`$. Critical energy is defined as follows: we consider an external perturbation on a site in a coarse grained cell ($`k`$-cell) of size $`l^{(k)}\times l^{(k)}`$ and we look at the avalanches starting from this coarse-grained cell. If the avalanche transfers energy outside the given $`k`$-cell we compute the average energy $`\epsilon _c^{(k)}`$ of that $`k`$-cell before the toppling; as a matter of fact, that $`k`$-cell is critical with a probability given by the frequency of the avalanches transferring energy outside the $`k`$-cell itself. Moreover, we define the energy transferred $`\delta \epsilon ^{(k)}`$ at the scale $`l^{(k)}`$ as the number of grains going outside the $`k`$-cell divided by the number of boundaries crossed and by the length $`l^{(k)}`$ (this is the trivial scaling).

If we look at numerical results (Fig. 6) we note that the critical energy at large scale is the average energy pr94  of the system and this is not surprising since at the scale of the system size this is exactly what we compute. As for the behaviour of $`\delta \epsilon `$ (Fig. 7) one gets that in the limit $`k\mathrm{}`$ it goes to zero. This result confirms the idea that the fixed point value for the rigidity is infinite, signalling a clear difference with respect to usual diffusive systems. The same qualitative results are obtained for the Zhang model zh  (See Fig. 8 and 9).

## V Conclusions

In summary we have investigated, both in the framework of the Dynamically Driven Renormalizaton Group scheme and by numerical simulations, the role of the so-called local rigidity in sandpile models. The local rigidity is defined as the ratio between the critical energy and the amplitude of the external perturbation, both at the microscopic scale. It turns out that, under the renormalization flow equations of the DDRG, the local rigidity renormalizes to an infinite fixed point value both for the BTW model and the Zhang model, while for a typical diffusive system one would expect a vanishing value. Numerical simulations of coarse-grained sandpile models confirm this picture.

Authors acknowledge EU contract FMRXCT980183 and G.C. acknowledge FET Open project COSIN IST-2001-33555.

## VI Appendix

$``$ $`\alpha =3a`$

In Fig. 10 we show all the possible paths starting from the perturbation of the critical site.

The probability relative to the first event at time $`t`$ is the same as before, $`\frac{1}{4}p_1+\frac{1}{2}p_2+\frac{3}{4}p_3+p_4`$. At time $`t+1`$ we have $`a`$) $`\frac{1}{4}p_1+\frac{1}{6}p_2`$ for the first two events in figure, $`\frac{1}{6}p_2+\frac{1}{4}p_3`$ for the third (they are distinguishable only with respect to renormalization of $`\delta \epsilon `$); $`b`$) $`\frac{1}{6}p_2+\frac{1}{4}p_3`$ for the first two events, $`\frac{1}{4}p_3+p_4`$ for the third; $`c`$) $`\frac{1}{4}p_1+\frac{1}{6}p_2`$.

At time $`t+2`$ we have $`\frac{1}{4}p_1+\frac{1}{3}p_2+\frac{1}{4}p_3`$ for the first two and $`\frac{1}{6}p_2+\frac{1}{2}p_3+p_4`$ for the third; in the renormalization of $`\epsilon _c`$ we have to consider only the sum $`\frac{1}{2}p_1+\frac{5}{6}p_2+p_3+p_4`$. So we can write

$$\epsilon _c^{(k+1)}=\mathrm{}+w_{\alpha =3}^{(a)}(\rho )\epsilon _{\alpha =3}^{(k)}(\frac{1}{4}p_1+\frac{1}{2}p_2+\frac{3}{4}p_3+p_4)\times $$

$$\times \left[\left(\frac{1}{2}p_1+\frac{5}{6}p_2+p_3+p_4\right)\left(1+\left(\frac{1}{4}p_1+\frac{1}{6}p_2\right)\right)\right]+\mathrm{}$$
(20)
and

$$\frac{\delta \epsilon ^{(k+1)}}{\delta \epsilon ^{(k)}}=\mathrm{}+w_{\alpha =3}^{(a)}(\rho )(\frac{1}{4}p_1+\frac{1}{2}p_2+\frac{3}{4}p_3+p_4)\times $$

$$\times [(\frac{1}{2}p_1+\frac{1}{2}p_2+\frac{1}{4}p_3)+(\frac{1}{6}p_2+\frac{1}{4}p_3)\times $$

$$\times \left(\left(\frac{1}{4}p_1+\frac{1}{3}p_2+\frac{1}{4}p_3\right)\left(2+1\right)+\left(\frac{1}{6}p_2+\frac{1}{2}p_3+p_4\right)\frac{3}{2}\right)+$$

$$+\left(\frac{1}{6}p_2+\frac{1}{4}p_3\right)\left(\frac{1}{2}p_1+\frac{5}{6}p_2+p_3+p_4\right)+\left(\frac{1}{4}p_3+p_4\right)$$

$$((\frac{1}{4}p_1+\frac{1}{3}p_2+\frac{1}{4}p_3)(\frac{3}{2}+1)+(\frac{1}{6}p_2+\frac{1}{2}p_3+p_4)\frac{4}{3})\times $$

$$\times (\frac{1}{4}p_1+\frac{1}{6}p_2)(\frac{1}{2}p_1+\frac{5}{6}p_2+p_3+p_4)]+\mathrm{}$$
(21)
for the contributions coming from the $`\alpha =3a`$ configuration.

$``$ $`\alpha =3b`$

We can compute the probabilities of the shown in Fig. 11.

At time $`t`$ we have to distinguish between two kinds of events: the toppling on a single site (this term is considered two times to include the toppling on the other site) and the one on two sites. The statistical weights are $`\left(\frac{1}{4}p_1+\frac{1}{3}p_2+\frac{1}{4}p_3\right)`$ and $`\left(\frac{1}{6}p_2+\frac{1}{2}p_3+p_4\right)`$ respectively. At time $`t+1`$ both the events leave one flow going outside the cell, so we have:

$$\epsilon _c^{(k+1)}=\mathrm{}+w_{\alpha =3}^{(b)}(\rho )\epsilon _{\alpha =3}^{(k)}\times $$

$$\times [2(\frac{1}{4}p_1+\frac{1}{2}p_2+\frac{3}{4}p_3+p_4)(\frac{1}{2}p_1+\frac{5}{6}+p_3+p_4)+$$

$$+(\frac{1}{6}p_2+\frac{1}{2}p_3+p_4)(1(\frac{1}{2}p_1+\frac{5}{6}p_2)^2)]+\mathrm{}$$
(22)
$$\frac{\delta \epsilon ^{(k+1)}}{\delta \epsilon ^{(k)}}=\mathrm{}+w_{\alpha =3}^{(b)}(\rho )\times $$

$$\times [2(\frac{1}{4}p_1+\frac{1}{2}p_2+\frac{3}{4}p_3+p_4)(\frac{1}{2}p_1+\frac{5}{6}+p_3+p_4)+$$

$$+(\frac{1}{6}p_2+\frac{1}{2}p_3+p_4)(1(\frac{1}{2}p_1+\frac{5}{6}p_2)^2)]+\mathrm{}$$
(23)
$``$ $`\alpha =4`$

In a cell with all critical sites the number of possible time evolutions grows enormously. In Fig. 12 we show the first two possible events, with probabilities $`p(a)=\frac{1}{4}p_1+\frac{1}{3}p_2+\frac{1}{4}p_3`$ and $`p(b)=\frac{1}{6}p_2+\frac{1}{2}p_3+p_4`$. The paths coming from $`a`$ are shown in Fig. 13 and the relatives probabilities in Table 1.

Now we have to compute $`224`$ paths from the $`b`$ event. The final result, avoiding details, for the renormalization of the critical height is

$$\epsilon _c^{(k+1)}=\mathrm{}+w_{\alpha =4}(\rho )\{2(\frac{1}{4}p_1+\frac{1}{3}p_2+\frac{1}{4}p_3)\times $$

$$\times [(\frac{1}{2}p_1+\frac{5}{6}p_2+p_3+p_4)(1+(\frac{1}{4}p_1+\frac{1}{6}p_2)+$$

$$+(\frac{1}{4}p_1+\frac{1}{6}p_2)^2)]+(\frac{1}{6}p_2+\frac{1}{2}p_3+p_4)[1\left(\frac{1}{4}p_1\right)^2+$$

$$(\frac{1}{4}p_1+\frac{1}{6}p_2)(\frac{3}{4}p_1+\frac{1}{6}p_2)(\frac{1}{2}p_1+\frac{1}{6}p_2)]\}$$
(24)
If we introduce the quantities

$`\pi _1`$ $``$ $`{\displaystyle \frac{1}{4}}p_1+{\displaystyle \frac{1}{2}}p_2+{\displaystyle \frac{3}{4}}p_3+p_4`$
$`\pi _2`$ $``$ $`{\displaystyle \frac{1}{2}}p_1+{\displaystyle \frac{5}{6}}p_2+p_3+p_4`$
$`\pi _3`$ $``$ $`{\displaystyle \frac{1}{2}}p_1+{\displaystyle \frac{1}{2}}p_2+{\displaystyle \frac{1}{4}}p_3`$
$`\pi _4`$ $``$ $`{\displaystyle \frac{1}{6}}p_2+{\displaystyle \frac{1}{4}}p_3`$
$`\pi _5`$ $``$ $`{\displaystyle \frac{1}{4}}p_1+{\displaystyle \frac{1}{3}}p_2+{\displaystyle \frac{1}{4}}p_3`$
$`\pi _6`$ $``$ $`{\displaystyle \frac{1}{6}}p_2+{\displaystyle \frac{1}{2}}p_3+p_4`$
$`\pi _7`$ $``$ $`{\displaystyle \frac{1}{4}}p_1+{\displaystyle \frac{1}{6}}p_2`$
$`\pi _8`$ $``$ $`{\displaystyle \frac{1}{2}}p_1+{\displaystyle \frac{1}{6}}p_2`$
$`\pi _9`$ $``$ $`{\displaystyle \frac{1}{4}}p_3+p_4`$
$`\pi _{10}`$ $``$ $`{\displaystyle \frac{3}{4}}p_1+{\displaystyle \frac{1}{2}}p_2+{\displaystyle \frac{1}{4}}p_3`$
then we can write down the renormalization of $`\delta \epsilon `$ as

$`{\displaystyle \frac{\delta E^{(k+1)}}{\delta E^{(k)}}}`$ $`=\mathrm{}+w_{\alpha =4}(\rho )\{2\pi _5[\pi _3+`$ (25)
$`\pi _4\left(2\pi _7+\pi _4\left(1+\pi _2+{\displaystyle \frac{5}{2}}\pi _5+{\displaystyle \frac{4}{3}}\pi _6\right)\right)+`$
$`+\pi _9\left({\displaystyle \frac{4}{3}}\pi _5+{\displaystyle \frac{5}{4}}\pi _6\right)+\pi _7\pi _2+\pi _7(2+1)+`$
$`+\pi _4\left({\displaystyle \frac{3}{2}}+\left({\displaystyle \frac{3}{2}}+{\displaystyle \frac{3}{2}}\right)\pi _5+\pi _6\right)+\pi _4\left(\left({\displaystyle \frac{3}{2}}+1\right)\pi _5+{\displaystyle \frac{4}{3}}\pi _6\right)+`$
$`+\pi _9((2+{\displaystyle \frac{4}{3}})\pi _5+{\displaystyle \frac{5}{3}}\pi _6)+\pi _7\pi _2)+\pi _9\times `$
$`\times (({\displaystyle \frac{3}{2}}+1)\pi _7++\pi _4({\displaystyle \frac{4}{3}}+{\displaystyle \frac{8}{3}}\pi _5+{\displaystyle \frac{5}{4}}\pi _6)+`$
$`\pi _4({\displaystyle \frac{7}{3}}\pi _5+{\displaystyle \frac{5}{4}}\pi _6)++\pi _9(({\displaystyle \frac{5}{3}}+{\displaystyle \frac{5}{4}})\pi _5++{\displaystyle \frac{3}{2}}\pi _6)+`$
$`+\pi _7\pi _2)+\pi _7(\pi _3+\pi _4(\pi _2+3\pi _5{\displaystyle \frac{3}{2}}\pi _6)+`$
$`+\pi _9({\displaystyle \frac{5}{2}}\pi _5+{\displaystyle \frac{4}{3}}\pi _6)+\pi _7\pi _2)]+\pi _6\times `$
$`[(\pi _{10}^2{\displaystyle \frac{1}{16}}p_1^2)++2(\pi _7\pi _5+{\displaystyle \frac{1}{4}}p_1\pi _4)(5\pi _5+{\displaystyle \frac{5}{2}}\pi _6)+`$
$`2\left(\pi _7\pi _6+{\displaystyle \frac{1}{4}}p_1\pi _9\right)\left({\displaystyle \frac{5}{2}}\pi _5+{\displaystyle \frac{4}{3}}\pi _6\right)+`$
$`+\left(2\pi _7\pi _4+\pi _4^2\right)\left(10\pi _5+{\displaystyle \frac{17}{3}}\pi _6\right)+\left(2\pi _7{\displaystyle \frac{1}{4}}p_1+\pi _7^2\right)\pi _2+`$
$`+2(\pi _4^2+\pi _9\pi _5)(5\pi _5+{\displaystyle \frac{35}{12}}\pi _6)+(2\pi _9\pi _4+\pi _9^2)\times `$
$`\times ({\displaystyle \frac{5}{2}}\pi _5+{\displaystyle \frac{3}{2}}\pi _6)]\}`$


format: text

text:
# A New Protocol and Lower Bounds for Quantum Coin Flipping

## 1 Introduction

In many cryptographic protocols, there is a need for random bits that are common to both parties. However, if one of parties is allowed to generate these random bits, this party may have a chance to influence the outcome of the protocol by appropriately picking the random bits. This problem can be solved by using a cryptographic primitive called coin flipping.

###### Definition 1

A coin flipping protocol with $`ϵ`$ bias is one where Alice and Bob communicate and finally decide on a value $`c\{0,1\}`$ such that

* If both Alice and Bob are honest, then $`Prob(c=0)=Prob(c=1)=1/2`$.
* If one of them is honest (follow the protocol), then, for any strategy of the dishonest player, $`Prob(c=0)1/2+ϵ`$, $`Prob(c=1)1/2+ϵ`$.

Classically, coin flipping was introduced by Blum. Classical coin flipping protocols are based on computational assumptions such as one-way functions.

However, classical one-way functions may not be hard against quantum adversaries. (For example, factoring and discrete log are not hard in the quantum case.) Finding a good candidate for a one-way function secure against quantum adversaries is an important open problem.

On the other hand, the unique properties of quantum mechanics allow the implementation of certain cryptographic tasks without any computational assumptions. (The security proof is based only on the validity of quantum mechanics.) The most famous example is the quantum key distribution. The question is: can we replace the computational assumptions of the classical case by information-theoretic security in the quantum case for the coin flipping?

For bit commitment (a related cryptographic primitive), this is impossible111It is possible, however, to have quantum protocols for bit commitment under quantum complexity assumptions (existence of quantum 1-way functions). See Dumais et.al. and Crepeau et.al.. The ideas of this impossibility proof can be used to show that there is no quantum protocol for perfect quantum coin flipping (quantum coin flipping with bias 0) . However, this still leaves the possibility that there might be quantum protocols with an arbitrarily small bias $`ϵ>0`$.

The first positive result was by Aharonov et.al. who gave a protocol for quantum coin flipping in which a dishonest party cannot force a given outcome with probability more than 0.9143…

There has been some effort to construct more complicated protocols which would achieve arbitrarily small $`ϵ>0`$. At least two protocols have been proposed: by Mayers et.al. and by Zhang et.al.. None of them had provable security guarantees but both were conjectured to achieve an arbitrarily small $`ϵ>0`$ for an appropriate choice of parameters. Both of them were eventually broken: the protocol of  was broken by 222The paper  claims to break any protocol for coin flipping but this claim is incorrect. It does break a class of protocols which includes the one of , though. and the protocol of  is insecure because of our Theorem 5.

In this paper, we give a simple protocol in which a dishonest party cannot achieve one outcome with probability more than 0.75.

Then, we show that our protocol is optimum in a certain class of protocols that includes our protocol, the protocol of  and other similar protocols.

Our third result (Theorem 5) shows that, if there is a protocol with an arbitrarily small bias $`ϵ>0`$, it must use a non-constant number of rounds of communication (not just communicate many qubits in a constant number of rounds). Namely, a coin flipping algorithm with a bias $`ϵ`$ needs to have at least $`\mathrm{\Omega }(\mathrm{log}\mathrm{log}\frac{1}{ϵ})`$ rounds. In particular, this means that the parallel repetition fails for quantum coin flipping. (One cannot decrease the bias arbitrarily by repeating the protocol in parallel many times.)

Related work. We have recently learned that two of results in this paper (the 0.75 protocol and the matching lower bound for a class of protocols) have been independently discovered by Spekkens and Rudolph . Also, Kitaev  has very recently shown that, in any protocol, at least one party can achieve one outcome with probability at least $`1/\sqrt{2}=0.71\mathrm{}`$. Thus, our 0.75 protocol is close to being optimal.

Curiously, Kitaev’s lower bound does not apply to a weaker version of coin flipping. In weak coin flipping, it is known in advance that Alice wants to bias the coin to 0 and Bob wants to bias it to 1. Then, it is enough to give guarantees about $`Pr[c=0]`$ if Bob is honest but Alice cheats and $`Pr[c=1]`$ if Alice is honest but Bob cheats. Protocols for weak coin flipping have been studied by Goldenberg , Spekkens and Rudolph  and Ambainis. The best protocol  achieves a maximum bias of $`1/\sqrt{2}`$. We note best lower bound for weak coin flipping is Theorem 5 of this paper.

The role of rounds in quantum communication has been studied in a different context (quantum communication complexity of pointer jumping) by Klauck et. al. . There is a popular survey of quantum cryptography by Gottesman and Lo.

## 2 Preliminaries

### 2.1 Quantum states

We briefly introduce the notions used in this paper. For more detailed explanations and examples, see .

An $`n`$-dimensional pure quantum state is a vector $`|\psi \text{ }\mathrm{C}^n`$ of norm 1. Let $`|0`$, $`|1`$, $`\mathrm{}`$, $`|n1`$ be an orthonormal basis for $`\text{ }\mathrm{C}^n`$. Then, any pure state can be expressed as $`|\psi =_{i=0}^{n1}a_i|i`$ for some $`a_0\text{ }\mathrm{C}`$, $`a_1\text{ }\mathrm{C}`$, $`\mathrm{}`$, $`a_{n1}\text{ }\mathrm{C}`$. Since the norm of $`|\psi `$ is 1, $`|a_i|^2=1`$.

The simplest special case is $`n=2`$. Then, the basis for $`\text{ }\mathrm{C}^2`$ consists of two vectors $`|0`$ and $`|1`$ and any pure state is of form $`a|0+b|1`$, $`a\text{ }\mathrm{C}`$, $`b\text{ }\mathrm{C}`$, $`|a|^2+|b|^2=1`$. Such quantum system is called a quantum bit (qubit).

We often look at $`|\psi `$ as a column vector consisting of coefficients $`a_i`$. Then, we use $`\psi |`$ to denote the conjugate transpose of $`|\psi `$. $`\psi |`$ is a row vector consisting of $`a_i^{}`$ (complex conjugates of $`a_i`$). In this notation, $`\psi |\varphi `$ denotes the inner product of $`\psi `$ and $`\varphi `$. (If $`|\psi =a_i|i`$, $`|\varphi =b_i|i`$, then $`\psi |\varphi =a_i^{}b_i`$.) $`|\psi \varphi |`$ denotes the outer product of $`\psi `$ and $`\varphi `$ (an $`n\times n`$ matrix with entries $`a_ib_j^{}`$).

A mixed state is a classical probability distribution $`(p_i,|\psi _i)`$, $`0p_i1`$, $`_ip_i=1`$ over pure states $`|\psi _i`$. The quantum system described by a mixed state is in the pure state $`|\psi _i`$ with probability $`p_i`$.

A mixed state can be also described by its density matrix $`\rho =_ip_i|\psi _i\psi _i|`$. It can be shown that any density matrix has trace 1. (A trace of a matrix is the sum of its diagonal entries.)

A quantum system can undergo two basic operations: a unitary evolution and a measurement.

: A unitary transformation $`U`$ is a linear transformation on $`\text{ }\mathrm{C}^k`$ that preserves the $`l_2`$ norm (i.e., maps vectors of unit norm to vectors of unit norm).

If, before applying $`U`$, the system was in a pure state $`|\psi `$, then the state after the transformation is $`U|\psi `$.

If, before $`U`$, the system was in a mixed state with a density matrix $`\rho `$, the state after the transformation is the mixed state with the density matrix $`U\rho U^{}`$.

: An observable is a decomposition of $`\text{ }\mathrm{C}^k`$ into orthogonal subspaces $`_1`$, $`\mathrm{}`$, $`_l`$: $`\text{ }\mathrm{C}^n=_1_2\mathrm{}_l`$. A measurement of a pure state $`|\psi `$ with respect to this observable gives the result $`i`$ with probability $`P_i|\psi ^2`$ where $`P_i|\psi `$ denotes the projection of $`|\psi `$ to the subspace $`_i`$. After the measurement, the state of the system becomes $`\frac{P_i|\psi }{P_i|\psi }`$.

A more general class of measurements are POVM measurements (see ). In most of this paper, it will be sufficient to consider projective measurements.

### 2.2 Bipartite states

In the analysis of quantum coin flipping protocols, we often have a quantum state part of which is held by Alice and the other part by Bob. For example, we can have the EPR state (the state of two qubits $`\frac{1}{\sqrt{2}}|0|0+\frac{1}{\sqrt{2}}|1|1`$), with the first qubit held by Alice and the second qubit held by Bob. Such states are called bipartite states.

If Alice measures her part, Bob’s part becomes a mixed state. For example, if Alice measures the first qubit of the EPR state in the basis consisting of $`|0`$ and $`|1`$, Bob’s state becomes $`|0`$ with probability 1/2 and $`|1`$ with probability 1/2. Let $`\rho `$ be the density matrix of the mixed state that Bob gets if Alice measures her part of a bipartite state $`|\psi `$. Then, we say that $`\rho `$ is obtained by tracing out the Alice’s part of $`|\psi `$.

There are many different ways how Alice can measure (trace out) her part. However, they all give the same density matrix $`\rho `$ for Bob’s part.

Let $`\rho `$ be a mixed state. Then, any pure state $`|\psi `$ of a larger system that gives $`\rho `$ if a part of the system is traced out is called a purification of $`\rho `$.

### 2.3 Distance measures between quantum states

We use two measures of distance between quantum states (represented by density matrices): trace distance and fidelity. For more information on these (and other) measures of distance between density matrices, see .

Let $`p=(p_1,\mathrm{},p_k)`$ and $`q=(q_1,\mathrm{},q_k)`$ be two classical probability distributions. Then, the variational distance between $`p`$ and $`q`$ is

$$|pq|=\underset{i=1}{\overset{k}{}}|p_iq_i|.$$

The variational distance characterizes how well one can distinguish the distributions $`p`$ and $`q`$.

In the quantum case, the counterpart of a probability distribution is a mixed state. The counterpart of the variational distance is the trace distance. It is defined as follows.

The trace norm of a matrix $`A`$ is the trace of $`|A|`$ where $`|A|=\sqrt{A^{}A}`$ is the positive square root of $`A^{}A`$. We denote the trace norm of $`A`$ by $`A_t`$. The following lemma relates the trace norm of $`\rho _1\rho _2`$ (which we also call trace distance between $`\rho _1`$ and $`\rho _2`$) with the variational distance between distributions obtained by measuring $`\rho _1`$ and $`\rho _2`$.

###### Lemma 1

 Let $`p_{\rho _1}^M`$, $`p_{\rho _2}^M`$ be the probability distributions generated by applying a measurement $``$ to mixed states $`\rho _1`$ and $`\rho _2`$. Then, for any (projective or POVM) measurement $``$, $`|p_{\rho _1}^Mp_{\rho _2}^M|\rho _1\rho _2_t`$ and there exists a measurement $``$ that achieves the variational distance $`\rho _1\rho _2_t`$.

We can always choose the measurement $``$ that achieves the variational distance $`\rho _1\rho _2_t`$ so that $``$ is a projective measurement and it has just two outcomes: 0 and 1.

Let $`|\psi _1`$ and $`|\psi _2`$ be two bipartite states. Let $`\rho _1`$ and $`\rho _2`$ be the mixed states obtained from $`|\psi _1`$ and $`|\psi _2`$ by tracing out (measuring) Alice’s part.

###### Lemma 2

 If $`\rho _1=\rho _2`$, then Alice can transform $`|\psi _1`$ into $`|\psi _2`$ by a transformation on her part of the state.

For example, consider the bipartite states

$$|\psi _1=\frac{1}{\sqrt{2}}(|00+|01),$$

$$|\psi _2=\frac{1}{2}(|00+|01+|10|11),$$

with the first qubit held by Alice and the second qubit held by Bob. If Alice measures her qubit of $`|\psi _1`$, Bob is left with $`|0`$ with a probability 1/2 and $`|1`$ with a probability 1/2. If Alice measures her qubit of $`|\psi _2`$, Bob is left with $`\frac{1}{\sqrt{2}}(|0+|1)`$ with a probability 1/2 and $`\frac{1}{\sqrt{2}}(|0|1)`$ with a probability 1/2. Both of those states have the same density matrix

$$\left(\begin{array}{ccc}1/2& 0& \\ 0& 1/2& \end{array}\right).$$

By lemma 2, this means that Alice can transform $`|\psi _1`$ into $`|\psi _2`$. Indeed, she can do that by applying the Hadamard transform $`H`$ to her qubit.

A generalization of lemma 2 is: if the two density matrices $`\rho _1`$ and $`\rho _2`$ are close, then Alice can transform $`|\psi _1`$ into a state $`|\psi _1^{}`$ that is close to $`|\psi _2`$.

In this case, the distance between the two density matrices is measured by the fidelity $`F(\rho _1,\rho _2)`$. The fidelity is defined as

$$F(\rho _1,\rho _2)=\underset{|\psi _1,|\psi _2}{\mathrm{max}}|\psi _1|\psi _2|^2,$$

over all choices of $`|\psi _1`$ and $`|\psi _2`$ that give density matrices $`\rho _1`$ and $`\rho _2`$ when a part of system is traced out.

###### Lemma 3

 Let $`\rho _1`$, $`\rho _2`$ be two mixed states with support in a Hilbert space $``$, $`𝒦`$ any Hilbert space of dimension at least $`dim()`$, and $`|\varphi _i`$ any purifications of $`\rho _i`$ in $`𝒦`$. Then, there is a local unitary transformation $`U`$ on $`𝒦`$ that maps $`|\varphi _2`$ to $`|\varphi _2^{}=IU|\varphi _2`$ such that

$$|\varphi _1|\varphi _2^{}|^2=F(\rho _1,\rho _2).$$

###### Lemma 4

$$F(\rho _1,\rho _2)=\left[Tr\left(\sqrt{\sqrt{\rho _1}\rho _2\sqrt{\rho _1}}\right)\right]^2.$$

The trace distance and the fidelity are closely related. If $`\rho _1`$ and $`\rho _2`$ are hard to distinguish for Bob, then Alice can transform $`|\psi _1`$ into a state close to $`|\psi _2`$ and vica versa. Quantitatively, this relation is given by

###### Lemma 5

 For any two mixed states $`\rho _1`$ and $`\rho _2`$,

$$1\sqrt{F(\rho _1,\rho _2)}\frac{1}{2}\rho _1\rho _2_t\sqrt{1F(\rho _1,\rho _2)}.$$

In particular, $`F(\rho _1,\rho _2)=0`$ if and only if $`\rho _1\rho _2_t=2`$.

## 3 A protocol with bias 0.25

Protocol: Define

$$|\varphi _{b,x}=\{\begin{array}{cc}\frac{1}{\sqrt{2}}|0+\frac{1}{\sqrt{2}}|1& \text{if }b=0\text{}x=0\\ \frac{1}{\sqrt{2}}|0\frac{1}{\sqrt{2}}|1& \text{if }b=0\text{}x=1\\ \frac{1}{\sqrt{2}}|0+\frac{1}{\sqrt{2}}|2& \text{if }b=1\text{}x=0\\ \frac{1}{\sqrt{2}}|0\frac{1}{\sqrt{2}}|2& \text{if }b=1\text{}x=1\end{array}$$

1. Alice picks a uniformly random $`b\{0,1\}`$ and $`x\{0,1\}`$ and sends $`|\varphi _{b,x}`$ to Bob.
2. Bob picks a uniformly random $`b^{}\{0,1\}`$, sends $`b^{}`$ to Alice.
3. Alice sends $`b`$ and $`x`$ to Bob, he checks if the state that he received from Alice in the $`1^{\mathrm{st}}`$ step is $`|\varphi _{b,x}`$ (by measuring it in with respect to in a basis consisting of $`|\varphi _{b,x}`$ and two vectors orthogonal to it)333For example, if $`b=x=0`$, then Bob could measure in the basis $`|\varphi _{00}=\frac{1}{\sqrt{2}}|0+\frac{1}{\sqrt{2}}|1`$, $`\frac{1}{\sqrt{2}}|0\frac{1}{\sqrt{2}}|1`$, $`|2`$.. If the outcome of the measurement is not $`|\varphi _{b,x}`$, he has caught Alice cheating and he stops the protocol.
4. Otherwise, the result of the coin flip is $`bb^{}`$.

###### Theorem 1

The bias of this protocol is $`0.25`$.

Proof: We bound the probability of dishonest Alice (or dishonest Bob) achieving $`bb^{}=0`$. The maximum probability of achieving $`bb^{}=1`$ is the same because the protocol is symmetric.

Case 1: Alice is honest, Bob cheats. If $`b=0`$, Alice sends a mixed state that is equal to $`\frac{1}{\sqrt{2}}(|0+|1)`$ with probability 1/2 and $`\frac{1}{\sqrt{2}}(|0|1)`$ with probability 1/2. If $`b=1`$, she sends a mixed state that is equal to $`\frac{1}{\sqrt{2}}(|0+|2)`$ with probability 1/2 and $`\frac{1}{\sqrt{2}}(|0|2)`$ with probability 1/2. The density matrices of these two mixed states are

$$\rho _0=\left(\begin{array}{ccc}\frac{1}{2}& 0& 0\\ 0& \frac{1}{2}& 0\\ 0& 0& 0\end{array}\right)\rho _1=\left(\begin{array}{ccc}\frac{1}{2}& 0& 0\\ 0& 0& 0\\ 0& 0& \frac{1}{2}\end{array}\right)$$

and $`\rho _0\rho _1_t=1`$. By Theorem 3 of , the probability that Bob achieves $`b=b^{}`$ is at most $`\frac{1}{2}+\frac{\rho _0\rho _1_t}{4}=\frac{3}{4}`$.

Case 2: Bob honest, Alice cheats.

Let $`\rho `$ be the density matrix of the state sent by Alice in the $`1^{\mathrm{st}}`$ step. The first step of the proof is to “symmetrize” Alice’s strategy so that it becomes easier to bound her success probability.

###### Lemma 6

There is a strategy for dishonest Alice where the state sent by Alice in the $`1^{\mathrm{st}}`$ round has the density matrix of the form

$$\rho ^{}=\left(\begin{array}{ccc}1\delta _1\delta _2& 0& 0\\ 0& \delta _1& 0\\ 0& 0& \delta _2\end{array}\right)$$
(1)
for some $`\delta _1`$ and $`\delta _2`$ and Alice achieves $`b=b^{}`$ with the same probability.

Proof: Let $`U_0=I`$,

$$U_1=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)U_2=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)$$

$$U_3=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right).$$

Assume that Alice, before sending the state $`|\psi `$ to Bob in the $`1^{\mathrm{st}}`$ round, applies $`U_i`$ to it and, then, in the $`3^{\mathrm{rd}}`$ round, replaces each description of $`|\varphi _{b,x}`$ by a description of $`U_i|\varphi _{b,x}`$. Then, Alice achieves the outcomes 0 and 1 and gets caught with the same probabilities as before because

1. For all $`i\{0,1,2,3\}`$, $`b\{0,1\}`$, $`x\{0,1\}`$, $`U_i|\varphi _{b,x}`$ is either $`|\varphi _{b,0}`$ or $`|\varphi _{b,1}`$, and
2. For any $`|\psi `$, the inner product between $`U_i|\psi `$ and $`U_i|\varphi _{b,x}`$ is the same as the inner product between $`|\psi `$ and $`|\varphi _{b,x}`$.

Probabilities of obtaining 0, 1 and getting caught also stay the same if Alice picks a uniformly random $`i\{0,1,2,3\}`$ and then applies $`U_i`$ to both the state sent in the $`1^{\mathrm{st}}`$ round and the description sent in the $`3^{\mathrm{rd}}`$ round. In this case, the density matrix of the state sent by Alice in the $`1^{\mathrm{st}}`$ round is $`\rho ^{}=\frac{1}{4}(U_0\rho U_0^{}+U_1\rho U_1^{}+U_2\rho U_2^{}+U_3\rho U_3^{})`$. For every $`j,k\{1,2,3\}`$, $`jk`$, $`(U_i\rho U_i^{})_{jk}`$ is equal to $`\rho _{jk}`$ for two $`i\{0,1,2,3\}`$ and to $`\rho _{jk}`$ for the two other $`i`$. Therefore, $`\rho _{jk}^{}=0`$ for all $`jk`$, i.e. $`\rho ^{}`$ is of the form (1).

###### Lemma 7

For “symmetrized” Alice’s strategy, the probability that Alice convinces Bob that $`b=0`$ is at most $`F(\rho ^{},\rho _0)`$.

Proof: Let

$$|\psi =\underset{i}{}a_i|i|\psi _i$$
(2)
be the purification of $`\rho ^{}`$ chosen by Alice if she want to convince Bob that $`b=0`$. For every $`|\psi _i`$, Alice sends to Bob a description of a state $`|\psi _i^{}`$ which is one of $`|\varphi _{b,x}`$, $`b\{0,1\}`$, $`x\{0,1\}`$.

Alice is trying to convince Bob that $`b=0`$. Therefore, we can assume that she always sends to Bob a description of $`|\varphi _{0,0}`$ or $`|\varphi _{0,1}`$. (Replacing a description of $`|\varphi _{1,x}`$ by a description of $`|\varphi _{0,x}`$ can only increase the probability of Bob accepting $`b=0`$, although it may simultaneously increase the probability of Alice caught cheating.)

We pair up each state $`|\psi _i`$ with the state $`|\psi _j=U_1|\psi _i`$ and each state $`U_2|\psi _i`$ with $`U_3|\psi _i=U_2U_1|\psi _i`$. Our “symmetrization” guarantees that

* if $`|\psi _i`$ and $`|\psi _j`$ are the two states in one pair, then $`a_i=a_j`$,
* if one of states in a pair has $`|\psi _i^{}=|\varphi _{0,0}`$, the other has $`|\psi _j^{}=U_1|\varphi _{0,0}=|\varphi _{0,1}`$, and conversely,
* $`\psi _i|\psi _i^{}=\psi _j|\psi _j^{}`$ (because performing $`U_1`$ maps $`|\psi _i`$ and $`|\psi _j`$ to $`|\psi _i^{}`$ and $`|\psi _j^{}`$, respectively).

Therefore, we can write the equation (2) as

$$|\psi =\underset{i}{}a_i\left(\frac{1}{\sqrt{2}}|i,0|\psi _{i,0}+\frac{1}{\sqrt{2}}|i,1|\psi _{i,1}\right)$$
(3)
with $`|\psi _{i,0}^{}=|\varphi _{0,0}`$ and $`|\psi _{i,1}^{}=|\varphi _{0,1}`$.

The probability that Bob accepts $`|\psi _{i,x}`$ as $`|\psi _{i,x}^{}`$ is $`|\psi _{i,x}|\psi _{i,x}^{}|^2`$. The total probability of Bob accepting is

$$\underset{i}{}\frac{1}{2}|a_i|^2(|\psi _{i,0}|\psi _{i,0}^{}|^2+|\psi _{i,1}|\psi _{i,1}^{}|^2).$$
(4)
Notice that, because of “symmetrization”, $`\psi _{i,0}|\psi _{i,0}^{}=\psi _{i,1}|\psi _{i,1}^{}`$. Therefore, if we define $`|\phi _i=\frac{1}{\sqrt{2}}|i,0|\psi _{i,0}+\frac{1}{\sqrt{2}}|i,1|\psi _{i,1}`$ and $`|\phi _i^{}=\frac{1}{\sqrt{2}}|i,0|\psi _{i,0}^{}+\frac{1}{\sqrt{2}}|i,1|\psi _{i,1}^{}`$, we have $`\phi _i|\phi _i^{}=\psi _{i,0}|\psi _{i,0}^{}=\psi _{i,1}|\psi _{i,1}^{}`$. This means that (4) is equal to

$$\underset{i}{}|a_i|^2|\phi _i|\phi _i^{}|^2.$$

Let $`\rho _i`$ be a mixed state which is $`|\psi _{i,0}`$ with probability 1/2 and $`|\psi _{i,1}`$ with probability 1/2. Then, $`\rho ^{}=_i|a_i|^2\rho _i`$. Since $`|\phi _i`$ and $`|\phi _i^{}`$ are purifications of $`\rho _i`$ and $`\rho _0`$, we have $`|\phi _i|\phi _i^{}|^2F(\rho _i,\rho _0)`$ and

$$\underset{i}{}|a_i|^2|\phi _i|\phi _i^{}|^2\underset{i}{}|a_i|^2F(\rho _i,\rho ).$$

By concavity of fidelity ,

$$\underset{i}{}|a_i|^2F(\rho _i,\rho _0)F(\underset{i}{}|a_i|^2\rho _i,\rho _0)=F(\rho ,\rho _0).$$

###### Lemma 8

The probability that Alice achieves $`bb^{}=0`$ (or, equivalently, $`bb^{}=1`$) is at most $`\frac{1}{2}(F(\rho ^{},\rho _0)+F(\rho ^{},\rho _1))`$.

Proof: With probability 1/2, Bob’s bit is $`b^{}=0`$. Then, to achieve $`bb^{}=0`$, Alice needs to convince him that $`b=0`$. By Lemma 7, she succeeds with probability at most $`F(\rho ^{},\rho _0)`$.

With probability 1/2, Bob’s bit is $`b^{}=1`$. Then, Alice needs to convince Bob that $`b=1`$ and she can do that with probability $`F(\rho ^{},\rho _1)`$. The overall probability that Alice succeeds is $`\frac{1}{2}(F(\rho ^{},\rho _0)+F(\rho ^{},\rho _1))`$.

By Lemma 4,

$$F(\rho ^{},\rho _0)=[Tr(\sqrt{\sqrt{\rho ^{}}\rho _0\sqrt{\rho ^{}}})]^2=\left(\frac{1}{\sqrt{2}}\sqrt{1\delta _1\delta _2}+\frac{1}{\sqrt{2}}\sqrt{\delta _1}\right)^2.$$

Similarly, $`F(\rho ^{},\rho _1)=(\frac{1}{\sqrt{2}}\sqrt{1\delta _1\delta _2}+\frac{1}{\sqrt{2}}\sqrt{\delta _2})^2`$. Therefore,

$$\frac{1}{2}(F(\rho ^{},\rho _0)+F(\rho ^{},\rho _1))$$

$$=(\frac{1}{\sqrt{2}}\sqrt{1\delta _1\delta _2}+\frac{1}{\sqrt{2}}\sqrt{\delta _1})^2+(\frac{1}{\sqrt{2}}\sqrt{1\delta _1\delta _2}+\frac{1}{\sqrt{2}}\sqrt{\delta _2})^2$$

$$=\frac{1}{2}\left((1\delta _1\delta _2)+\frac{\delta _1}{2}+\frac{\delta _2}{2}+\sqrt{1\delta _1\delta _2}(\sqrt{\delta _1}+\sqrt{\delta _2})\right).$$
(5)
Let $`\delta =\frac{\delta _1+\delta _2}{2}`$. The convexity of the square root implies that $`\sqrt{\delta _1}+\sqrt{\delta _2}2\sqrt{\delta }`$ and (5) is at most

$$\frac{1}{2}\left(1\delta +2\sqrt{\delta (12\delta )}\right).$$

Taking the derivative of this expression shows that it is maximized by $`\delta =\frac{1}{6}`$. Then, it is equal to $`\frac{1}{2}(1\frac{1}{6}+\frac{4}{6})=\frac{3}{4}`$.

## 4 Lower bound for 3 rounds

We show a lower bound for a class of 3 round protocols which includes the protocol of section 3 and the protocol of . This class is defined by fixing the structure of the protocol and varying the choice of states $`|\varphi _{b,x}`$.

Let $`X_0`$ and $`X_1`$ be two sets and $`\pi _0`$ and $`\pi _1`$ be probability distributions over $`X_0`$ and $`X_1`$, respectively. Assume that, for every $`b\{0,1\}`$ and $`xX_b`$ we have a state $`|\varphi _{b,x}`$.

1. Alice picks a uniformly random $`b\{0,1\}`$. Then, she picks $`xX_b`$ according to the distribution $`\pi _b`$ and sends $`|\varphi _{b,x}`$ to Bob.
2. Bob picks a random $`b^{}\{0,1\}`$, sends $`b^{}`$ to Alice.
3. Alice sends $`b`$ and $`x`$ to Bob. Bob checks if the state that he received in the $`1^{\mathrm{st}}`$ step is $`|\varphi _{b,x}`$.
4. The result of the coin flip is $`bb^{}`$.

###### Theorem 2

Any protocol of this type has a bias at least 0.25.

Proof: Let $`\rho _0`$ and $`\rho _1`$ be the density matrices sent by an honest Alice if $`b=0`$ and $`b=1`$, respectively. (These density matrices are mixtures of $`|\varphi _{b,x}`$ over $`xX_i`$.)

###### Lemma 9

Bob can achieve 0 with probability $`\frac{1}{2}+\frac{\rho _0\rho _1_t}{4}`$.

Proof: By Lemma 1, there is a measurement $``$ that, applied to $`\rho _0`$ and $`\rho _1`$, produces two probability distributions with the variational distance between them equal to $`\rho _0\rho _1_t`$ and it can be chosen so that there are just two outcomes: 0 and 1.

Let $`p_0`$ and $`1p_0`$ be the probabilities of outcomes 0 and 1 when the measurement $``$ is applied to $`\rho _0`$. For the variational distance to be $`\rho _0\rho _1_t`$, the probabilities of outcomes 0 and 1 when the measurement $``$ is applied to $`\rho _1`$ have to be $`p_0\frac{\rho _0\rho _1_t}{2}`$ and $`1p_0+\frac{\rho _0\rho _1_t}{2}`$.

Bob applies the measurement $``$ to the state that he receives from Alice and sends $`b=0`$ if the measurement gives 0 and $`b=1`$ if the measurement gives 1. Since an honest Alice chooses $`a=0`$ with probability 1/2 and $`a=1`$ with probability 1/2, Bob achieves $`a=b`$ (and $`ab=0`$) with probability

$$\frac{1}{2}p_0+\frac{1}{2}\left(1p_0+\frac{\rho _0\rho _1_t}{2}\right)=\frac{1}{2}+\frac{\rho _0\rho _1_t}{4}.$$

###### Lemma 10

Alice can achieve 0 with probability

$$\frac{1}{2}+\frac{\sqrt{F(\rho _0,\rho _1)}}{2}.$$

Proof: First, we consider an honest Alice which does the protocol on a quantum level. That means that she flips a classical coin to determine $`a\{0,1\}`$ and then prepares the superposition

$$|\psi _a=\underset{iX_a}{}\sqrt{\pi _a(i)}|i|\varphi _{a,i}$$

and sends the second part of the superposition to Bob. After receiving $`b`$ from Bob, she measures $`i`$ and sends $`a`$ and $`i`$ to Bob.

The pure states $`|\psi _0`$ and $`|\psi _1`$ are purifications of the density matrices $`\rho _0`$ and $`\rho _1`$. By Lemma 3, there is a unitary transformation $`U`$ on the Alice’s part of $`\psi _1`$ such that $`|\psi _0|U(\psi _1)^2=F(\rho _0,\rho _1)`$.

Let $`\alpha `$ be such that $`F(\rho _0,\rho _1)=\mathrm{cos}^2\alpha `$. Then, $`\psi _0|U(\psi _1)=\mathrm{cos}\alpha `$. This means that

$$\{\begin{array}{c}|\psi _0=\mathrm{cos}\frac{\alpha }{2}|\phi _0+\mathrm{sin}\frac{\alpha }{2}|\phi _1\hfill \\ U|\psi _1=\mathrm{cos}\frac{\alpha }{2}|\phi _0\mathrm{sin}\frac{\alpha }{2}|\phi _1\hfill \end{array}$$

for some states $`|\phi _0`$, $`|\phi _1`$.

A dishonest Alice prepares $`|\phi _0`$ and sends the $`2^{\mathrm{nd}}`$ part to Bob. If she receives $`b^{}=0`$ from Bob, she acts as an honest quantum Alice who has prepared $`|\psi _0`$ and sent the $`2^{\mathrm{nd}}`$ part to Bob. (That is, she measures her part $`|i`$ and sends 0 and $`i`$ to Bob.) Bob accepts $`b=0`$ with probability at least444For a formal proof of this, define $``$ to be the space of all bipartite states $`|\psi `$ such that Bob accepts with probability 1, if Alice acts in this way. Then, $`|\psi _0`$ and, since the angle between $`|\phi _0`$ and $`|\psi _0`$ is $`\frac{\alpha }{2}`$, the squared projection of $`|\phi _0`$ on $``$ is at least $`\mathrm{cos}^2\frac{\alpha }{2}`$, implying that Bob accepts with probability at least $`\mathrm{cos}^2\frac{\alpha }{2}`$ if Alice starts with $`|\phi _0`$. $`|\psi _0|\phi _0|^2=\mathrm{cos}^2\frac{\alpha }{2}`$.

If she receives $`b^{}=1`$, Alice performs $`U^1`$ on her part of $`|\phi _0`$ and continues as an honest quantum Alice who has prepared $`|\psi _1`$ (measures $`|i`$ and sends to 1 and $`i`$ to Bob). Bob accepts $`b=1`$ with probability

$$|U^1(\phi _0)|\psi _1|^2=|\phi _0|U(\psi _1)|^2=\mathrm{cos}^2\frac{\alpha }{2}.$$

In both cases, the probability of Bob accepting $`bb^{}=0`$ is $`\mathrm{cos}^2\frac{\alpha }{2}`$. Therefore, the overall probability of $`bb^{}=0`$ is $`\mathrm{cos}^2\frac{\alpha }{2}`$ as well and we have

$$\mathrm{cos}^2\frac{\alpha }{2}=\frac{1+\mathrm{cos}\alpha }{2}=\frac{1+\sqrt{F(\rho _0,\rho _1)}}{2}.$$

If $`F(\rho _0,\rho _1)\frac{1}{4}`$, then, by Lemma 10, Alice can achieve a bias of $`\frac{\sqrt{F(\rho _0,\rho _1)}}{2}\frac{1}{4}`$.

If $`F(\rho _0,\rho _1)\frac{1}{4}`$, then, by Lemma 9, Bob can achieve a bias of $`\frac{1}{4}\rho _0\rho _1_t`$ and, by Lemma 5,

$$\frac{1}{4}\rho _0,\rho _1_t\frac{1}{2}(1\sqrt{F(\rho _0,\rho _1)})\frac{1}{4}.$$

## 5 Two standard forms for quantum protocols

We use the following “standard form” for quantum protocols.

###### Theorem 3

 If there is a protocol for quantum coin flipping with a bias at most $`ϵ`$, there is also a protocol with bias at most $`ϵ`$ in which no party makes measurements until all communication is complete.

The main idea of the proof of Theorem 3 is that all measurements can be delayed till the end of protocol. For more details, see Mayers . This result has been very useful for proving the impossibility of quantum bit commitment  and other cryptographic primitives.

A different “standard form” has been pointed out to us by Kitaev .

###### Theorem 4

 If there is a protocol for quantum coin flipping with a bias $`ϵ`$, there is another protocol with bias $`ϵ`$ in which only the first message from Alice to Bob is quantum and all the other messages are classical.

The proof idea is that Alice transmits a lot of EPR pairs in the first round and, after that, Alice and Bob can replace all quantum communication by classical communication using teleportation.

We do not use this result in our paper but we decided to mention it because it might be useful for other purposes. The protocols of the form of Theorem 4 have a fairly simple structure. In the first step Alice creates an entangled state with Bob and then they both do operations on their qubits and communicate classical information. Because of this simple structure, they might be easier to analyze than general protocols. We note that this structure of a protocol somewhat resembles the well-known LOCC (local operations and classical communication) paradigm in the study of entanglement .

## 6 The lower bound on the number of rounds

###### Theorem 5

Let $`ϵ<1/4`$. Any protocol for quantum coin flipping that achieves a bias $`ϵ`$ must use $`\mathrm{\Omega }(\mathrm{log}\mathrm{log}\frac{1}{ϵ})`$ rounds.

Assume we have a protocol for quantum coin flipping with $`k`$ rounds and a bias $`ϵ`$. By Theorem 3, we can assume that this protocol does not make any measurements till the end of communication.

The protocol starts with a fixed starting state $`|\psi ^0`$. Then (if both players are honest), Alice applies a unitary transformation $`U_1`$, sends some qubits to Bob, he applies $`U_2`$, sends some qubits to Alice and so on. After $`U_k`$, both Alice and Bob perform measurements on their parts. Since there is no measurements till the communication is finished, the joint state of Alice and Bob after $`i`$ steps is a pure state $`|\psi ^i`$.

At the end of protocol, Alice and Bob measure the final state to determine the outcome of the coin flip. If both Alice and Bob follow the protocol, the two measurements give the same result and this result is 0 with probability 1/2 and 1 with probability 1/2.

For our analysis, we decompose each of intermediate states $`|\psi ^i`$ as $`|\psi _0^i+|\psi _1^i`$, where $`|\psi _0^i`$ is the state which leads to the outcome 0 if the rest of protocol is applied and $`|\psi _1^i`$ is the state which leads to the outcome 1 if the rest of protocol is applied. This is done as follows.

First, we decompose the final state $`|\psi ^k`$. Let $`|\psi _0^k`$ and $`|\psi _1^k`$ be the (unnormalized) states after the final measurement if the measurement gives 0 (1). Then, $`|\psi _0^k|\psi _1^k`$ and $`|\psi ^k=|\psi _0^k+|\psi _1^k`$. Also, $`\psi _0^k^2=\psi _1^k^2=\frac{1}{2}`$ (since a protocol must give 0 with probability 1/2 and 1 with probability 1/2).

Next, we define $`|\psi _0^i=(U_{i+1}U_{i+2}\mathrm{}U_k)^1|\psi _0^k`$ and $`|\psi _1^i=(U_{i+1}U_{i+2}\mathrm{}U_k)^1|\psi _1^k`$. Then, $`|\psi ^k=|\psi _0^k+|\psi _1^k`$ implies $`|\psi ^i=|\psi _0^i+|\psi _1^i`$.

Let $`\rho _{A,j}^i`$ ($`\rho _{B,j}^i`$) be the density matrix of Alice’s (Bob’s) part of the (normalized) bipartite state $`\sqrt{2}|\psi _j^i`$. Let $`F_A^i`$ ($`F_B^i`$) be the fidelity between $`\rho _{A,0}^i`$ and $`\rho _{A,1}^i`$ ($`\rho _{B,0}^i`$ and $`\rho _{B,1}^i`$).

Our proof is based on analyzing how $`F_A^i`$ and $`F_B^i`$ change during the protocol. We show that they must be large at the beginning, 0 at the end and, if they decrease too fast, this creates an opportunity for cheating. This implies the lower bound on the number of rounds.

We start with the simplest part of the proof: $`F_A^i`$ and $`F_B^i`$ must be small at the end ($`i=k`$).

###### Lemma 11

$`F_A^k=F_B^k=0`$.

Proof: At the end, both Alice and Bob know the outcome of the protocol with certainty. That means that there is a measurement of Alice’s qubits that perfectly distinguishes $`|\psi _0^k`$ and $`|\psi _1^k`$ (i.e., this measurement gives 0 with probability 1 on $`|\psi _0^k`$ and 1 with probability $`|\psi _1^k`$). By Lemma 1, $`\rho _{A,0}^k\rho _{A,1}^k_t=2`$. By Lemma 5, $`F(\rho _{A,0}^k,\rho _{A,1}^k)`$ must be 0.

Similarly, $`F_B^k=0`$.

Second, we show that, if $`F_A^0`$ or $`F_B^0`$ is too small, one of sides can cheat.

###### Lemma 12

Alice can achieve one of outcomes 0 and 1 with probability at least $`1\sqrt{F_A^0}`$.

Proof: Since there is no communication before the start of the protocol, the starting superposition $`|\psi ^0`$ is a tensor product $`|\psi _A|\psi _B`$, with Alice having $`|\psi _A`$ and Bob having $`|\psi _B`$.

Consider the best measurement $``$ (for Alice) that distinguishes $`\rho _{A,0}^0`$ and $`\rho _{A,1}^0`$ (Lemma 1). Then, $`|\psi _0^0=|\psi _{00}+|\psi _{01}`$, where $`|\psi _{00}`$ is the remaining state if the measurement $``$ on $`|\psi _0^0`$ gives the outcome 0 and $`|\psi _{01}`$ is the remaining state if $``$ gives the outcome 1. Let $`|\psi _1^0=|\psi _{10}+|\psi _{11}`$, with $`|\psi _{10}`$ and $`|\psi _{11}`$ defined similarly.

If Alice applies $``$ to $`|\psi ^0=|\psi _0^0+|\psi _1^0`$, she either gets the outcome 0 and the remaining state $`|\psi _0^{}=|\psi _{00}+|\psi _{10}`$ or 1 and the remaining state $`|\psi _1^{}=|\psi _{01}+|\psi _{11}`$. $`|\psi ^0`$ is a product state and the measurement $``$ is applied to Alice’s side only. Therefore, $`|\psi _0^{}`$ and $`|\psi _1^{}`$ (the remaining states when $``$ gives 0 and 1) are product states as well.

Since $`|\psi ^0=|\psi _0^{}+|\psi _1^{}`$, either $`\psi _0^{}^2\frac{1}{2}`$ or $`\psi _1^{}^2\frac{1}{2}`$. For simplicity, we assume that $`\psi _0^{}^2\frac{1}{2}`$ and Alice is trying to achieve the outcome 0. (The outcome 1 can be achieved similarly with a slightly smaller probability.)

Let $`|\psi _A^{}|\psi _B`$ be the normalized state $`\frac{|\psi _0^{}}{\psi _0^{}}`$. To bias the coin towards 0, Alice just runs the honest protocol with her starting state being $`|\psi _A^{}`$ instead of $`|\psi _A`$.

Let $`\psi _{01}^2+\psi _{10}^2ϵ`$. We show that this implies that $`|\psi _A^{}|\psi _B`$ is close to the normalized state $`\sqrt{2}|\psi _0^0`$ (which gives the outcome 0 with probability 1). We have

$$\frac{|\psi _0^{}}{\psi _0^{}}=\frac{|\psi _{00}+|\psi _{10}}{\psi _0^{}}=\frac{|\psi _{00}+|\psi _{01}}{\psi _0^{}}+\frac{|\psi _{10}|\psi _{01}}{\psi _0^{}}.$$

$`|\psi _{00}+|\psi _{01}=|\psi _0^0`$ leads to the outcome 0 with certainty. Therefore, the probability of a different outcome (1 or Alice caught cheating) is at most

$$\frac{\psi _{10}\psi _{01}^2}{\psi _0^{}^2}\frac{\psi _{10}^2+\psi _{01}^2}{\psi _0^{}^2}\frac{ϵ}{1/2}=2ϵ.$$

Therefore, the described strategy for dishonest Alice gives 0 with probability at least $`12ϵ`$.

Next, we bound $`\psi _{01}^2+\psi _{10}^2`$.

Let $`1p_0`$ and $`p_0`$ be the probabilities of outcomes 0 and 1 when measuring $`\sqrt{2}|\psi _0^i`$. Let $`p_1`$ and $`1p_1`$ be the probabilities of 0 and 1 when measuring $`\sqrt{2}|\psi _1^i`$. Then, the variational distance between these two probability distributions is $`2(1p_0p_1)`$. Since we are using the best measurement for distinguishing $`\rho _{A,0}^0`$ and $`\rho _{A,1}^0`$, $`2(1p_0p_1)`$ is equal to $`\rho _{A,0}^0\rho _{A,1}^0_t`$. By Lemma 5, this implies

$$1\sqrt{F_A^0}=1\sqrt{F(\rho _{A,0}^0,\rho _{A,1}^0)}\rho _{A,0}^0\rho _{A,1}^0_t=(1p_0p_1)$$

and this is equivalent to $`p_0+p_1\sqrt{F_A^0}`$.

Notice that $`p_0=2\psi _{01}^2`$ because $`\rho _{A,0}^0`$ is the density matrix of Alice’s side of $`\sqrt{2}|\psi _{A,0}^0`$ and $`|\psi _{01}`$ is the remaining state if the measurement of $`|\psi _{A,0}^0`$ gives 1. Similarly, $`p_1=2\psi _{10}^2`$. Therefore, we have $`\psi _{01}^2+\psi _{10}^2\frac{1}{2}\sqrt{F_A^0}`$ and Alice can bias the coin to 0 with probability at least $`1\sqrt{F_A^0}`$.

Hence, if the bias of a protocol is $`ϵ`$, then, by Definition 1, we must have $`1\sqrt{F_A^0}\frac{1}{2}+ϵ`$. This implies $`\sqrt{F_A^0}\frac{1}{2}ϵ`$ and $`F_A^0(\frac{1}{2}ϵ)^2`$. Since $`ϵ<1/4`$, we must have $`F_A^0\frac{1}{16}`$.

Third, we show that, if after any round, one of $`F_A^i`$ and $`F_B^i`$ is much larger than the other, this also creates a possibility for cheating.

###### Lemma 13

Let $`i\{1,\mathrm{},k1\}`$. Then, there is a strategy for dishonest Alice which achieves the result 0 with probability at least

$$\left(\frac{1}{\sqrt{2}}\sqrt[4]{F_A^i}\right)^2+\left(\frac{\sqrt{F_B^i}}{\sqrt{2}}\sqrt[4]{F_A^i}\right)^2.$$
(6)
Proof: For brevity, we denote $`F_A^i`$ and $`F_B^i`$ by $`F_A`$ and $`F_B`$ (omitting the index $`i`$ which is the same throughout the proof).

We first prove the $`F_A=0`$ case. This case was previously considered by Mayers et.al.. They showed that, if $`F_A=0`$ and $`F_B>0`$, then Alice can successfully cheat. Below, we show how to formalize their argument so that it shows the probability that Alice can achieve.

$`F_A=0`$ case. Then, (6) is just $`\frac{1}{2}+\frac{F_B}{2}`$.

By Lemma 5, $`F(\rho _{A,0}^i,\rho _{A,1}^i)=F_A=0`$ implies $`\rho _{A,0}^i\rho _{A,1}^i_t=2`$. By Lemma 1, there is a measurement for Alice that perfectly distinguishes $`\rho _{A,0}^i`$ and $`\rho _{A,1}^i`$. With probability 1/2, the outcome of the measurement is 0 and the joint state of Alice and Bob after the measurement is $`|\psi _0^i`$. With probability 1/2, the outcome is 1 and the joint state of Alice and Bob becomes $`|\psi _1^i`$. In the first case, she just continues as in the honest protocol. This gives the answer 0 with probability 1/2.

If she gets $`|\psi _1^i`$, by Lemma 3, there is a unitary transformation $`U`$ that can be performed by Alice such that

$$|\psi _0^i|U(\psi _1^i)|^2=F(\rho _{B,0}^i,\rho _{B,1}^i)\psi _0^i^2=\frac{F(\rho _{B,0}^i,\rho _{B,1}^i)}{2}=\frac{F_B}{2}.$$
(7)
Alice performs $`U`$ and then continues as in the honest protocol. This gives the answer 0 with probability at least $`F_B/2`$.

Together, the probability of answer 0 is at least $`\frac{1}{2}(1+F_B)`$.

$`F_A0`$ case. By Lemma 5, there is a measurement $``$ for Alice that, applied to $`\rho _{A,0}^i`$ and $`\rho _{A,1}^i`$, produces two probability distributions with the variational distance between them at least $`2(1\sqrt{F_A})`$. Without the loss of generality, we can assume that this is a measurement with two outcomes 0 and 1 and the probability of 0 is higher for $`\rho _{A,0}^i`$ and the probability of 1 is higher for $`\rho _{A,1}^i`$.

The strategy for cheating Alice is the same as in the $`F_A=0`$ case. She applies the measurement $``$ and, then, if she gets 0, continues as in the honest protocol. If she gets 1, she applies the transformation $`U`$ and then continues as in the honest protocol.

Next, we show that this strategy achieves the result 0 with the probability given by the formula (6).

Let $`|\psi _0^{}`$ and $`|\psi _1^{}`$ denote the (unnormalized) remaining states when the outcome of the measurement $``$ is 0 and 1, respectively.

Also, let $`|\psi _{ab}`$ (for $`a,b\{0,1\}`$) denote the (unnormalized) remaining states when $`|\psi _a^i`$ is measured and the outcome of the measurement is $`b`$. Since $`|\psi ^i=|\psi _0^i+|\psi _1^i`$, we have $`|\psi _0^{}=|\psi _{00}+|\psi _{10}`$ and $`|\psi _1^{}=|\psi _{01}+|\psi _{11}`$.

On the other hand, $`|\psi _0^i=|\psi _{00}+|\psi _{01}`$ and $`|\psi _1^i=|\psi _{10}+|\psi _{11}`$. Therefore,

$$\psi _0^{}\psi _0^i=\psi _{10}\psi _{01}\psi _{10}+\psi _{01}\sqrt{2(\psi _{10}^2+\psi _{01}^2)}.$$
(8)
Similarly to the proof of Lemma 12, $`\psi _{10}^2+\psi _{01}^2\frac{1}{2}\sqrt{F_A}`$. Therefore, (8) is at most $`\sqrt[4]{F_A}`$. We also have $`\psi _1^{}\psi _1^i\sqrt[4]{F_A}`$ with the same proof.

Let $`_0^i`$ be the set of bipartite states such that applying the rest of the protocol ($`U_kU_{k1}\mathrm{}U_{i+1}`$) and the final measurement at the end of the protocol gives the outcome 0 with probability 1. Then, $`|\psi _0^i_0^i`$. Also, the norm of the projection of $`U(|\psi _1^i)`$ on $`_0^i`$ is at least $`\sqrt{F_B/2}`$ (by (7)).

Consider the norms of the projections of $`|\psi _0^{}`$ and $`|\psi _1^{}`$ on $`_0^i`$. They differ from the norms of $`|\psi _0^i`$ and $`|\psi _1^i`$ by at most $`\psi _0^{}\psi _0^i\sqrt[4]{F_A}`$ and $`\psi _1^{}\psi _1^i\sqrt[4]{F_A}`$. Therefore, the projection of $`|\psi _0^{}`$ on $`_0^i`$ is of norm at least $`\frac{1}{\sqrt{2}}\sqrt[4]{F_A}`$ and the projection of $`U|\psi _1^{}`$ is of norm at least $`\frac{\sqrt{F_B}}{\sqrt{2}}\sqrt[4]{F_A}`$. This means that the probability of outcome 0 is at least

$$\left(\frac{1}{\sqrt{2}}\sqrt[4]{F_A}\right)^2+\left(\frac{\sqrt{F_B}}{\sqrt{2}}\sqrt[4]{F_A}\right)^2.$$

For the purposes of this paper, a weaker form of lemma 13 is sufficient.

###### Corollary 1

Let $`i\{1,\mathrm{},k1\}`$. Then, there is a strategy for dishonest Alice which achieves the result 0 with probability at least $`\frac{1}{2}+\frac{F_B}{2}2\sqrt{2}\sqrt{F_A}`$.

Proof: We have

$$\left(\frac{1}{\sqrt{2}}\sqrt[4]{F_A}\right)^2+\left(\frac{\sqrt{F_B}}{\sqrt{2}}\sqrt[4]{F_A}\right)^2$$

$$=\left(\frac{1}{2}\sqrt{2}\sqrt[4]{F_A}+\sqrt{F_A}\right)+\left(\frac{F_B}{2}\sqrt{2}\sqrt{F_B}\sqrt[4]{F_A}+\sqrt{F_A}\right)$$

$$\left(\frac{1}{2}\sqrt{2}\sqrt[4]{F_A}\right)+\left(\frac{F_B}{2}\sqrt{2}\sqrt[4]{F_A}\right)$$

$$=\frac{1}{2}+\frac{F_B}{2}2\sqrt{2}\sqrt[4]{F_A}.$$

###### Corollary 2

Assume that the bias of a protocol is at most $`ϵ`$. Then, after every round, $`F_B2ϵ+6\sqrt[4]{F_A}`$ and $`F_A2ϵ+6\sqrt[4]{F_B}`$.

Proof: By Lemma 13, Alice can achieve $`Pr[0]=\frac{1}{2}+\frac{F_B}{2}2\sqrt{2}\sqrt[4]{F_A}`$. Because the bias of the protocol is at most $`ϵ`$, we must have $`\frac{F_B}{2}2\sqrt{2}\sqrt[4]{F_A}ϵ`$ and $`F_B2ϵ+4\sqrt{2}\sqrt[4]{F_A}2ϵ+6\sqrt[4]{F_A}`$.

$`F_A2ϵ+6\sqrt[4]{F_B}`$ follows similarly.

Next, we use Corollary 2 to show that the fidelities $`F_A^i`$ and $`F_B^i`$ cannot decrease too fast.

###### Lemma 14

Assume that a $`k`$-round protocol has the bias at most $`ϵ`$. Then, for any $`i<k`$, $`F_A^i14ϵ^{1/4^{ki1}}`$ and $`F_B^i14ϵ^{1/4^{ki1}}`$.

Proof: By induction on $`ki`$.

Base case. $`i=k1`$.

First, remember that $`F_A^k=F_B^k=0`$. Let $`X\{A,B\}`$ be the person who sends the message in the $`k^{\mathrm{th}}`$ round and $`Y`$ be the person who receives the message. Sending away a part of the state can only increase the fidelity. Therefore, $`F_X^{k1}F_X^k=0`$, i.e. $`F_X^{k1}=0`$.

By Corollary 2, $`F_Y^{k1}2ϵ+6\sqrt[4]{F_X^{k1}}=2ϵ<14ϵ`$.

Inductive case.

We assume that the lemma is true for $`i`$ and show that it is also true for $`i1`$. Similarly to the previous case, let $`X`$ be the person who sends the message in the $`i^{\mathrm{th}}`$ round and $`Y`$ be the other person. Then,

$$F_X^{i1}F_X^i14ϵ^{1/4^{ki1}}.$$

By Corollary 2,

$$F_Y^{i1}2ϵ+6\sqrt[4]{14ϵ^{1/4^{ki1}}}(2+6\sqrt[4]{14})ϵ^{1/4^{ki}}<14ϵ^{1/4^{ki}}.$$

In particular, Lemma 14 implies that $`F_A^014ϵ^{1/4^{k1}}`$. We also have $`F_A^0\frac{1}{16}`$ (Lemma 12 and the first paragraph after its proof). Therefore, $`14ϵ^{1/4^{k1}}\frac{1}{16}`$. Taking log of both sides twice gives $`k=\mathrm{\Omega }(\mathrm{log}\mathrm{log}\frac{1}{ϵ})`$.

## 7 Conclusion

We have constructed a protocol for quantum coin flipping with bias 0.25 and shown that it is optimal for a restricted class of protocols. We also gave a general lower bound on the number of rounds needed to achieve a bias $`ϵ`$. A stronger lower bound has been later shown by Kitaev  but our bound also applies to weak coin flipping. The table below summarizes the known results for both strong and weak coin flipping.

|  | Best protocol | Best lower bound |
| --- | --- | --- |
| Strong | 0.25 (this paper) | $`\frac{1}{\sqrt{2}}\frac{1}{2}=0.21\mathrm{}`$  |
| Weak | $`\frac{1}{\sqrt{2}}\frac{1}{2}=0.21\mathrm{}`$  | $`ϵ>0`$, $`\mathrm{\Omega }(\mathrm{log}\mathrm{log}\frac{1}{ϵ})`$ rounds required |
|  |  | (this paper) |

The bounds for strong coin flipping are quite close but weak coin flipping is still wide open.

Another interesting question about coin flipping protocols is “cheat-sensitivity” studied by . A protocol is for coin flipping or other cryptographic tasks is cheat-sensitive if a dishonest party cannot increase the probability of one outcome without being detected with some probability. Many quantum protocols display some cheat-sensitivity but it remains to be seen what degree of cheat-sensitivity can be achieved.

## 8 Acknowledgments

Thanks to Dorit Aharonov, Daniel Gottesman, Alexei Kitaev, Boaz Leslau, Hoi-Kwong Lo, Rashindra Manniesing, Moni Naor, Ashwin Nayak, Louis Salvail, Yaoyun Shi, Rob Spekkens, Amnon Ta-Shma, Umesh Vazirani and Xinlan Zhou for useful comments, discussions and information about related work.