## Sunday, 8 September 2013

### The No-Cloning Theorem

A "no-go" theorem in the theory of quantum computation and quantum information will be presented here that shows the impossibility of a certain quantum operation exemplifying an essential feature of quantum mechanics. We will analyze here what it takes to be able to create a copy of an  arbitrary, unknown quantum state, or qubit to be more specific. What is actually meant by this statement will become clear as we develop this discussion. However, it is suggested to take a quick glance at the theorem statement written in bold below to get some motivation for the idea. Eventually a proof will be given, and it will be claimed that quantum states can be cloned only under certain circumstances (when the states under consideration are pair-wise orthogonal). For now, it helps to think of this task in a classical perspective.

In this case, the objective is as follows. Suppose we are given one (classical) bit $x$ in one of two definite states, which we will label as $0$ or $1$, together with an auxiliary bit initially prepared to be in the state $0$. It will  be justified later that this choice of using an auxiliary bit prepared as $0$, instead of $1$, is just a mathematical convention. Think of this second auxiliary bit as just being some blank slate which we are trying to turn into a copy of the bit $x$. Let us label this joint system of two bits as an ordered pair $(x,0)$. What we are essentially looking for is some classical operation which takes the state $(x,0)$ to the state $(x,x)$. It is important to note that we do not necessarily need to know the actual state of $x$ (the bit we are trying to make a copy of). What we do know for sure is that it is either in the state $0$ or $1$. Whatever operation actually performs this copying procedure should be independent of the actual state of $x$. In practice, frequent use is made of this notion of creating copies of a classical bit.

The ability of classical computers to accomplish such a copying task is naturally seen by making use of the controlled$-NOT$, or controlled$-X$ operation denoted by $CNOT$. This logic gate is a binary operation acting on two bits, one of which we will refer to as the control bit and the other as the target bit. The action of the $CNOT$ gate is to change the target bit to the opposite state it is initially in only if the control bit is in the state $1$. That is, if the control bit is in the state $0$, performing the $CNOT$ operation on the two bits leaves the target bit unchanged, and flips the target bit to the opposite value if the control bit is initially in the state $1$ (the states $0$ and $1$ are considered opposite values with respect to one another). A more explicit representation of this operation can be given by introducing another binary operation $\oplus$ defined as being addition modulus 2. Then the action of the $CNOT$ gate on two bits $(x,y)$ yields the state $(x,x\oplus y)$. To see that this operation actually amounts to the creation of a copy of the bit $x$, let's see what happens in the two cases where $x$ is in either of the states $0$ or $1$, and the target bit $y$ is initially prepared to be in the state $0$ as above.

First, if $x$ is in the state $0$, then applying the $c-X$ gate to $(x,0)=(0,0)$ gives $(0,0\oplus0)=(0,0)=(x,x)$. Instead, if $x$ is in the state $1$, then acting on the two bits $(x,0)=(1,0)$ with the $CNOT$ gate yields the state $(1,1\oplus0)=(1,1)=(x,x)$. Thus, in both instances we end up with the state $(x,x)$ having successfully managed to create a copy of the original bit $x$. The choice we made in  setting the initial state of our auxiliary bit in the state $0$ can be done without loss of generality. We could have just as well chosen to prepare the initial state of the auxiliary bit in the state $1$ instead. Doing so would just amount to making a slight change in how we defined the $CNOT$ operation. Instead of having the  state $(x,y)$ transformed to the state $(x,x\oplus y)$  under the $CNOT$ operation we would use a modified definition of the $CNOT$ operation which takes the state $(x,y)$ to the state $(x, x\oplus\neg y)$, where $\neg y$ represents the standard not operation taking $0$ to $1$ and $1$ to $0$.

Keeping this exposition in mind, we now consider the possibility of copying the analog of a classical bit, the qubit, in the context of quantum mechanics. By letting $\left|0\right>$ and $\left|1\right>$ denote a pair of orthonormal basis vectors of $\mathcal{H}^2$ an arbitrary state can be expressed as the linear combination $\left|\psi\right>=\alpha\left|0\right>+ \beta\left|1\right>$, with $\alpha, \beta\in \mathbb{C}$ being subject to the normalization condition $\left|\alpha\right|^2+\left|\beta\right|^2=1$. We are then trying to see if there exists some quantum mechanical procedure which allows us to make a copy of a qubit in an arbitrary, unknown pure state $\left|\psi\right>$. If this qubit is written as $\left|\psi\right>=\alpha\left|0\right>+\beta\left|1\right>$, then the assumption that $\left|\psi\right>$ is in an "unknown" state implies that we may not actually know what the values of the complex numbers $\alpha$ and $\beta$ are with absolute certainty.  Recall that no finite amount of measurements which could be performed on an ensemble of  states of this form can completely determine the exact values of $\alpha$ and $\beta$!

Given some qubit $\left|\psi\right>$ which we are trying to copy, together with another auxiliary qubit $\left|s\right>$, we question the existence of some quantum mechanical procedure which transforms $\left|s\right>$  into the same state as $\left|\psi\right>$. To make this more precise within the formalism it suffices to consider some unitary operator acting on a state in the tensor-product space of our two bits $\mathcal{H}=\mathcal{H}^2\otimes\mathcal{H}^2$ sending it to some other state in $\mathcal{H}$. Here, $\mathcal{H}$ is a Hilbert space of dimension four representing the joint system of our two qubits. Denote by $\left|\psi\right>\otimes\left|s\right>$ the state of this two qubit system in $\mathcal{H}$. As mentioned, this unitary constraint on the possible transformations which might allow us to create a copy of the state $\left|\psi\right>$ is the least we need to assume in order to be consistent with the theory. Now, we are finally in position to give a formal statement of the no-cloning theorem.

## The no-cloning theorem:

There exists no unitary transformation $U$ which is capable of creating a copy of an arbitrary, pure state $\left|\psi\right>\in\mathcal{H}^2$ such that $U(\left|\psi\right>\otimes\left|s\right>)=\left|\psi\right>\otimes\left|\psi\right>$ for all $\left|\psi\right>\in\mathcal{H}^2$ and some $\left|s\right>\in\mathcal{H}^2$.

This may seem like a surprising result. After all, we just showed that creating  copies of classical bits is easily done using the $CNOT$ operation. The fact that this is possible, at least in this classical sense, may seem to be in apparent contradiction with the statement of the no-cloning theorem. The classical theory of computation ought to be regarded as a special case of the more general quantum theory of computation. Therefore, we should at least hope our ability to make copies of classical bits remains consistent with the no-cloning theorem. There is an important subtlety in the way this theorem was stated. Note that the theorem is referring to cloning an "arbitrary" qubit $\left|\psi\right>\in\mathcal{H}^2$. Moreover, the unitary operator $U$ governing the evolution of the system's state during the supposed cloning process is a single, unique operator which should have the capability of cloning any qubit state we could possibly choose in $\mathcal{H}^2$. It is precisely this condition which leads us to the impossibility of a cloning procedure that works in such generality. There is more to it though. Perhaps the existence of such a unitary operator is asking for too much. By modifying some of these assumptions it is possible to create clones of special classes of qubits. Before we continue to discuss the strict conditions under which this is possible, as promised, a rigorous proof of the theorem is now given.

Let $\left|\psi\right>, \left|\varphi\right>, \left|s\right>\in\mathcal{H}^2$.  Suppose $U$ is a unitary operator defined on a Hilbert space $\mathcal{H}=\mathcal{H}^2\otimes\mathcal{H}^2$ of dimension four such that the following holds:
$U(\left|\psi\right>\otimes\left|s\right>)=\left|\psi\right>\otimes\left|\psi\right>,$
$U(\left|\varphi\right>\otimes\left|s\right>)=\left|\varphi\right>\otimes\left|\varphi\right>.$
Then taking the inner product of these two expressions and using the unitary assumption $U^{\dagger}U=I$, where $U^{\dagger}$ denotes the conjugate-transpose of $U$ and $I$ is the $4\times4$ identity matrix, yields
$\begin{array}{rcl} (\left<\varphi\right|\otimes\left<s\right|)U^{\dagger}U(\left|\psi\right>\otimes\left|s\right> & = & (\left<\varphi\right|\otimes\left<\varphi\right|)\otimes(\left|\psi\right>\otimes\left|\psi\right>) \\ \left<\varphi|\psi\right>\left<s|s\right> & = & \left<\varphi|\psi\right>\left<\varphi|\psi\right> \\ \left<\varphi|\psi\right> & = & (\left<\varphi|\psi\right>)^2. \end{array}$
The third equality follows from $\left<s|s\right>=1$, since $\left|s\right>\in\mathcal{H}^2$ satisfies the normalization condition. The last line here is just an equation of the form $c=c^2$, where $c$ is some real number representing the value of the inner product between the states $\left|\psi\right>$ and $\left|\varphi\right>$. This has two solutions: either $c=1$ or $c=0$. In the first case, when $c=\left<\varphi|\psi\right>=1$, $\left|\psi\right>$ and $\left|\varphi\right>$ are actually identical states. The interesting case is when $c=\left<\varphi|\psi\right>=0$. This implies that $\left|\psi\right>$ and $\left|\varphi\right>$ are orthogonal states in $\mathcal{H}^2$! Thus, since both $\left|\psi\right>$ and $\left|\varphi\right>$ were originally taken to be arbitrary states this shows that $U$ can function as a general cloning operator only if mutually orthogonal states $\left|\psi\right>$ and $\left|\varphi\right>$ are to be cloned.

Having seen the proof of the theorem, cloning bits in the classical case can now be reconciled with its quantum analog.  Remember that the computational basis states $\left|0\right>$ and $\left|1\right>$ introduced earlier served as a complete set of orthonormal basis of $\mathcal{H}^2$. Then as a consequence of the theorem this implies that the only qubit states that can be cloned in $\mathcal{H}^2$ are $\left|0\right>$ and $\left|1\right>$, which correspond to the classical bits $0$ and $1$. So, if $\left|\psi\right>=\alpha\left|0\right>+\beta\left|1\right>$ and both $\alpha$ and $\beta$ are non-zero, then there exists no unitary transformation $U$ with the ability to clone all states of this form. However, if either $\alpha$ or $\beta$ is zero, then the normalization condition implies that the non-zero coefficient must be one. Hence, the qubit is no longer in a superposition of basis states and simply takes the form $\left|\psi\right>=\left|0\right>$ or $\left|\psi\right>=\left|1\right>$. This is when the quantum states conform to their classical counterparts.

It is worthwhile to consider an alternate, more constructive proof of the theorem which mirrors the classical case.  As shown, the classical $CNOT$ gate allowed us to create clones of ordinary bits. When a qubit is in one of the computational basis states the quantum analog of the $CNOT$ gate can be used to create a copy of the qubit. Let us denote this quantum $CNOT$ gate by $U_{CN}$. This operator acts similarly to the classical $CNOT$ gate where the target qubit is flipped to its opposite value only when the control qubit is in the state $\left|0\right>$. A matrix representation for $U_{CN}$ in this two qubit case is given by
$U_{CN}= \begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}.$
It can easily be checked that $U_{CN}$, which is its own conjugate-transpose, is a unitary transformation:
$U_{CN}^{\dagger}U_{CN}=\begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} = \begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}= I.$
To make sense of this, using the notation $\left|\psi\right>\left|\varphi\right>=\left|\psi\right>\otimes\left|\varphi\right>$, associate to the space $\mathcal{H}$ the four computational basis states
$\left|0\right>\left|0\right> =\begin{pmatrix}1 \\ 0 \\ 0 \\ 0 \end{pmatrix}, \left|0\right>\left|1\right> = \begin{pmatrix}0 \\ 1 \\0 \\ 0 \end{pmatrix}, \left|1\right>\left|0\right> = \begin{pmatrix}0 \\ 0 \\ 1 \\ 0 \end{pmatrix}, \left|1\right>\left|1\right> = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}.$
Choose any state $\left|\psi\right>\in\mathcal{H}^2$ and let
$\left|\psi\right>=\alpha\left|0\right>+\beta\left|1\right>=\begin{pmatrix}\alpha \\ \beta \end{pmatrix}.$
Set the auxiliary qubit in the basis state
$\left|s\right>=\left|0\right>=\begin{pmatrix}1 \\ 0 \end{pmatrix}.$
Then using $U_{CN}$ on the state of two qubits
$\left|\psi\right>\left|0\right>=\begin{pmatrix}\alpha \\ 0 \\ \beta \\ 0 \end{pmatrix}$
gives
$U_{CN}((\alpha\left|0\right>+ \beta\left|1\right>)\left|0\right>)=\begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix}\alpha \\ 0 \\ \beta \\ 0 \end{pmatrix}=\begin{pmatrix}\alpha \\ 0 \\ 0 \\ \beta \end{pmatrix}=\alpha\left|0\right>\left|0\right>+\beta\left|1\right>\left|1\right>.$
Whereas the cloned state we are trying to achieve is of the form
$\left|\psi\right>\left|\psi\right>=\begin{pmatrix}\alpha^2 \ \alpha\beta \ \alpha\beta \ \beta^2 \end{pmatrix}=\alpha^2\left|0\right>\left|0\right>+\alpha\beta\left|0\right>\left|1\right>+\alpha\beta\left|1\right>\left|0\right>+\beta^2\left|1\right>\left|1\right>.$
We would like to get something of the form $U_{CN}(\left|\psi\right>\left|0\right>)=\left|\psi\right>\left|\psi\right>$. Equating these two states implies $\alpha\beta=0$ so that at least one of $\alpha$ or $\beta$ is $0$ since we're dealing with the field of complex numbers. But the normalization condition implies one of $\alpha$ or $\beta$ is $1$. Hence, $\left|\psi\right>$ must be one of the basis states $\left|0\right>$ or $\left|1\right>$ in order to clone $\left|\psi\right>$ using $U_{CN}$.

These results are ultimately a consequence of the linearity of quantum mechanics. What has been shown here was really in the special context of qubits, which are not the most general quantum systems. A qubit is naturally associated to a two dimensional Hilbert space with the normalization condition on the states being implicit. The universal property expressed in the no-cloning theorem holds just as well for normalized states in Hilbert spaces of arbitrary dimension, and the limiting result that only orthogonal states can be cloned in these spaces also remains true. Despite other possibilities of being able to clone quantum states, the end result is that non-orthogonal quantum states  cannot be cloned in general unless one is willing to tolerate a finite loss of "fidelity"---that is, imperfect copies of states.

Interestingly enough, at least from what I am aware of,  the first proof of the no-cloning theorem appeared in the literature in 1982 by Wootters and Zurek. This is rather surprising given that the theory of computation and quantum mechanics had  been sufficiently developed by the end of the 1930s to prove a no-cloning result like this. Might it be that no one cared to ask the question? Whether or not such a result was known prior to 1982, it seems that it's implications may have been taken for granted. This property of quantum mechanics is at the root of the differences between the quantum and classical worlds,  and is closely related to other fundamental quantum mechanical principles.

In essence, the inability to clone general quantum states  has something to do with the inability to distinguish non-orthogonal states in a given space, which in turn has something to do with the amount of information accessible in these states. Furthermore, it can even be said that states in a superposition contain "hidden" information that is not accessible from a finite amount of measurements alone. The certain quantum mechanical essence  contained in these last remarks can be exemplified through an informal, alternate proof of the no-cloning theorem. This is done through a consistency argument using the uncertainty principle.  Suppose arbitrary quantum states could be cloned. Then by creating  multiple copies of a given state, and using a pair of non-commuting observables, one would have the ability of performing measurements on these copies in such a way that the values of these observables could simultaneously be known to any degree of precision. This contradicts the lower bound implied by the uncertainty principle.