Quantum Information

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.

Quantum Computing Measurement Postulate

Quantum computation and information is based on the postulates of Quantum Mechanics. They are:

  1. State: Each state is represented by a unit vector in a Hilbert space.
  2. Evolutions: The state evolves only by unitary matrices.
  3. Measurement Postulate: Quantum measurements are described by a collection {\{M_m\}} of measurement operators. These are operators acting on the state space of the system being measured.The measurement operators satisfy the completeness eqaution, i.e.,

    \displaystyle \sum_m M_m^\dagger M_m=I.

    The index {m} in {\{M_m\}} refers to the measurement outcome that may occur in the experiment. If {|\psi \rangle} is the state then the probability of outcome {m} is given by

    \displaystyle p(m)=\langle \psi|M_m^\dagger M_m|\psi\rangle.

    The state of after the measurement is given by

    \displaystyle \frac{M_m|\psi\rangle}{\sqrt{\langle \psi|M_m^\dagger M_m|\psi\rangle}}.

Let us take an example here. Let {|\psi \rangle} represent the following picture.

Handwritten 'S'

Now, we want to perfrom an experiment to determine what the picture represents. So, first we need to decide what measurement operators (i.e. to decide what type of output we want) to use. If we think that {|\psi \rangle} is a digit then we might want to use the measurement operators say, {\{N_n\}}, that gives an output from the following set: \{0, 1, 2, 3, … ,9\}. If we think that {|\psi \rangle} is an English alphabet then we use measurement operators say, {\{L_l\}}, that gives an output from the following set:\{a, b, c,…,z\}. The thing to note here is that we can two different set of operators to measure a quantum state, and based on the operators used the results might be different. If we use the former set of operators we are most likely to get the result {\mathbf{5}}. Instead, if we used the set of operators which produces the result in the alphabet we are most likely to the output {\mathbf{S}}. Until now everything looks good, we wanted to find out what the image represented and we can do it using the set of operators described above. This is exactly what an Optical Character Recognition (OCR) system would have done then what’s the difference?

Well, from here onwards the quantum system would behave differently, in the classical system the picture would remain the same but if the picture were really described by a quantum state, {|\psi\rangle}, it will change to some other state {|\phi\rangle}, say. Consider the set of operators {\{N_n\}}. If we think of 0, 1, .., 9 to be orthogonal vectors, then the operators can be the projectors on the respective spaces. In this case if we performed a measurement using {\{N_n\}} and the output was {\mathbf{5}} then resulting vector {|\phi\rangle} will lie in the subspace of {\mathbf{5}}.

The Kiss Notation

I am attending a course in Quantum Information Processing. As with Quantum Mechanics, Quantum Information Processing uses the Dirac’s notation (Defined Below).

Dirac’s Noation:

  1. |\psi\rangle represents a column vector – is called ‘ket psi’.
  2. \langle\psi| represents the conjugate transpose of |\psi\rangle – is called ‘bra psi’.

In quantum computation one often comes across the following notation


Instead of pronouncing the above notation as ‘bra psi ket phi'(which is rather lenghty to pronouce) – we would say it as ‘psi kiss phi’.

The speciality of the kiss notation is that if you take a dagger of the kiss notation, i.e. (|\psi\rangle\langle\phi|)^\dagger, it still remains kiss, with the psi and phi chaging there position. (Re-enforcing our idea of that fact that love cannot be killed :-D)

(|\psi\rangle\langle\phi|)^\dagger = |\phi\rangle\langle\psi|

The new LATEX commands for the above formulation are:

  1. \newcommand*{\kiss}[2]{|#1 \rangle\langle #2|}
  2. \newcommand*{\kisso[1]{|#1 \rangle\langle #1|}

The above commands can be updated in the LATEX Preamble of LYX or can be written in the begining of the TEX document and can be used in the document.

Usage of the above commands are as follows:

  1. \kiss{i}{u} will have the following ouput – |i\rangle\langle u|
  2. \kisso{i} will have the following output – |i\rangle\langle i|