# Quantum Coin Flipping Protocol

$\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. :-(

-
As I understood your protocols, a dishonest B can win with probability one: he just have to pretend he obtained $|\psi_a^\perp\rangle$ from his measurement. Did I misunderstood something ? –  Frédéric Grosshans Apr 3 '12 at 9:26
By the way, this kind of protocol is called "weak coin flipping" in the literature, and I think that protocols with arbitrary small bias are known. –  Frédéric Grosshans Apr 3 '12 at 9:42
I think that you are right in this regard. BTW, with question b. am I right in my analsyis? –  MathematicalPhysicist Apr 3 '12 at 10:21
I really don't get your analysis on several points. does "$\psi$ different of $\psi_a$" means orthogonal, or just different ? I don't understand why you need a "prob. A is dishonest" ? And why do you set it to .5. And you don't consider entanglement. –  Frédéric Grosshans Apr 3 '12 at 12:23

# Cheating Bob

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$.

-
I have corrected my questions, sorry to mislead you. :-( –  MathematicalPhysicist Apr 3 '12 at 16:15
So you changed the order of cases to consider. I don't think it changes the validity of y answer. –  Frédéric Grosshans Apr 3 '12 at 16:33
But both questions ask for Bob's optimal strategy and not for Alice's! –  MathematicalPhysicist Apr 3 '12 at 17:30
In the usual terminology : Honest Bob = Bob follows the protocol. He doesn't have anything to optimize on, since his strategy is fixed by the protocol. And Cheating Alice = Alice can do anything. The protocol doesn't define her strategy. Finding a bound on Bob's result means therefore optimizing on Alice's strategies. –  Frédéric Grosshans Apr 4 '12 at 16:28
I think the BB84 protocol is the protocol that A can follow in order to maximize her chances to win the game. –  MathematicalPhysicist Apr 6 '12 at 5:51