CSE 599d - Quantum Computing

The No-Cloning Theorem, Classical Teleportation and Quantum Teleportation,

Superdense Coding
Dave Bacon
Department of Computer Science & Engineering, University of Washington

I. THE NO-CLONING THEOREM

Cloning has been in the news a lot lately. But today we are not going to talk about that type of cloning, but instead
of a process of duplicating quantum information. That we are not talking about cloning DNA (for our results will
not be positive) is rather fortunate for the Raelians!
The no-cloning theorem is one of the earlier results in the study of quantum information. It has an interesting
history, some of which is written down in a paper by Asher Peres, “How the No-Cloning Theorem Got Its Name” which
is available online at [Link] and is generally attributed to Wootters, Zurek, and
Dieks in 1982. (When I was an undergraduate at Caltech, they had an automated system for requesting copies of
articles when you were searching their publication database. I discovered, probably around my junior year, the papers
of William Wootters, promptly ordered the automated system to print out every paper Wootters had ever written at
that time and my life hasn’t been the same ever since! Wootters thesis is, in my opinion, one of the most interesting
resutls I’ve ever encountered.) So what is the no-cloning theorem?
Suppose that we have in our lab a qubit in an unknown quantum state |ψi = α|0i + β|1i. Actually it is perhaps
better to say that some external referee knows a description of this quantum state, but we in the lab don’t know this
quantum state. Now we can construct all sort of machines (unitaries and measurements) which act on this qubit. The
question posed in the no-cloning theorem is whether it is possible to design a machine which, for all possible actual
states |ψi, is able to take this state |ψi and create two copies of this state |ψi ⊗ |ψi, hence “cloning” the quantum
state.
Let’s prove a simple version of the no-cloning theorem. We want to show in this version that there is no unitary
operation which can enact the evolution |ψi ⊗ |0i → |ψi ⊗ |ψi for all possible states |ψi. To see this, suppose that
there exists such a unitary. Then it must be able to clone |0i and |1i: U |0i ⊗ |0i = |0i ⊗ |0i and U |1i ⊗ |0i = |1i ⊗ |1i
Then if this is true, by the linearity of quantum theory, U √12 (|0i + |1i) ⊗ |0i = √12 (|0i ⊗ |0i + |1i ⊗ |1i) which is not
equal to √12 (|0i + |1i) ⊗ √12 (|0i + |1i) which is what we would require if this were a cloning unitary. Thus we have a
contradiction: no such unitary can exist.
We’ve shown the no-cloning theorem for qubits and for just unitary transformations. In fact there is a more general
version of this theorem, called the no-broadcasting theorem which deals with an even more general situation. Suffice
it to say, in all of these formulations a quantum machine which can perfectly clone all quantum states is shown to not
be constructible. An interesting question which we won’t talk about too much, but which has led to a lot of very nice
results is what about imperfect cloning machines?
Finally it is interesting to ask how quantum the no-cloning theorem is. What about if we return to our classical prob-
abilistic information processing device. Suppose we have a classical system of two configurations with the probability
distribution [p 1 − p]T ]. Is it possible to turn this into two copies of the probability distribution [p 1 − p]T ⊗ [p 1 − p]T
for all possible probabilities p? At first you might think: of course we can do this: we just copy the bits! But if we
take [p 1 − p]T ⊗ [1 0] and copy the first bit to the second, this produces the probability distribution [p 0 0 1 − p]T . This
is not the same as the probability distribution [p 1 − p]T ⊗ [p 1 − p]T . In fact one can see that if we allow stochastic
evolutions, then by the same argument we used in the quantum case, there is no classical machine which can clone
the probability distribution.
This latter example is one of the important points I want to make about doing quantum information science. It
is important to always challenge ourselves to distinguish the difference between classical and quantum information
processing machines. And it is important in these comparisons to not compare “deterministic” classical information
processing machines (ones in which the probabilities are always unity) to quantum machines, but to compare proba-
bilistic information processing devices. This doesn’t mean that comparing to deterministic machines isn’t important:
it’s just that it is often misleading. This is not to say that the quantum no-cloning theorem isn’t somehow different
that the classical no-cloning theorem. The quantum no-cloning theorem actually results in results which have no
classical equivalent...when we are using the quantum properties of the states.
 2

II. TELEPORTATION

If there could be teleportation, or teleportage, or whatever it is...

- Science fiction writer J. Wyndham, 1951

When a reporter asked Asher if quantum teleportation could teleport the soul as well as the body, Asher
answered, characteristically, “No, not the body, just the soul.”
- Obituary for Asher Peres, Physics Today, August 2005

Most of us first encounter teleportation when Captain Kirk and Spock decide to make a trip down to the surface of
a planet. This form of teleportation is a method to magically transmit people or objects from one location to another.
How this works is only known to television producers and Scotty. In this lecture we will talk about a different sort of
teleportation. In fact we will talk about two types of teleportation, classical teleportation and quantum teleportation.
Calling something teleportation makes it sound really cool and mysterious, but in this class you will find that while
quantum teleportation is certainly very interesting, it is not as surprising as you might initially have expected. This
is because there is a protocol in the classical world, the world of our probabilistic information processing device,
which is very much in the same spirit of teleportation. We call this protocol classical teleportation and actually most
of you have actually encountered this protocol before! Once we have talked about classical teleportation, I will use
the classical teleportation to “derive” quantum teleportation. This derivation follows along with a very nice article
written by David Mermin (“From Classical State-swapping to Quantum Teleportation”, Phys. Rev. A 65, 012320
(2002); quant-ph/0105117.)
Suppose that I have in my laboratory a qubit. I don’t know the state of this qubit, just that it is in some quantum
state (some external referee may know what this quantum state is.) Now you live a few blocks away from me and I
want to give my qubit to you such that this qubit is in the same state as it is in my lab. Well one thing I could do is
that I could pack up the qubit in a bag (only theorists can do this) and take the qubit over to your house. Then you
will have my qubit. But of course this is kind of a pain. For one thing, moving qubits around is not very easy to do
(that bag I used is not easily constructible) and further it often happens that in moving the qubit from one location
to another the qubit will lose its quantum nature (we’ll learn more about this problem when we study quantum error
correction.) So one thing I could ask is whether it is possible for me to pick up the phone and call you and tell
you some classical information which will alow you to construct a qubit just like mine at your home. Now from the
no-cloning theorem, we know that there is no way to take an arbitrary qubit |ψi and clone it |ψi ⊗ |ψi. Thus there
is no way for me to get you a copy of my qubit without, in some way, disturbing my qubit. Now the goal is for me to
just send you classical information. If I just perform unitary measurements on my quantum state and some ancilla,
this doesn’t really do anything to disturb the quantum information: it’s just rotated into some new basis. Thus the
only way for it to be possible for me to send the qubit using this classical channel is for me to perform measurements
which involve my qubit. But now we have a bit of a paradox: such a measurement will reveal some information about
the qubit (i.e. some information about the amplitudes α and β.) And this information will need to be transmitted
from me to you over the classical phone line. But now if this information is enough to be able to construct the qubit,
then it will be possible for multiple people who intercept our message to construct the qubit. But this would violate
the no-cloning theorem. Thus if there is going to be some sort of procedure for sending my qubit from me to you with
a classical phone line, the classical information transmitted over the phone line better not reveal anything about the
actual amplitudes of the qubit.

A. Classical Teleportation

And this line of reasoning now leads us to classical teleportation. Is there a way to send a classical probability
distribution over a bit from one party to another without revealing any information about the probability distribution?
There is! It is the classical prescription used in a one-time pad for sending information securely over a classical channel.
How does this work? Suppose that we have two parties, which we will now refer to as Alice and Bob in the convention
invented, I think, by cryptographers, and now universally used by those in quantum computing. Alice and Bob each
have one of two bits whose description is given by [ 12 0 0 12 ]T . In other words a fair coin is flipped an the value of
this coin is distributed to both parties. We will often call this a shared secret random bit. Sometimes I will call it
shared randomness (this will make sense when we talk about entanglement and Bell’s theorem.) OK, back to our
story at hand. Alice and Bob share this secret random bit. Alice has a classical system in the distribution [p 1 − p]T .
What Alice does to send her distribution to Bob is that she performs an exclusive or between her bit and the shared
secret random bit (recall that the exclusive or of two bits b1 and b2 is b1 + b2 mod 2. Now to someone who does not
know the value of the shared secret random bit, the result of this result will be a bit which appears to be totally
 3

random. If this result bit is sent from Alice to Bob, then an eavesdropper, Eve, can learn nothing about the original
bit [p 1 − p]T . Now when Bob gets the bit in his lab, he can use his version of the shared random bit to recover Alice’s
state [p 1 − p]T . He does this by performing an exclusive or between the bit he receives from Alice and his copy of
the shared classical key. Why does this work? Because exclusive or is a commutative operation and doing it twice
with the same value is the same as doing nothing.
Now I have made a further assumption here one which makes classical teleportation quite subtle. In particular I
am assuming that when I perform the exclusive or of two bits then the value of these bits is replaced by a single value
which is the output of this exclusive or. And this is what makes classical teleportation kind of subtle. Suppose that
instead of using an exclusive or which takes two bits as input and produces one output bit, we perform an exclusive
or which takes two bits as input and produces two bits as output. One way to do this is to use a controlled-NOT
operation (which we introduced as a quantum gate, but which we can port over to the classical world.) This transform
acts as (x, y) → (x, x ⊕ y). We can then use this transform in a classical circuit like this



v • (1)



 1

2
•
0
 
0
1
2

Here the first wire is a bit which Alice has. The second and third wires are one half of the shared random secret bit.
After the first controlled-NOT, the second wire is the “result” bit. At this point in the protocol it is sent from Alice
to Bob. Then Bob performs his controlled-NOT and the final state which is the “teleported” system is the third bit.
Now why is there a subtly here? Well because now technically the state we have after this procedure is not a state
where Bob just as [p 1 − p]T , uncorrelated with Alice’s system. And indeed we find that we have not violated the
classical no-cloning theorem but instead Alice and Bob have correlated bits.
What should we take from this? Well that if we can use irreversible gates where information can truly (whatever
that means) disappear, then we can teleport a classical probability distribution. However if we use reversible gates
then, while the bit Bob has will always behave like Alice’s bit, Alice will retain some correlation with this bit so we
haven’t exactly teleported the classical probability distribution.

B. Quantum Teleportation

Having discussed classical teleportation, we will now use it as inspiration for seeing if we can achieve a similar
function in the quantum world. So again to rehash, the setup is that Alice has a qubit and she wishes to transmit
this qubit to Bob using only a classical communication. Now the trick to teleporting in the classical bit from Alice
to Bob was to start them out with a shared secret random bit. What will the equivalent concept be for our quantum
protocol? It will be an entangled quantum state, say in analogy with the shared secret random bit, √12 (|00i + |11i).
But we’ll get to this in good time. To start our “derivation” of quantum teleportation, let’s start with a simple
quantum circuit.
Suppose that we want to swap two qubits. There is a unitary transform which does this and is called the SWAP
gate (surprising name, eh?) This gate is sometimes denoted by

|ψi × |φi (2)

|φi × |ψi
It is an easy exercise to verify that we can construct the SWAP gate using a series of controlled-NOT gates:



 

|ψi • • |φi (3)
|φi • |ψi
Now our goal is to SWAP our qubit from Alice to Bob (eventually using classical communication, not direct interaction
like we have now) so we will think in our minds as the first quantum wire being Alice’s qubit and the second being
Bob’s qubit. Now we don’t really require Bob’s qubit to be arbitrary in our attempt to do quantum teleportation.
Thus we will act arbitrarily and set |φi = |0i. When we do this we see that one of the controlled-NOT’s does not
matter:


 


 
 

|ψi • • |0i |ψi • |0i (4)
⇔
|0i • |ψi |0i • |ψi
 4

Now we are faced with a little bit of a conundrum. We know that we need to use entanglement in order to mimic the
classical teleportation. But to do this in our current setup, at the very least we need another qubit. So let’s just add
it. Further we need to interact with this qubit in some manner. So let’s do this by the following


 

• • • (5)



⇔

 

• •

Putting this into our circuit we now have the three qubit quantum circuit



 

|ψi • • |0i (6)


 

|µi • • |µi
|0i • |ψi
Well now we have a reasonable number of qubits, but do we have any entanglement? Recall that one way to create
a secret shared random bit is to take a random bit and use it as the control in a controlled-NOT. This will produce
the classical correlated state [ 12 0 0 12 ]T . A similar construction will work for creating an entangled quantum state.
In particular to generate the entangled quantum state √12 (|00i + |11i) we can do the following



√1 (|0i + |1i) • (7)
2
|0i
Now looking at our big circuit it seems most likely that we would like to use that second controlled-NOT to create
the entanglement. But how the devil to get rid of that first controlled-NOT?
Well recall that |+i = √12 (|0i + |1i) is the +1 eigenvector of X: X|+i = |+i. This in turn implies the simple
identity that



• (8)
⇔ |+i |+i
|+i
Thus if, in the big circuit we are constructing, we set |µi = |+i, we can eliminate the first controlled-NOT.


 


 
 

|ψi • • |0i |ψi • |0i (9)
⇔


 
 
 

|+i • • |+i |+i • • |+i
|0i • |ψi |0i • |ψi
Notice how we now have, in the first controlled-NOT a way to generate entanglement in our circuit. Now we are
getting somewhere! If we think about Alice having one half of this entangled quantum state and Bob having the other
half, then we begin to see a circuit which resembles our classical teleportation circuit.
But one really funny thing stands out. And that is the final controlled-NOT. It is a controlled-NOT “going the
wrong way,” i.e. acting from Bob back to Alice. How in the world are we going to get this to turn around and act in
the other direction? To see how to do this, we will need the Hadamard gate. Recall that the Hadamard matrix acts
as
 
1 1 1
H=√ (10)
2 1 −1

It has the properties that H 2 = I and the HXH = Z where X and Z are the particular Pauli matrices. Using these
properties, it is easy to see that

H 
 H Z (11)
⇔
•
•
 5

But the controlled-Z operation, is just the two by two operation

1 0 0 0
 
0 1 0 0 
Z = = • (12)
0 0 1 0 
0 0 0 −1
• Z

i.e. the controlled-Z, which we often call the controlled-PHASE gate is symmetric under exchange of the two qubits
it acts on. Using this fact we can now being to fathom how to “flip” the last controlled-NOT around. First we insert
identities I into the circuit

|ψi • 
 |0i (13)


H H H H


 

|+i • • |+i
|0i • |ψi
and then flip that last controlled-NOT to a controlled-PHASE

|ψi • • |0i (14)



H H
|+i • • |+i

|0i 
 
 Z |ψi

At this point it is probably just wise to act (backwards) with the last Hadamard to produce

|ψi • • |+i (15)



H
|+i • • |+i

|0i 
 
 Z |ψi

Well we are almost there. To finish things off, recall that it was our goal to teleport Alice’s qubit to Bob using
classical information. Thus it makes sense to measure the first two qubits in our circuit in the computational basis,

FE
|ψi • H • (16)



FE
|+i • •

|0i 
 
 Z |ψi

The result of this measurement will be 50% |0i and 50% |1i for both qubits, i.e these bits will be perfectly random.
Next we can use the fact that measurement in the computational basis commutes with a controlled wire of a controlled
quantum gate:

FE FE
• • (17)
⇔
U U

Here the double wires represent classical bits. I.e. in the second circuit we have made a measurement in the
computational basis and then depending on what the output of this measurement is, used this classical bit to apply
conditionally the unitary on the target qubit. Using this our circuit begins to look even more tantalizing:

FE
|ψi • H • (18)



FE
|+i • •

|0i 
 
 Z |ψi
 6

So what do we have here. The first controlled-NOT is used to create an entangled state of two qubits. One half of
this entangled state can be sent to Alice and to Bob. This will function just like the shared random secret bits. Next
Alice will take here qubit and her half of the entangled quantum state and perform a unitary transform followed by
a measurement. What is the effect of this unitary transform followed by a measurement?

FE
• H (19)



FE
Well suppose we feed in the state √1 (|00i + |11i)
into this circuit. Then this state gets transformed to |00i and we will
2
measure |00i with one hundred percent probability. Similarly one can check that the circuit transforms the following
inputs to computational basis states
1
|Φ+ i = √ (|00i + |11i) → |00i
2
1
|Ψ+ i = √ (|01i + |10i) → |01i
2
1
|Φ− i = √ (|00i − |11i) → |10i
2
1
|Ψ− i = √ (|01i − |10i) → |11i (20)
2
These for entangled states are called the Bell states (named after John Bell who we will encounter later when we
discuss entanglement.) So if any of these states are input into this circuit, then with one hundred percent probability
we will get the outcome corresponding to the appropriate computational basis state. Similarly if you have a more
general input which is a superposition of these states, then you will obtain, with a probability equal to the square of
the overlap between the Bell basis state and the input state. This type of setup, where we perform a unitary transform
followed by a measurement in the computational basis is often called “measuring in a different basis” Sometimes the
inverse of this unitary is then also applied after the measurement result has been copied to some classical bits. So we
now see that this part of the circuit serves to measure in the Bell basis.
Continuing on in our journey through our derived circuit, we see that having measured in the Bell basis Alice’s
qubit and her shared half of the entangled state, she will get one of four outcomes or two bits of classical information.
Alice can then take this information and send it to Bob. Bob then, depending on which of the four possible two bit
string’s he received apply the appropriate Pauli operator (either I, X, Z or ZX.) Then, quite astoundingly, Bob
will have Alice’s qubit |ψi! We have “teleported” the qubit from Alice to Bob. By sharing the entangled quantum
state √12 (|00i + |11i), Alice was able to transmit her qubit to Bob using only a classical phone line. This is rather
remarkable.
There are some interesting things to think about in the quantum teleportation protocol which often throw people
off when they first encounter it. The first is asking “where” Alice’s qubit went immediately after Alice measures in
the Bell basis. At this point in the protocol, there is no single system that has Alice’s qubit. It is only after Alice tells
Bob what her measurement outcome and Bob applies the appropriate transform that the qubit “reemerges.” Now
this will really bother you if you think about the qubit as a configuration and not as a description. At no point does
the qubit really disappear: it is just that our description is no longer isolated to a single qubit at all times during the
protocol.
The other thing to notice is that the measurement outcomes for the Bell basis are always perfectly random and do
not depend on the qubit state |ψi. This is good, because this is exactly what we were aiming for. If this had not been
true we could not have expected the protocol to work.
So that’s it. That’s quantum teleportation. Not quite as Spock-y as you might have thought, is it?

III. RULE 3 REDUX

In teleportation we’ve seen that performing a rotation and then making a measurement is like “measuring” in a
different basis. I’ve defined the measurement rule as always being a measurement in the computational basis, but
certainly we can make this rule a bit larger (eventually we’ll expand it even further!) In particular given a basis for
a quantum syste {|φi i}, i.e. a set of orthonormal (hφi |φj i = δi,j ) vectors which span the Hilbert space of quantum
system, we can define measurement in this basis by the following rule. If the quantum system has the quantum state
 7

|ψi, then the probability of getting outcome i (which corresponds to state |φi i) is given by P r(i) = |hφi |ψi|2 . If one
obtains outcome i for this measurement, then the new description of the quantum system is given by |φi i. It is easy
to check that if the basis is the computational basis {|ii} then this yields are old measurement rule. Further when
there is a different basis, the prescription for calculating the probability is to take the overlap of a basis element with
the quantum state and take its norm squared.
It is important to emphasize at this point that exactly what measurements we can perform on our quantum
system is dependent on the physics of the system. Sometimes the physics of the system will allow us to perform
measurements in many different basis. But most of the time, for example in most physical implementations of qubits
today, measurement in only one basis is really easy. One can effectively measure in a different basis by performing the
appropriate unitary rotation, measuring in a standard basis, and then rotating back. Thus, even though measurement
in any basis is not possible, we often are sloppy and talk about measuring in a different basis when it is very clear
how to perform these rotations and thus effectively measure in a different basis.

IV. SUPERDENSE CODING

We have seen that sharing an entangled state between Alice and Bob is a resource that these two parties can use
to teleport a qubit from Alice to Bob using two bits of classical information. What else might we use an entangled
quantum state for? One other very simple application is known as superdense coding. Superdense coding allows us
to use an entangled quantum state of two qubits to double the classical capacity of a quantum channel. Entanglement
can change qubit bit into two bits!
To see how this works, we return to the entangled quantum state |Φ+ i = √12 (|00i + |11i). Now suppose that Alice
has one half of this entangled quantum state and Bob has the other half. If Alice applies the single qubit unitary
operator X to her qubit, then the full action of this operator on both qubits is X ⊗ I. We can then check that
1
(X ⊗ I)|Φ+ i = √ (|10i + |01i) = |Ψ+ i (21)
2
What is neat about this is that |Φ+ i and |Ψ+ i are orthogonal. And from our new measurement rule this means that
if we can perform a measurement in a basis that contains these two states then we can distinguish between these
two states. Note that this measurement will be a measurement on both qubits at once. How does this help us in
superdense coding? Well it is easy to check that

(I ⊗ I)|Φ+ i = |Φ+ i
(X ⊗ I)|Φ+ i = |Ψ+ i
(Z ⊗ I)|Φ+ i = |Φ− i
(XZ ⊗ I)|Φ+ i = |Ψ− i
(22)

Where the states indicated are the Bell basis states defined above. Recall that these states are orthogonal. Notice
that we have only acted on Alice’s qubit. So this is how we can use an entangled quantum state to double the classical
capacity of a quantum channel from Alice to Bob. Alice and Bob start with on half of |Φ+ i. Alice wants to send two
bits a, b ∈ {0, 1} to Bob. To do this she applies X a Z b to her half of |Φ+ i. She then sends her half of the entangled
quantum state to Bob. Now Bob, since he has both qubits of the entangled state can perform a measurement in the
Bell basis. When he does this he will obtain one of the four outcomes corresponding to the different Bell basis states.
In fact he will obtain only one of these results and these four outcomes will be cover exactly the four different bits a, b
that Alice wanted to send to Bob. So by performing this measurement Bob can learn two bits of information. But
Alice only sent a single qubit! This is very strange and is called superdense coding.
Now one might worry that this isn’t so strange because when we send a qubit from Alice to Bob, why can’t we
just send an infinite amount of classical information in the α and β amplitudes of our qubit α|0i + β|1i? Well this
has certain tripped up more than its fair share of very smart people (I have seen Nobel prize winners make this
mistake!) The reason, philosophically, is that the amplitudes of a qubit are more like probabilities than they are like
real properties of our system. Thus you might as well ask why sending a probabilistic bit doesn’t allow one to send an
infinite amount of classical information in the probability p. More concretely there is a theorem, known as Holevo’s
theorem which says in a very precise way that a qubit can only be used to send a single bit of classical information
(when there is no extra entanglement hanging around!) Now I’m using argument by authority here, which is just
disgusting, but it is true and later we may get a chance to examine Holevo’s beautiful theorem. But in a smaller
sense we can already begin to grasp why we cannot use qubits to send more than one classical bit (without the aid
 8

of entanglement!) Suppose that I encode two bits of information into the different states |0i, |1i, |+i, |−i. Now if I
perform a measurement on this qubit, there is no way for me to learn, with total certainty the value of these two
bits? Why? Because states like |0i and |+i are not orthogonal. Thus measurements in some basis will never yield
a measurement outcome with certainty (because all such basis elements that have some overlap with |0i must have
some overlap with |+i.) Thus we can see, intuitively at least, that we can’t use a qubit to send more than a classical
bit of information as long as we don’t have some spare entanglement lying around. And this is what makes superdense
coding even more interesting!

Acknowledgments

The diagrams in these notes were typeset using Q-circuit a latex utility written by graduate student extraordinaires
Steve Flammia and Bryan Eastin.