Quantum Coin Flipping Protocol

Question

$\newcommand{\ket}[1]{\left|#1\right>} $I have the next protocol:

1. $A$ tosses a fair coin $a\in \{0,1\}$, if $a=0$, $A$ sends to $B$ $\ket{\psi_0}=\ket0$, if $a=1$ $A$ sends to $B$, $\ket{\psi_1}=\ket{+}$.

2. $B$ now picks randomly $b\in \{0,1\}$.

3. $A$ sends to $B$, the value of $a$.

After step 1., $B$ measures the state he gets in the basis $\{\psi_a, \psi^{\perp}_a\}$, if he doesn't get $\psi_a$ he wins, otherwise the score is $a\oplus b$, i.e if it's $0$ then $B$ wins, if it's $1$ then $A$ wins.

The question is to find the best strategy for $B$ to win if he's dishonest and $A$ is honest, and it's probability, and when B is honest and $A$ is dishonest to show that there exist a constant positive prob for which $B$ can win the game.

My attempt at solution is as follows:

For the first question: a. Well, as far as I can see $B$ can only cheat on choosing between b=0 or 1, but still he's left with 50/50 chance of winning, I don't see better strategy.

b. Here when $A$ cheats and $B$ is honest, if $A$ picks $a = 0 \ or \ 1$, and $\psi$ he sends is different than $\phi_a$, then by the criterion of the game $B$ wins. In case $A$ doesn't cheat $B$ has 0.5 chance of winning the game. So the probability should be (prob. A is dishonest)(prob B to win)+(prob A is honest)(prob B to win)= 0.5*1+0.5*0.5=0.75.

But then again, I might be wrong here. :-(

Answer 1

Cheating Bob

$\newcommand{\ket}[1]{\left|#1\right>} $A cheating Bob can always win. He just needs to pretend to have obtained $\ket{\psi_a^\perp}$ from his measurement.

Cheating Alice

By definition, if Alice cheats, she is not restricted to send one of the $\ket{\psi_a}$ states. I suspect that her optimal attack involves preparing an entangled state, sending half of it to Bob and make a measurement depending on $b$. The chosen $a$ will depend on the output value of $b$.

Let's look at a (maybe suboptimal) way for Alice to cheat.

1. Alice sends the state $\ket\phi=\frac{\ket0+\ket+}{\sqrt{2+\sqrt2}}=\frac{(1+\sqrt2)\ket0+\ket1}{\sqrt{4+2\sqrt2}}$
2. When Bob reveals $b$, Alice choses $a=b\oplus1$, to ensure $a\oplus b=1$
3. Alice sends $a$ to Bob. Let's suppose $a=0$ (the situation is obviously symmetric when $a=1$.). Bob's measurement is then $\{\ket0, \ket1\}$.
   • He gets $\ket1$ with probability $\frac1{4+2\sqrt2}=14.64\%$. Bob wins in this case.
   • He gets $\ket0$ with probability $1-\frac1{4+2\sqrt2}=85.36\%$. Since $a\otimes b=1$, Alice always wins in this case.

A much better trivial classical protocol

As shown above, Bob's cheating probability is 100% and Alice's is at least 85\%. The following fully classical protocol is better: 1. Alice randomly choses $a$ and tells it to Bob 2. Bob randomly choses $b$ ant tells it to Alice. The winner is given by $a\oplus b$. Alice cheating probability is now 50% instead of 85%, while Bob's cheating probability is no worse than in the preceding, where it was already 100% ! This protocol is therefore better than yours, even if not very useful...

Literature on Weak Coin Flipping

The protocol you describe is called weak coin flipping. Mochon has given a protocol with arbitrary small bias in arxiv:0711.4114 (Warning: hard to understand paper), involving several rounds of communication between Alice and Bob. An easier to understand protocol was proposed by Spekkens and Rudolph in arXiv:quant-ph/0202118, with a cheating probability of at most $1/\sqrt2$.