Impossibility of Quantum Bit Commitment

I learnt about the quantum bit commitment protocol today and found it very interesting and it will be the subject of this post.

The Situation: Alice and Bob (a very influential person) like to bet on the outcome of a cricket match between India and Pakistan. Alice would like to place the bet on one of the outcomes:

  1. India wins
  2. India loses

If she wins Bob has to pay her a certain amount of money. She does not want Bob to know on what outcome she has placed the bet, as being an influential person Bob can affect the result of the match in his favour. Bob wants that she should not be able to change the bet once she has placed it.

We will now see how we can achieve the above conditions in a quantum setting. We will be using an electron spin for placing the bet.

The protocol:

  1. Alice takes an electron in the state {|\psi\rangle}.
  2. She does the following:
    • If she wants to place the bet that India wins then she will measure her system with the observable {\sigma_z}.\displaystyle \sigma_{z}=\left( \begin{array}{cc} 1 & 0\\ 0 & -1 \end{array} \right);
      \displaystyle |\psi_{-z}\rangle=\left( \begin{array}{c} 0\\ 1 \end{array} \right) ,
      \displaystyle |\psi_{z}\rangle=\left( \begin{array}{c} 1\\ 0 \end{array} \right)
    • If she wants to place the bet that India loses then she will measure her system with the observable {\sigma_x}.\displaystyle \sigma_{x}=\left( \begin{array} {cc} 0 & 1 \\ 1 & 0 \end{array} \right)
      \displaystyle |\psi_{x}\rangle=\frac{1}{\sqrt{2}}\left( \begin{array}{c} 1\\ 1 \end{array} \right)
      \displaystyle |\psi_{-x}\rangle=\frac{1}{\sqrt{2}}\left( \begin{array}{c} 1\\ -1 \end{array} \right)
  3. She notes the outcome of her measurement and then gives the resultant qubit to Bob.
  4. After the match she announces the outcome of her measurement and what observable she had used to do the measurement.
  5. Bob performs the measurement with the same observable if he gets the same result as Alice then she is telling the truth.

Why it works:

  1. In the first case when Alice measures the system with {\sigma_z} the resulting state of the qubit will be {\frac{1}{2}|\psi_z\rangle \langle\psi_z| + \frac{1}{2}|\psi_{-z}\rangle \langle \psi_{-z}|}.
  2. In the case when Alice measures the system with {\sigma_x} the resulting state of the qubit will be {\frac{1}{2}|\psi_x\rangle \langle\psi_x| + \frac{1}{2}|\psi_{-x}\rangle \langle \psi_{-x}|}.We see that in both cases when Bob has not been told the result of the measurement, the qubit is in the same mixed state {\frac{I}{2}}. Bob has no way of knowing how it was prepared. We have now made sure that Bob has not way of doing any cheating.
  3. Lets see what will happen if Alice tries to cheat. If Alice tries to cheat she will have to tell that she measured with the other observable and will have to give a random outcome of the measurement. There is 50{\%} chance that Bob also gets the same output when he measures. To reduce this probability we can start with many copies of {|\psi\rangle}. Alice is suppose to measure all of them with the same observable and then send them to Bob. The rest of the protocol remains the same. By doing this we will have reduced the probability of Alice winning by cheating very very small. Any outcome which does not match to what Alice says will mean that she has cheated.

It looks like that we are done. Have we achieved a perfect bit commitment protocol? The answer is no. We have made an assumption that the only way Alice can affect the qubit is when she has it. Is it possible that she can in some way affect the qubit with a remote of some sort? Yes, it is possible by using entangled qubits.

Lets see how it is possible. Suppose Alice prepares all the qubits in the following state {\frac{1}{2}(|00\rangle + |11\rangle)}. She gives one of the qubits to Bob. Bob, now holds a qubit which for him is in the state \frac{I}{2}. But, since she will have the other entangled qubit she will be the able to change the state of the qubit with Bob by measuring her qubit.

Mutual Information and Conditional Mutual Information

Let \text{I}(X;Y) represent the mutual information between random variables X and Y.

Here I give example one for the following inequalities.

  1. \text{I}(X;Y|Z) \geq \text{I}(X;Y)
  2. \text{I}(X;Y|Z) \leq \text{I}(X;Y)

Example 1: For \text{I}(X;Y|Z) \geq \text{I}(X;Y)

Let X, Y be independent uniformly distributed random bits and Z=X \bigoplus Y. Then,

LHS = {\text{I}(X;Y|Z=0) + \text{I}(X;Y|Z=1) \over 2}

={{1 + 1} \over 2} =1

RHS = 0

Hence, \text{I}(X;Y|Z) \geq \text{I}(X;Y).

Example 2: For \text{I}(X;Y|Z) \leq \text{I}(X;Y)

Let X=Y=Z, X is a uniformly distributed random bit. Then, it can be shown that

LHS = 0

RHS= 1

3GPP Resources

Here are a collection of white papers from Ericsson on various technologies in the 3rd Generation Partnership Project. I have found these resources very userful. It gives a nice introduction to the techonology.


  1. Basic Concepts of HSPA


  1. Innovations in WCDMA
  2. WCDMA Basic Concepts


  1. The evolution of EDGE

NOTE: I will keep updating this post as I keep getting more and more resources. If you know of a good 3GPP resource (not let me know.