Take the 2-minute tour ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.

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

share|improve this question
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
add comment

1 Answer

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

share|improve this answer
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
show 6 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.