Introduction to quantum computing with Q# – Part 6, No-cloning theorem

In the last part of this series we looked at the phenomenon of entanglement – one of the core concepts of quantum theory, which has been fundamentally important in the development of quantum information theory. We grappled with its deeply mysterious behavior and tried to understand and project its consequences onto the Q# code.

In today’s part 6, we shall ask ourselves a seemingly innocent question – how to you clone a quantum state, or in other words, how do you copy a qubit?

Historical background

In 1981, Nick Herbert submitted a paper called FLASH — A superluminal communicator based upon a new kind of measurement to Springer’s Foundations of Physics journal. It was focused on what appeared at first to be an improbable idea – faster than light communication. This potentially earth-shattering concept was of course in violation of the special theory of relativity, but nonetheless – or specifically, because of that – still drew a lot of attention. The core theoretical prerequisite for superluminal communication that the paper proposed, was the ability to create perfect copies of quantum states, in unlimited quantities. Asher Peres, who was one of the reviewers of this submission, recalls in How the No-Cloning Theorem Got its Name that while it was obvious to him that the paper could not possibly be correct, he still recommended for it to be published:

I recommended to the editor of Foundations of Physics that this paper be published. I wrote that it was obviously wrong, but I expected that it would elicit considerable interest and that finding the error would lead to significant progress in our understanding of physics.

Peres was definitely right. In October 1982, two scientists – William Wootters from the University of Texas and Wojciech Zurek from the California Institute of Technology – wrote a relatively short (fitting on a single sheet of standard scientific two-column paper) letter to the Nature magazine. It was titled A single quantum cannot be cloned, and addressed this single, simple, yet tantalizing question. Could quantum mechanics facilitate superluminal communication?

Wootters and Zurek were quick to disperse this idea:

Is it possible (…) to amplify a quantum state, that is, to produce several copies of a quantum system (the polarized photon in the present case) each having the same state as the original? (…) We show here that the linearity of quantum mechanics forbids such replication and that this conclusion holds for all quantum systems. Note that if photons could be cloned, a plausible argument could be made for the possibility of faster-than-light communication.

The notion that any copying of unknown quantum states is precluded by the mathematical foundations of quantum mechanics itself became known as the “no-cloning theorem”. The name was actually contributed by the great John Wheeler, who at that time was working very closely with both Wootters (his graduate student) and Zurek (his post doc).

CNOT as a copying candidate?

In classical computing based on the von Neumann architecture, COPY is one of the fundamental instructions, and the ability to copy a bit from one place to another is an intrinsic property of computing circuits. Let’s recall for a moment our discussion from part 4 about the CNOT gate. Turns out, that the CNOT gate, in a classical sense, can also considered a simple single-bit copy machine. To remind ourselves, if we leave the complexities of superposition aside and focus only on the two computational basis states $\ket{0}$ and $\ket{1}$, then CNOT can be summarized as:

$$\ket{00}\rightarrow\ket{00}$$
$$\ket{01}\rightarrow\ket{01}$$
$$\ket{10}\rightarrow\ket{11}$$
$$\ket{11}\rightarrow\ket{10}$$

Just as we did earlier in part 4, it is most common to reason about CNOT by taking a view that would be focused on the control qubit. That is, we can describe CNOT in the following way – when the control qubit is $\ket{1}$, the value of the target qubit would be swapped, otherwise it would stay the same. However, we could also look at the CNOT behavor through a slightly different lense – with the target qubit, instead of the control qubit, at the center of our mental model. If we now only consider the states where the target is initialized to $\ket{0}$, we get:

$$\ket{00}\rightarrow\ket{00}$$
$$\ket{10}\rightarrow\ket{11}$$

Which we can summarize as – CNOT provides a single-bit-like copy mechanism when the target qubit is initialized to $\ket{0}$. In the case when control qubit is $\ket{0}$, it copies $\ket{0}$ onto $\ket{0}$, while when control qubit is $\ket{1}$, it copies $\ket{1}$ onto $\ket{0}$. This observation was also stated by Imre and Balazs in their excellent book Quantum Computing and Communications: An Engineering Approach:

The COPY command is a fairly common one often used by computer scientists and programmers. It is worth pointing out that the CNOT gate can be regarded as a one-bit copy machine. Provided its data input is initalized permanently with $\ket{0}$ then the CNOT gate emits a copy of the control input on each output.

Unfortunately, as we learnt in part 5, the behavior of CNOT in quantum computing is a lot more complicated than in classical computing. When the control qubit is in a linear superposition of the two basis states – $\alpha\ket{0} + \beta\ket{1}$, where both $\alpha$ and $\beta$ are non-zero – then application of the CNOT transformation would produce an entangled pair of qubits instead of a copy. For example:

$$CNOT(H\ket{0}\ket{0}) = \frac{1}{\sqrt{2}}(\ket{00} + \ket{11})
$$

Imre and Balazs comment on this superposition-driven behavior of the CNOT gate in their typical, light-hearted way:

We have already investigated the operation of the CNOT gate feeded with superposition. Although we expected to realize the COPY command we reached entanglement instead. On one hand we were delighted with this surprising outcome but on the other hand we started to have suspicions about the limits of copying in the quantum world.

At this point, it is difficult not to share the skepticism of Imre and Balazs, as we can clearly see a completely divergent paths between classical and quantum computing. How can we, however, explain the no-cloning theorem?

Proving the no-cloning theorem

The no-cloning theorem is actualy a direct consequence of the unitary nature of all quantum transformation – or as we’ve been calling them in quantum computing, quantum gates. We can rephrase the original proof of Wootters and Zurek to illustrate this. Suppose such a quantum cloning two qubit gate actually exists – we can tentatively call it $C$ (as in, “copying”). How would such a $C$ behave? Given two completely generic orthogonal quantum states $\ket{\varphi}$ and $\ket{\psi}$, and a pure state (“scratch” state onto which the copying will happen) $\ket{\rho}$ we would expect that the following happens:

$$C(\ket{\varphi}\ket{\rho}) = \ket{\varphi\varphi}$$
$$C(\ket{\psi}\ket{\rho}) = \ket{\psi\psi}$$

So taking a pair of a qubits in an orthogonal state and a pure state, we’d expect to get a pair of qubits in that orthogonal state as a result. However, since $\ket{\varphi}$ and $\ket{\psi}$ are orthogonal, there exists a state $\ket{\phi}$ that is a linear combination of both, for example:

$$\ket{\phi} = \frac{1}{\sqrt{2}}(\ket{\varphi} + \ket{\psi})$$

What follows is that linearity tells us that if we try to clone $\ket{\phi}$ using the same cloning transformation $C$, we would get:

$$C(\ket{\phi}\ket{\rho}) = \frac{1}{\sqrt{2}}(C(\ket{\varphi}\ket{\rho}) + C(\ket{\psi}\ket{\rho})) \\ = \frac{1}{\sqrt{2}}(\ket{\varphi\varphi} + \ket{\psi\psi})$$

This is not exactly the expected result. If the state $\ket{\phi}$ was really cloned, we should be seeing:

$$C(\ket{\phi}\ket{\rho}) = \ket{\phi\phi}$$

And $\ket{\phi\phi}$ can be expanded (based on the fact that $\ket{\phi} = \frac{1}{\sqrt{2}}(\ket{\varphi} + \ket{\psi})$):

$$\ket{\phi\phi} = \frac{1}{2}(\ket{\varphi\varphi} + \ket{\varphi\psi} + \ket{\psi\varphi} + \ket{\psi\psi})$$

We’ve reached a dead end here because our two expected outcomes of cloning are not equal to each other:

$$\frac{1}{\sqrt{2}}(\ket{\varphi\varphi} + \ket{\psi\psi}) \neq \\ \frac{1}{2}(\ket{\varphi\varphi} + \ket{\varphi\psi} + \ket{\psi\varphi} + \ket{\psi\psi})$$

This tells us that we cannot have a copying gate that would be able to handle any arbitrary superposition. Nielsen and Chuang provide an alternative way of looking at the problem. They start off the same way as we did, by defining their expectations as:

$$C(\ket{\varphi}\ket{\rho}) = \ket{\varphi\varphi}$$
$$C(\ket{\psi}\ket{\rho}) = \ket{\psi\psi}$$

What follows, is an interesting observation that we could take the inner product of both equations:

$$\braket{\varphi|\psi} = (\braket{\varphi|\psi})^2$$

We know that such an equation could only have solutions when the inner product is equal to $1$ (the vectors are equal) or to $0$ (the vectors are orthogonal). So this means that cloning is only possible when either $\ket{\varphi} = \ket{\psi}$ or $\ket{\varphi}$ and $\ket{\psi}$ are orthogonal to each other. Nielsen and Chuang summarize:

Thus a cloning device can only clone states which are orthogonal
to one another, and therefore a general quantum cloning device is impossible. A
potential quantum cloner cannot, for example, clone the qubit states $\ket{\varphi} = \ket{0}$ and $\ket{\psi} = \frac{1}{\sqrt{2}}\ket{0} + \ket{1}$ since these states are not orthogonal.

This perfectly agrees with our initial findings regarding the CNOT gate. It can be considered to be a copying gate – but only for the two computational basis states $\ket{0}$ and $\ket{1}$. In fact, the above conclusion was also drawn by Wootters and Zurek in their original proof in Nature, back in 1982.

As in the case of photons, linearity does not forbid the amplification of any given state by a device designed especially for that state, but it does rule out the existence of a device capable of amplifying an arbitrary state.

All things considered, the proof for the no-cloning theorem is relatively simple – although that is often the case after such proofs are discovered, the real challenge is to come up with it in the first place. In Elegance and Enigma, Zurek shares an incredible story related to the proof of the no-cloning theorem. Next time you grapple with a difficult problem yourself, or get lost in the mathematics of quantum theory, take solace in the fact that Richard Feynman, one of the most acclaimed theoretical physicists of the 20th century, had real problems coming up with the no-cloning proof.

I wanted to try on Feynman the proof of “no cloning.” That was one of the few times when I knew I had the right answer before he did, and I wanted to tell it to him. But he insisted that I do not: he wanted to figure it out for himself. He appreciated the severity of the problem—the danger of superluminal communication—but tried other ways of dissolving it. (…) So I just watched him trying various approaches and told him when I saw a dead end coming—I had earlier visited some of these dead ends myself. When I eventually gave him the proof, he seemed convinced but also frustrated that he did not get it on his own.

Epistemological consequences

When thinking about a quantum state in a classical sense, as if it was a state of a macroscopic object, the lack of copying possibility seems severely limiting and inconsistent with our expectations of what constitutes information about reality. However, yet again, the quantum world proves to be considerably different from our everyday intuition and expectations. The question about the ability to copy such a state also takes epistemological character. Wootters and Zurek, in their Physics Today article explain it in the following way:

The fact that an unknown quantum state cannot be discovered by a measurement or revealed by cloning suggests that not only is it unknown, but it does not even exist in the usual sense.

With that in mind, we are hopefully a little more incline to accept that the no-cloning theorem could really be a logical consequence of the state of reality. While this view stretches beyond the pure factual discussion and reaches into the areas of interpretation of quantum mechanics, it is very much in-line with the “reality without realism” line of thinking adopted in this series of blog post, and reflects the spirit of Copenhagen; reality that may always be beyond our conception.

Summary

And just like that, we have reached the end of part 6 of this introduction to quantum computing with Q#. Interestingly, in this part, we have not written a single line of code – after all, there is no way to copy a qubit state in Q# too – we did lay solid theoretical foundations towards the topics that will follow next. Namely, we could ask ourselves, is the lack of copying really that big of a problem? Or could it be an advantage?

In one of the next parts we will look at quantum cryptography and security protocols that specifically take advantage of the fact that qubits cannot be copied. Specifically in the next part though, we will explore something else though – we shall see that while we cannot copy an unknown quantum state, we sure can… teleport it.