# Quantum Coin Flipping Protocol

$$\newcommand{\ket}{\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

$$\newcommand{\ket}{\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$$.

• 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