Three myths about quantum computing

In this series of posts I will discuss some misconceptions about quantum computing.

One often hears people saying that quantum physics is “strange” and that our classical intuition “breaks down” in the quantum world. I will try to argue that one should not brag about the weirdness of quantum mechanics without carefully investigating the corresponding phenomena in the classical world. In fact, many quantum phenomena no longer seem surprising once their lesser cousins in the classical probabilistic world are understood.

To illustrate my point, I will consider three basic properties of quantum information

  1. exponential state space
  2. no-cloning theorem
  3. quantum teleportation and superdense coding

and discuss how they translate to the classical case.

These topics are usually covered in the first class of an introductory quantum computing course, so none of what I discuss should come as a surprise to somebody who has taken such a course or read an introductory textbook on the topic. However, I have to admit that I was equally shocked both, when I learned these basic facts about quantum information in class, as when I later realized that they have a corresponding classical counterpart.

I would like to acknowledge all my “non-quantum” friends with whom I have had conversations about quantum physics. I would probably still believe in these misconceptions if I had not tried to explain you in simple terms why quantum physics is supposed to be so strange. Maybe it is not so strange after all…

p.s. For those of you who have never attempted to explain what you are doing to somebody who does not have a PhD degree in your area of expertise, consider the following three quotes by the founders of quantum mechanics:

Most of the fundamental ideas of science are essentially simple, and may, as a rule, be expressed in a language comprehensible to everyone.
—Albert Einstein

The physicist may be satisfied when he has the mathematical scheme and knows how to use it for the interpretation of the experiments. But he has to speak about his results also to non-physicists who will not be satisfied unless some explanation is given in plain language. Even for the physicist, the description in plain language will be the criterion of the degree of understanding that has been reached.
—Werner Heisenberg

If you cannot—in the long run—tell everyone what you have been doing, your doing has been worthless.
—Erwin Schrödinger

Unitary equivalence of purifications


Let \rho be a mixed quantum state on system \mathcal{A}. We say that a pure quantum state |\psi\rangle on a composite system \mathcal{A} \otimes \mathcal{B} is a purification of \rho if

\rho = \mathrm{Tr}_B (|\psi\rangle \langle\psi|)

The following theorem is a basic result in quantum information theory.

Theorem 1 (unitary equivalence of purifications). If |\psi\rangle and |\phi\rangle are two purifications of \rho then

|\phi\rangle = (I_A \otimes U) |\psi\rangle

for some unitary U that acts only on system \mathcal{B}.

Schmidt decomposition

The above result is usually proved using the following theorem.

Theorem 2 (Schmidt decomposition). Any bipartite quantum state |\psi\rangle on \mathcal{A} \otimes \mathcal{B} can be written as

|\psi\rangle = \sum_i \sqrt{p_i} |\alpha_i\rangle |\beta_i\rangle

for some orthonormal bases \{|\alpha_i\rangle\} and \{|\beta_i\rangle\} on systems A and B, respectively, and a probability distribution \{p_i\}.

However, standard proofs of Theorem 1 are often based on the following (wrong) argument: given two spectral decompositions of the same matrix, the corresponding eigenvalues and eigenvectors in both decompositions must be equal. This is true only if the given matrix has a non-degenerate spectrum. Otherwise the eigenvectors corresponding to a repeated eigenvalue are not uniquely determined (any orthonormal basis of the corresponding subspace is a valid set of eigenvectors).

A simple proof of Theorem 1

Here is an elementary proof of Theorem 1 which does not run into problems in case of a degenerate spectrum. By Theorem 2 we can write the first state as

|\psi\rangle = \sum_i \sqrt{p_i} |\alpha_i\rangle |\beta_i\rangle

Let us expand the first register of the second state |\phi\rangle in the basis \{|\alpha_i\rangle\}:

|\phi\rangle = \sum_i |\alpha_i\rangle |\tilde{\gamma}_i\rangle

where \{|\tilde{\gamma}_i\rangle\} are some arbitrary (non-normalized) vectors. Then we have

\mathrm{Tr}_B (|\psi\rangle \langle\psi|)    = \sum_{i,j} \sqrt{p_i p_j}      |\alpha_i\rangle \langle\alpha_j|      \mathrm{Tr} (|\beta_i\rangle \langle\beta_j|)

= \sum_{i,j} \sqrt{p_i p_j}      |\alpha_i\rangle \langle\alpha_j|      \delta_{ij}


\mathrm{Tr}_B (|\phi\rangle \langle\phi|)    = \sum_{i,j} |\alpha_i\rangle \langle\alpha_j|      \mathrm{Tr} (|\tilde{\gamma}_i\rangle \langle\tilde{\gamma}_j|)

= \sum_{i,j}      |\alpha_i\rangle \langle\alpha_j|      \langle\tilde{\gamma}_j|\tilde{\gamma}_i\rangle

By assumption, both partial traces are equal. Since \{|\alpha_i\rangle\} is an orthonormal basis, the coefficients in both expressions must be the same:

\sqrt{p_i p_j} \delta_{ij}    = \langle\tilde{\gamma}_j|\tilde{\gamma}_i\rangle

This means that |\tilde{\gamma}_i\rangle are pairwise orthogonal and \||\tilde{\gamma}_i\rangle\| = \sqrt{p_i} (it could happen that p_i = 0 for some i, but this is not a problem). Equivalently, this equation says that we can find an orthonormal basis \{|\gamma_i\rangle\} such that |\tilde{\gamma}_i\rangle = \sqrt{p_i} |\gamma_i\rangle. Then we see that |\phi\rangle = (I \otimes U) |\psi\rangle, where U = \sum_i |\gamma_i\rangle \langle\beta_i| is the unitary change of basis from \{|\beta_i\rangle\} to \{|\gamma_i\rangle\}.

Music evening 1

There is so much beautiful music that has been composed, performed and recorded. But how do we find out about it? It is not necessarily easy to find something that you like by just randomly clicking around the web.

Luckily, everyone likes music, so a good way to discover great music is just by talking to people (besides, it is also a meaningful way for people to connect). That is how the first music evening came about…

The idea is very simple—people just come together and everyone shares one piece of music with everybody else (preferably, it should be “the most beautiful piece ever written” or at least have some special significance to the person who shares it).

The first event took place yesterday at my place. (We not only shared good music, but also had some yummy Italian-Indian-Latvian style risotto!) Here is the list of people who attended and the music that they like (I linked songs on YouTube or Grooveshark, and also added some extra links to Wikipedia or other relevant websites where you can find more information about the music):












Event was followed by a short dance party…

Maxwell’s equations

This is how the differential Maxwell’s equations look like using vector notation:

\dfrac{\partial\mathbf{B}}{\partial t} = - \nabla \times \mathbf{E}       \nabla \cdot \mathbf{B} = 0

\dfrac{\partial\mathbf{E}}{\partial t} =   \nabla \times \mathbf{B}       \nabla \cdot \mathbf{E} = 0

It turns out that these equations can be written in a more compact form:

d\mathrm{F} = 0       d{*}\mathrm{F} = 0

known as the differential geometric formulation.

The main idea to derive this alternative formulation is as follows. First, we define the electromagnetic tensor which contains the components of both \mathbf{E} and \mathbf{B}:

F =  \begin{pmatrix}  0 & E_x & E_y & E_z \\  -E_x & 0 & -B_z & B_y \\  -E_y & B_z & 0 & -B_x \\  -E_z & -B_y & B_x & 0  \end{pmatrix}

This matrix is skew-symmetric, so we can encode it as a 2-form:

\mathrm{F} = \mathrm{E}(\mathbf{E}) + \mathrm{B}(\mathbf{B})

where the 2-forms \mathrm{E}(\mathbf{E}) and \mathrm{B}(\mathbf{B}) encode the entries of vectors \mathbf{E} and \mathbf{B} in the following way:

\mathrm{E}(\mathbf{v})  = v_x \, dt \wedge dx  + v_y \, dt \wedge dy  + v_z \, dt \wedge dz

\mathrm{B}(\mathbf{v})  = v_x \, dz \wedge dy  + v_y \, dx \wedge dz  + v_z \, dy \wedge dx

Next, one defines an operation known as Hodge dual and checks that

{*}\mathrm{E}(\mathbf{v}) = \mathrm{B}(\mathbf{v})       {*}\mathrm{B}(\mathbf{v}) = -\mathrm{E}(\mathbf{v})

Finally, one has to define the exterior derivative and check that

d\mathrm{E}(\mathbf{v}) = dt \wedge \mathrm{B}(\nabla \times \mathbf{v})

d\mathrm{B}(\mathbf{v}) = dt \wedge \mathrm{B} \biggl( \dfrac{\partial \mathbf{v}}{\partial t} \biggr) - (\nabla \cdot \mathbf{v}) \, dx \wedge dy \wedge dz

Using these equations we can rewrite d\mathrm{F} = 0 and d{*}\mathrm{F} = 0 in terms of \mathbf{E} and \mathbf{B} and verify that the resulting equations are equivalent to the original Maxwell’s equations.

For more details see: Differential geometric formulation of Maxwell’s equations.