Three myths about quantum computing — Part 2: No-cloning theorem

This is the second post in the series on myths about quantum computing.

One of the first things we learn about quantum information is that it cannot be copied. This may seem rather surprising and counter-intuitive, since classical information stored on your computer can be easily copied (in fact, it is extremely challenging to come up with methods that would prevent this). One might even conclude that there must be something special about quantum information that does not allow us to copy it.

My goal in this post is to argue that this is not the case. The main point is that classical probability distributions cannot be copied either. This observation should make the quantum no-cloning theorem seem less surprising.

Quantum no-cloning theorem

Let us consider the standard argument why quantum states cannot be copied—the main idea is that unitary transformations have to preserve inner products.

Theorem 1 (Quantum no-cloning theorem). Transformation that acts as

|0\rangle \otimes |\psi\rangle \mapsto    |\psi\rangle \otimes |\psi\rangle

for any quantum state |\psi\rangle, is not unitary.

Proof. Let |\psi_1\rangle and |\psi_2\rangle be two quantum states, and assume that U is a unitary operation that implements the desired transformation. Then

U \bigl( |0\rangle \otimes |\psi_1\rangle \bigr) =    |\psi_1\rangle \otimes |\psi_1\rangle

U \bigl( |0\rangle \otimes |\psi_2\rangle \bigr) =    |\psi_2\rangle \otimes |\psi_2\rangle

If we take the inner product of the corresponding sides of these two equations, we get

\langle\psi_1|\psi_2\rangle =    \langle\psi_1|\psi_2\rangle^2

where we used the assumption that U is unitary. When we solve this, we get that either \langle\psi_1|\psi_2\rangle = 0 or \langle\psi_1|\psi_2\rangle = 1. This means that using a unitary transformation we can only copy states from an orthonormal set. However, the set of all quantum states is not orthonormal, so there is no unitary transformation that would copy an arbitrary unknown quantum state. \blacksquare

Classical no-cloning theorem

Recall from the previous post that quantum states and classical probability distributions are not that much different. Let us see if we can come up with a no-cloning argument that would also work in the classical case.

First, observe that independent probability distributions are combined in exact same way as quantum states—using the Kronecker product. (There is nothing “quantum” about the \otimes operation!) In probabilistic classical computing the set of allowed transformations are those that map probability distributions to probability distributions. Such transformations are called stochastic. In general, they do not preserve inner products, so our previous argument will not go through.

Let us consider an alternative argument, based on linearity. For simplicity, let us consider only probability distributions over {0,1}.

Theorem 2 (Classical no-cloning theorem). Transformation that acts as

\begin{pmatrix} 1 \\ 0 \end{pmatrix} \otimes \pi \mapsto    \pi \otimes \pi

for any probability distribution \pi, is not stochastic.

Proof. Let

\pi = \begin{pmatrix} p \\ q \end{pmatrix}

be an arbitrary probability distribution over {0,1}. We would like to have a stochastic operation that implements the transformation

\begin{pmatrix} p \\ q \\ 0 \\ 0 \end{pmatrix} \mapsto    \begin{pmatrix} p^2 \\ pq \\ qp \\ q^2 \end{pmatrix}

for any p and q. However, this is not possible, since the above transformation is clearly not linear. \blacksquare

Note that the only property we needed in this proof was linearity, so one can use exactly the same argument also for the quantum case.