Quantum Computing

48$1780
&20387Ζ1*
$&5&35(66)5((%22.
Introduction
1 - Quantum Information
2 - Quantum Computers
3 - Quantum Computing
4 - Quantum Gates, Quantum Circuit and

Quantum Computation
5 - Superconducting Quantum Computing

Devices
6 - Application Areas
@CRCPreu
A!AWU)O.fOAN(lllOO•
QUANTUM
COMPUTING
VISIT WWW.ROUTLEDGE.COM
TO BROWSE FULL RANGE OF QUANTUM COMPUTING TITLES
SAVE 20% AND FREE STANDARD SHIPPING WITH DISCOUNT CODE
JML20
CHAPTER 15
Quantum Information
CONTENTS
15.1 Quantum Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
15.2 Entanglement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
15.3 Cloning and Teleportation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
Teleportation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
15.4 Quantum Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
The quantum Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
15.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
This chapter aims to introduce some of the applications of the ideas of quantum
mechanics that were developed during the last twenty years or so of the twentieth
century. The topics chosen reflect our increased understanding of a number of areas
and its application to new phenomena that have been predicted and sometimes
observed. They all rely on the interplay between the two types of time dependence
implicit in the fundamental postulates set out in Chapter 6:
Postulate 5 Between measurements, the development of the wave function with time
is governed by the time-dependent Schrödinger equation.
Postulate 2 Immediately after a measurement, the wave function of the system will
be identical to the eigenfunction corresponding to the eigenvalue obtained as a result
of the measurement.
In practice, there is generally a clear distinction between “unitary evolution”

under the influence of the time-dependent Schrödinger and the “collapse” associated
with a measurement. In unitary evolution (so called because in a matrix representa-
tion, the initial and final states are connected by a unitary matrix) the final state of the
system is completely determined by the Hamiltonian operator and the initial state. It
follows that unitary evolution is reversible, because the initial state can be generated
from the final state by the same time-dependent Schrödinger equation with the sign
of the time coordinate reversed and ψ replaced by ψ∗ . In contrast, the result of a
quantum measurement is generally unpredictable: the system collapses at random
343
344 Quantum Mechanics
into one of a set of possible outcomes, which is an irreversible change that occurs
in one time direction only. Although, in practice, we easily know when to apply
which form of time dependence, it is difficult to set objective criteria for this, and
we shall discuss the consequent “quantum measurement problem” in more detail in
Chapter 16.
Most of our discussion in this chapter will refer to the behaviour of what have
become known as “qubits.” A classical bit is a system that can exist in one or other
of two possible states, conventionally used to represent zero and one; a qubit is a
quantum system that can exist in one of two base states, but can also be in a state that
is a linear combination of these. A prime example is the spin-half particle, whose
component of angular momentum relative to the z axis can have the values ± 12 , with
corresponding eigenstates αz and βz . As we saw in Chapter 9, the spin could also be
measured relative to some other direction, producing new eigenvectors that could be
expressed as linear combinations of the old. For example, if α x and β x respectively,
represent positive and negative spin measured with respect to the x direction
α x = 2−1/2 (αz + βz )
β x = 2−1/2 (αz − βz ) (15.1)
cf. Chapter 9 (9.23).

Another example of a qubit is a plane-polarized photon. Plane polarization is a
familiar concept in classical optics where it refers to the plane in which the E vector
of the electromagnetic wave vibrates, and when experiments are done on weak light,
it is found that this property can also be applied to individual photons. The two states
of polarization follow very similar rules to the spin directions in the case of a spin-
half particle, but the angles are halved. Thus, if the base states correspond to a photon
polarized horizontally and vertically, respectively, the state of a photon polarized at
±45◦ to the horizontal axis can be expressed as linear combinations of the base states
using (15.1), where αz and βz now represent photons with horizontal and vertical
polarization, while α x and β x correspond to ±45◦ polarizations.
Atoms can also be used as qubits despite the fact that they generally have an
infinite number of bound states! This is achieved by ensuring that they are isolated
from all external influences other than radiation whose frequency matches the energy
difference between two of the states. To minimize the frequency of unwanted
collapses due to spontaneous transitions between the states (cf. Chapter 11), systems
are normally chosen where this energy difference is very small. Qubits have also
been constructed from semiconductors and from superconductors; in the latter case,
the two states typically correspond to opposite directions of current flow around a
superconducting ring.
Throughout this chapter, our prime example of a qubit will be the spin-half
particle, because that has been discussed in detail in earlier chapters. However,
practical applications often use other systems and we shall indicate this from time
to time.
Quantum Information 345
15.1 QUANTUM CRYPTOGRAPHY

Cryptography is the science of the exchanging of messages in a coded form that
makes them indecipherable to anyone else. We shall not attempt anything like a full
survey of this immense subject, but will concentrate on how the particular properties
of quantum systems can be used in this area. To transmit any message at all, it
must be coded in some way. The pages in this book do so using the alphabet and
other symbols, as well as relying on the reader’s and writer’s knowledge of the
English language and of mathematics. When the present edition was written using
a computer with a word-processing package, the letters, figures and symbols were
further encoded by the computer into a set of binary bits, represented by two symbols
“1” and “0.” In this way any message at all can be represented by a sequence of 1s
and 0s, and any system that is capable of existing in two distinct states can be used to
encode such a representation of a message. This procedure is now universally used
in electronic transmission where the bits are typically represented by voltage pulses
of different sizes.
The essential property of an encrypted message is that the information in it
should be understandable only to the sender and the receiver, and be meaningless
to a third party. This is achieved by processing the message using some procedure
known as a “cypher,” which can be decoded only if the reader is in possession
of a “key.” Early keys were in the form of code books, but modern cryptography
uses mathematical procedures that depend on knowing a comparatively small key,
typically a few thousand binary bits in length.
For example, a message, M, could be coded as E by the algorithm
E = Ms mod c (15.2)
where the right-hand side means that the number M is raised to the power s and the
answer expressed as a number to base c. If c is a product of two prime numbers (p
and q), it can be shown that the message can be decoded by the algorithm
M = Et mod c (15.3)
where t is a simple function of p and q. However, if p and q are not known, the
message is secure and all the other quantities can be exchanged publicly. If c is
large enough, breaking the code by searching for its prime factors would take a
conventional computer an impossibly long time (more than 106 years if c is 1000
binary digits in length). As we shall see later in this chapter, this factorization
problem is one where quantum computers could, in theory, make a dramatic
contribution, but it may well be 106 years before this technology is available!
The present section describes a method whereby a sender and receiver can both
acquire knowledge of a number to be used as a key to a code, while being sure that
no eavesdropper knows it. As we shall see, it cannot be directly used to transmit
previously defined numbers like p and q, because even the sender does not know
in advance what the shared number is going to be. However, the commonly held
information can be used to decide on which of a number of previously agreed
protocols is to be used; e.g. which pair of primes contained in a previously prepared
Alice Bob
z or x z or x
z or x
Eve
FIGURE 15.1 Alice sends a series of qubits to Bob, which are αz /βz or α x /β x at
random. Bob makes a similar set of randomly selected x or z measurements on the
qubits he receives. They then exchange information on the measurement orientations
they have chosen and use the results for the subset where these are the same, to define
the key to be used. In the absence of Eve’s intervention, Alice and Bob have the same
key, but this no longer holds if Eve has attempted to make a measurement.
list are to be used as p and q. In this way they can both follow the same coding
process, even if they do not know what this is going to be before the exchange takes
place. This key distribution process is where quantum mechanics comes in.
A sender (conventionally known as “Alice”) transmits a message to a receiver
(“Bob”) in the form of a stream of qubits where, say, αz and βz represent 0 and 1,
respectively. As we shall see, the specifically quantum properties of the particles
allow us to detect the presence of an eavesdropper (“Eve”) who is intercepting the
message and retransmitting it to Bob while hoping to do so undetected. The setup is
illustrated in Figure 15.1
The central idea is that Alice sends a sequence of qubits where some are in
the form αz or βz , but others are represented by α x or β x . Both αz and α x are to
be interpreted as 0, while βz and β x represent 1. Which orientations Alice uses are
decided at random, but she keeps a record of them. When Bob detects the qubits, he
also varies the orientation of his apparatus between the z and x directions at random
and records which apparatus he uses, as well as the results he obtains. Alice and
Bob then publicly tell each other which settings they used in each case and discard
those that were not the same—on average half the total. The remainder consists
of a set of numbers whose values they both know, and which they can then use to
decide which procedure they will follow to encode and decode messages sent openly
between them.
We now consider the effect of the possible intervention of Eve. She may intercept
the qubits sent by Alice, but she has no means of knowing the orientation of Alice’s
TABLE 15.1 The properties of a typical set of 12 qubits analyzed

by the apparatus shown in Figure 15.1. The asterisks in the final
column mark cases where Eve’s intervention has resulted in Bob
having the wrong result. (O: apparatus orientation; S: state of sent
qubit; M: message; R: state of received qubit; a/r: accepted or
rejected; K agreed common key; K : key corrupted by Eve )
Alice Bob Eve Bob
(Eve inactive) (Eve active)
O S M O R a/r K O R/S R K
z α 0 z α a 0 x α β 1*
z β 1 z β a 1 x β α 0*
x α 0 z α r z β β
z β 1 x α r x α α
x α 0 x α a 0 x α α 0
x β 1 z β r x β β
z β 1 x β r z β β
x β 1 z β r z β β
x α 0 x α a 0 x α α 0
x α 0 z α r z α α
z α 0 z α a 0 x α β 1*
z β 1 z β a 1 z β β 1
apparatus when they were sent. The simplest thing she can do is randomly guess
which orientation might have been used for a particular qubit, set her apparatus in
this orientation, record the result, and send a qubit in the same state as that just
recorded on to Bob. On average, she will guess right one-half of the time, but there is
only a 50% probability that this guess will be the same as Bob’s. The upshot is that
about one-half of the qubits that Bob later believes are reliable, have been corrupted
by passing through Eve’s apparatus set in the “wrong” orientation. About one-half
of these (i.e., one-quarter of the final sequence used as the key) will decode as bits
that are the opposite of those sent by Alice. Alice and Bob therefore no longer have a
set of numbers in common and soon find they cannot decode each other’s messages.
They have therefore detected the presence of Eve and can take appropriate action.
Worked Example 15.1 Illustrate the above procedure by considering the processing of a
string of twelve qubits sent by Alice to Bob in (i) the presence and (ii) the absence of Eve.
Solution See Table 15.1.
This protocol succeeds because of the collapse resulting from a quantum

measurement. A necessary concomitant of this is the system’s vulnerability to
random processes (noise). Even in the absence of Eve, Alice and Bob will
successfully end up with a common key only if their apparatuses are accurately
aligned when they believe they are, and if the polarization state has not been changed
(e.g., rotated slightly) during the transmission. Moreover, even though Eve cannot
accurately read the message and her attempt to do so can be detected, her presence
apparently makes the channel of communication useless. There are strategies for
combatting this by further public exchange of information, as a result of which Alice

and Bob can end up with a shared key considerably shorter than the length of the
shared message, but with a very low probability of Eve also knowing it.
Unlike the cases to be discussed in the rest of this chapter, quantum cryptography
is reasonably easy to carry out experimentally. Secure key interchange has been
demonstrated by sending polarized photons over distances of up to about 100 km of
standard optical communication fibre and there is active research aimed at extending
this to worldwide distances.
15.2 ENTANGLEMENT
The remaining examples discussed in this chapter involve two or more particles in
what is called an “entangled state.” In quantum mechanics, the word “entanglement”
refers to a quantum state of two or more particles, where the probabilities of the
outcome of measurements on one of them depend on the state of the other—even
though there is no interaction between them.
As an example of entanglement, consider two spin-half particles in a state where
they are far apart, their spins are opposite and we have no other information about
them. The spin part of their wave function has the form
ψ(1, 2) = 2−1/2 [αz (1)βz (2) − βz (1)αz (2)] (15.4)
where αz (i) and βz (i) represent particle i with a positive and negative spin component,
respectively, relative to the z axis. However, the only information this wavefunction
contains is that the spins are opposite—it does not tell us the absolute direction of
either spin. This is because ψ(1, 2) is independent of the direction of the axis of
quantization: to see this, we apply the transformation (15.1) to express ψ(1, 2) in
terms of α x (i) and β x (i) and get

ψ(1, 2) = 2−3/2 [α x (1) + β x (1)][α x (2) − β x (2)] − [α x (1) − β x (1)][α x (2) + β x (2)]
= −2−1/2 [α x (1)β x (2) − β x (1)α x (2)] (15.5)
which is the same as (15.4) with z replaced by x, apart from an irrelevant change
of sign. We can therefore drop the suffixes on α and β when we describe qubits
entangled in this way.
We now consider the effect of performing a measurement of the z component
of either of the spins when the system is in the state ψ(1, 2). Clearly we expect to
get a positive or a negative result at random with equal probability. But suppose we
measure the spin of particle 2 after we have measured the spin of particle 1 and
obtained (say) a positive result. As a result of this first measurement, the system
will have collapsed into an eigenstate of the spin-component operator with positive
eigenvalue. It therefore has the form
ψ(1, 2) = αz (1)βz (2) (15.6)
and we now know that the particles are in eigenstates of Ŝ z , because the state has
been disentangled. A measurement of the z component of the spin of the second

particle can now only yield a negative result, whereas there would have been equal
probability of a positive or negative result if we had made this measurement before
that on particle 1. It follows that the probabilities of obtaining particular values of the
spin of one particle can depend on what measurements have been previously carried
out on the other. It should be noted that this result is independent of other properties
of the particles, in particular their position: particles that have interacted and become
entangled can maintain this be entanglement even when they have moved a long
distance apart. This apparent influence of the operations carried out on one particle
on the properties of a distant particle is known as “nonlocality” and we discuss its
implications for our understanding of the conceptual basis of quantum mechanics in
Chapter 16.
Various techniques for creating entangled states have been developed in recent
years. Probably the most popular is now the application of “parametric down
conversion.” This involves the use of nonlinear optics in which a photon incident on
a crystal is converted into two photons, the sum of whose frequencies equals that of
the original photon (so that energy is conserved); the two emitted photons are found
to have perpendicular polarizations, although their absolute polarization is unknown.
15.3 CLONING AND TELEPORTATION

“Cloning” is a word used in biology to describe the creation of a living organism
that has identical genetic make up to another existing organism. In quantum physics,
the term refers to attempts to transfer the quantum state of one “reference” system
to another “target” system, without relying on prior knowledge of the reference state
and without disturbing it in the process. As we shall see, quantum cloning defined
in this way is impossible. To prove this, we consider two quantum systems with the
same composition; they might be qubits, but they could be more complex systems
such as two hydrogen atoms. Initially the target (system 1) is in a state φ(1) and we
are looking for a general procedure that will transform its state to be the same as the
state, ψ(2), of the reference system (system 2) without affecting the state of system 2
and without relying on any prior knowledge of the state of system 2. That is, we
are looking for a procedure that will perform the following transformations on the
composite state of the two systems
φ(1)ψ(2) →ψ(1)ψ(2)
(15.7)
where ψ(2) is any allowed state of system 2.

First consider the effect of making a measurement on this system. By definition,
cloning requires (15.7) to hold whatever the state of system (2), including states that
are not eigenstates of the measurement operator. However, all measurements result in
the wave function collapsing into an eigenstate of the measurement operator, which
in general results in a change in the state of system 2. As we have defined cloning
as a process that operates whatever state is represented by ψ(2), we conclude that

cloning by measurement is impossible.
Now suppose that we allow the composite system to evolve in a unitary manner
following the time-dependent Schrödinger equation under the influence of some
Hamiltonian H(1,ˆ 2). We consider two of the possible states represented by ψ(2) and
label these as ψA (2) and ψB (2). Substituting these in turn into (15.7), we take the
product of one of the resulting left-hand sides with complex conjugate of that of the
other. The time dependence of this product is then:

∂
φ∗ (1)ψ∗A (2)φ(1)ψB (2)dτ1 dτ2 =
∂t

− (i/h̄) φ∗ (1)ψ∗A (2)H(1, ˆ 2)φ(1)ψB (2)dτ1 dτ2

+ (i/h̄) φ(1)ψB (2)Ĥ ∗ (1, 2)φ∗ (1)ψ∗A (2)dτ1 dτ2
=0 (15.8)
where we have used the time-dependent Schrodinger equation and its complex
conjugate—c.f. (11.1) and (11.2)— along with the fact that Ĥ is Hermitian. (15.8)
means that the integral of the product of the wave functions does not change with
time. It therefore follows from (15.8) that if (15.7) holds

∗ ∗
φ (1)ψA (2)φ(1)ψB (2)dτ1 dτ2 = ψ∗A (1)ψ∗A (2)ψB (1)ψB (2)dτ1 dτ2 (15.9)
or 2
ψ∗A ψB dτ = ψ∗A ψB dτ (15.10)
This is true only in the special cases where the integral on the left-hand side is zero
or unity, which means that there is no such general procedure and the no-cloning
theorem is proved.
If the no-cloning theorem were not true, we could in principle create a large
number of cloned systems whose properties could be measured without significantly
affecting the ensemble as a whole and this would potentially be in breach of the
uncertainty principle. Suppose, for example, we have a spin-half particle in a state
where the direction of spin is unknown. If a large number of identical copies of these
could be made by cloning, then all three components of spin could be accurately
measured on the resulting ensemble, even though the operators representing them do
not commute.
Teleportation
The word “teleportation” entered the English language via the science-fiction
television series Star Trek. In this fantasy, a person or object could be transported to
a distant destination using a transmitter that measured all the properties of the object
Teleported
Bob
SEP
(2)
BMA Alice
Object
FIGURE 15.2 Quantum teleportation. SEP represents a source of entangled pairs of

particles. One member of a pair is sent to Bob while the other is sent to Alice, who
allows it to interact with the object qubit and uses the Bell measurement apparatus
(BMA) to project their state into one of the four Bell states. Alice then uses a classical
communication channel to tell Bob which of these results she obtained. Bob can then
transform the state of the teleported qubit into one identical to the initial state of the
object qubit.
and sent them (presumably by some radio link) to a receiver that reassembled the
information to recreate the object. In the process the original object was destroyed
(dematerialized?). In the quantum analogue, teleportation is the same as quantum
cloning except that the state of the reference system is inevitably changed in the
process. We consider, as a simple example, an object qubit, such as a spin-half
particle, in a state given by
ψ(3) = Aα(3) + Bβ(3) (15.11)
where the values of A and B are unknown. An experimentalist (Alice, of course)

wants to transfer these values to a target qubit (1), which she is to send to another
experimenter (Bob). She first performs an experiment to entangle qubit (1) with
another qubit (2) so that their quantum state has the form given by (15.4). The total
wave function of all three particles is therefore
Ψ(1, 2, 3) = 2−1/2 [Aα(3) + Bβ(3)][α(1)β(2) − β(1)α(2)] (15.12)

This is algebraically identical to the expression

1 1
Ψ(1, 2, 3) = − [Aα(1) + Bβ(1)]ψ1 (2, 3) + [Aα(1) − Bβ(1)]ψ2 (2, 3)
2 2
1 1
− [Aβ(1) + Bα(1)]ψ3 (2, 3) − [Aβ(1) − Bα(1)]ψ4 (2, 3) (15.13)
2 2
where
ψ1 (2, 3) = 2−1/2 [α(2)β(3) − β(2)α(3)]

ψ2 (2, 3) = 2−1/2 [α(2)β(3) + β(2)α(3)]
ψ3 (2, 3) = 2−1/2 [α(2)α(3) − β(2)β(3)]
ψ4 (2, 3) = 2−1/2 [α(2)α(3) + β(2)β(3)] (15.14)
as can be checked by expanding the right-hand sides of (15.12) and (15.13). This set
of states can be shown to have the maximum possible entanglement for two spin-half
particles and are known as “Bell states” (after John Bell—see Chapter 16) .
Alice sends particle 1 to Bob and then performs a measurement on particles 2 and
3. The essential feature of this “Bell state measurement” is that it is represented by an
operator whose eigenfunctions are the four ψi s, so that the whole system, including
particle 1, collapses into one of these states. Alice communicates the result of this
to Bob, using a classical channel of communication—cf. Figure 15.2. Thus, if Alice
obtains the result corresponding to ψ1 , Bob’s particle (1) must have the same spin
function as was originally possessed by particle 3, which of course was Alice’s
original intention. If she obtains one of the other results and lets Bob know, then
Bob can transform the state function into that required, simply by rotating the spin
using a magnetic field B for an appropriate time. For example, to generate the second
square-bracketed expression in (15.13) from the first, we use (11.14) in Chapter 11
to get
1 1
A(t) = A(0) exp(− iω p t) and B(t) = B(0) exp( iω p t) (15.15)
2 2
where ω p = eB/m. We get the required result (apart from an irrelevant phase factor)
if t = πm/eB. We emphasize that teleportation transfers the full quantum state of
the object qubit to the target, but, as always in quantum mechanics, only part of
this is revealed in any single measurement. However, the statistical properties of the
teleported state of the target are predicted to be the same as those of the object qubit
in the absence of teleportation, and this has been verified experimentally.
A major challenge to the practical realization of quantum teleportation is making
a measurement that collapses the system into one of the Bell states. If, for example,
we were simply to measure a component of spin of one of the particles, we would
cause the system to collapse into the corresponding eigenstate, which is not one of
the Bell states. To perform a Bell-state measurement successfully, we must address
both qubits 2 and 3 simultaneously and execute a measurement that is sensitive to
their relative properties, but does not produce any information about their individual
D1
a
c
d
b
D2
FIGURE 15.3 Two photons (a and b) are simultaneously incident on a semitranspar-

ent mirror where each is reflected and/or transmitted with equal probability, and then
detected by one of the detectors, D. If photons are simultaneously detected in both
detectors, this constitutes a Bell-state measurement.
states. Figure 15.3 illustrates how this could be partially achieved for two qubits,
which in practice are normally photons. Qubits 2 and 3 are represented by polarized
photons, which strike a semitransparent mirror simultaneously (i.e., within a time
short compared with the length of the associated wave packets) from opposite sides.
To understand how this can lead to a Bell-state measurement, we have to go beyond
the spin states set out in (15.14) and include a representation of the spatial parts
of the wave functions. Referring to figure 15.3, we denote the spatial parts of the
wave functions of the two beams approaching the beam splitter by a and b. As
photons are bosons, the total wave function (15.13) must be symmetric with respect
to exchange of labels 2 and 3. Referring to (15.14), we see that the spin function ψ1
is antisymmetric and the others are symmetric. It follows that when constructing the
total wave function the ψi (2, 3) must be multiplied by
2−1/2 [a(2)b(3) ± b(2)a(3)] (15.16)
where the negative sign applies when i = 1 and the positive sign for i = 2, 3, 4.
We now consider the effect of the semitransparent mirror from which the photons
emerge in states c and d—see Figure 15.3. Each photon has an equal probability of
transmission or reflection, so it is impossible to tell which path was followed by any
particular detected photon. The wave function in beam c is made up of a reflected
component that originated in beam a and a transmitted component that originated in
b. Similarly, d is a superposition of a transmitted part from a and a reflected part from
b; moreover, because this last reflection was at the interface with an optically denser
medium, a change of sign is introduced at this point. We represent these relations by
1
a →2− 2 (c + d)
1
b →2− 2 (c − d) (15.17)
After substitution from (15.17) the expressions in (15.16) become
2−1/2 [d(2)c(3) − c(2)d(3)] , if i = 1

and 2−1/2 [c(2)c(3) − d(2)d(3)] , otherwise. (15.18)
It follows that, if we detect one photon in detector D1 and the other in D2 , then
one must have been in c and the other in d, so only the first alternative can apply.
This means that photons 2 and 3 have been successfully measured to be in the first
Bell state and the initial state of photon 3 has been successfully teleported to photon
1. However, if both photons are detected in either D1 or D2 no Bell state is uniquely
determined by this measurement and no teleportation is possible. As ψ1 , is one of four
equally weighted Bell states that make up the original wave function, teleportation
occurs only 25% of the time. When a photon is registered in each of the two detectors,
Alice can tell Bob that the properties of the object photon have been successfully
teleported to his target photon. More sophisticated experimental arrangements, with
four possible outcomes, each of which corresponds to one of the Bell states, have
been devised. One of these is based on the parametric up-conversion of two photons
into a single photon followed by manipulation of its state.
We note that a classical communication channel by which Alice communicates
the result of her measurement to Bob is an essential part of the experiment and, as
she must identify one of four possibilities, two bits of classical information must be
transmitted in this way. This is an example of a general principle that forbids the
transmission of information using entanglement alone. Otherwise we could transmit
information instantaneously in breach of the principles of special relativity. We shall
return to this point in Chapter 16.
The principles of quantum teleportation have been experimentally demonstrated
for polarized photons and also using atomic beams. However, this is a long way from
Star Trek! Before any significantly complex object could be teleported, it would have
to be coupled in some way to a system consisting of as many entangled particle pairs
as the number of parameters needed to define the reference state. The practicability
of this is certainly well beyond our present technology.
15.4 QUANTUM COMPUTING

A conventional computer manipulates binary bits according to a set of rules, the
operation performed on one bit often depending on the state of one or more of the
others. In a “quantum computer” the binary bits are qubits and the operations proceed
by unitary evolution (as discussed earlier in this chapter, this means that the states
of the qubits evolve according to the time-dependent Schrödinger equation) until
we make measurements on them. All the basic operations of a classical computer
can be carried out using a quantum computer, though sometimes more elaborately
for reasons to be discussed later. There is, therefore, no obstacle in principle to the
construction of a quantum computer that would carry out the same computations as
a classical computer. However, the emphasis must be on the phrase “in principle.”
As we shall see, a useful quantum computation involves the entanglement of a
significant number of qubits; such entangled states are extremely sensitive to noise
and decoherence, so the practical obstacles to constructing a useful device are
immense, and overcoming them would almost certainly involve the development of
a completely new technology.
Of course, there is no reason why anyone would go to such trouble to construct
something that could do no more than a conventional computer. The great interest
in quantum computers is that, although they would carry out most computing
tasks no more efficiently than conventional machines, there are some processes that
would be performed at an immensely faster speed. An often-quoted example is the
factorization of a large number into its prime-number components by a method
known as Shor’s algorithm, after the person who devised it; as mentioned earlier, if
this operation could be efficiently performed it would endanger the security of some
commonly used cryptographic protocols. The factorization of a number consisting
of N decimal digits using a conventional computer requires a number of computing
steps that is proportional to exp(2L1/3 ln L2/3 ), where L = ln N. In contrast, the number
of operations required by a quantum computer has been shown to be about 300L3 .
For L equal to 10, the classical algorithm is faster, but the quantum computer takes
over for larger numbers: for L = 200, the calculation would take 109 years classically,
but could be performed by a quantum computer in about 8 hours.
As a first step to understanding the principles of quantum computation, we
consider a particular simple operation, known as a NOT gate. This has the property
of reversing the state of a bit: if we input 0 we get out 1, while if we input 1 we get
out 0. (Because it acts on one bit at a time, a NOT gate is an example of a “single-bit”
gate). It is very easy to devise a unitary operation that will carry out this procedure
on a qubit. We represent 0 and 1 by the spin-up (αz ) and spin-down (βz ) states of a
spin-half particle, which we subject to a field directed in the y direction. The spin
precesses according to (11.17) in Chapter 11 and if we apply the field for the correct
length of time, its direction will be reversed: i.e. αz → βz and βz → −αz , which is just
what we expect from the operation of a NOT gate (NB, the sign change is a result
of the phase change associated with spin rotation discussed in Chapter 11 and is not
relevant to the present discussion).
Suppose now we perform the same operation, but starting from a state where the
spin is not in an eigenstate of S z , but in one that is a linear combination of αz and βz .
(To simplify the notation, from now on we shall drop the subscript z when referring
to eigenstates of spin measured along the z axis.) We now get
Aα + Bβ → Aβ − Bα (15.19)
We see that both the operations α → β and β → −α are now contained in this single
operation. This procedure is central to quantum computation and is known as the
operation of a “Hadamard gate.”
A single NOT gate can be considered as a very simple computer, programmed
to perform a single operation. If this were a conventional device, we could fully
determine its properties only by running it twice: once with each of its possible inputs
(0 or 1). In the quantum case, however, if we run the program once only using, say,
α x as input, then the wave function of the output is a linear combination of both
outcomes. Thus, both calculations have been performed in one step!
We might be forgiven for being less than impressed by this, when we realize that
we could do the same thing by inverting a classical pointer held at an angle to the
horizontal—because reversing the direction of any vector reverses the direction of
all its components. In one sense, a quantum computer has much in common with
a classical analogue computer, but the power of a quantum computer is realized
only when it operates on a quantum state made up from a number of qubits
simultaneously, and this could be modelled classically only if our pointer existed
in a many dimensional space —2n dimensions in the case of n qubits.
An important restriction on the power of quantum computing is that, in order to
access the result of a calculation, we must make a measurement and this inevitably
causes wave function collapse. This means that in the case of the simple example
above, although both α and β are operated on simultaneously, only one of these
components can be measured in one operation, so there is apparently no practical
gain in performing the calculation in this way. For this reason, quantum computation
often has little or no advantage over conventional methods. However, there are
important exceptions to this rule and these relate to cases where the aim is to extract
a single piece, or a small number of pieces, of information that would require a
long and complex computation to determine classically. One example is searching
a large database for a single match and another is the determination of the period
of a periodic function. (For reasons we shall not go into, the latter is a key part of
the algorithm to factorize a product of two prime numbers mentioned above). We
shall give an outline of the principles of how the latter calculation could be carried
out, provided the correct unitary operations could be performed and the appropriate
measurements made. We shall see that a subtle interplay of unitary evolution and
collapse can be employed to perform this calculation with very high efficiency
We first note a further important constraint on the operation of a quantum
computer. This arises from the fact that the Schrödinger equation is time-reversible,
by which we mean that if we make the substitution t → −t, the equation is still valid.
Thus, if a system undergoes a unitary evolution from one state to another, it must also
be able to reverse the process in a similar manner; an example of this is the rotation of
a spin state in a magnetic field as discussed above, which can be reversed by applying
a field of the same strength and for the same time, but in the opposite direction. A
corollary of this is that each operation must have the same number of outputs as
it has inputs. To understand this, think of an operation where the input consists of
two numbers and the output consists of their sum: it is impossible to reconstruct the
original pair uniquely if the only information we have is the final result. This does not
mean that a quantum computer cannot perform an addition, but the process is more
complex than that employed classically and involves retaining more information.
Suppose we have a quantum computer that contains a number of qubits, which we
shall continue to think of as spin-half particles. We shall use n of these to construct
what is known as a register that can be used to represent all numbers from 0 to
2n − 1. We first want to set our register to zero, which means that all qubits must be
in the state α; this can be achieved by applying a magnetic field in the z direction
and allowing the spins to relax into their ground state. (NB: this is an example of an
irreversible measurement). Now consider the result of applying a magnetic field in
the y direction for a time sufficient to rotate the spins through 90 degrees so that they
are all in the state α x ; in the case where n = 3, this state is
χ =α x (1)α x (2)α x (3)
=2−3/2 (α1 + β1 ) (α2 + β2 ) (α3 + β3 )
=2−3/2 [α1 α2 α3 + α1 α2 β3 + α1 β2 α3 + α1 β2 β3
+β1 α2 α3 + β1 α2 β3 + β1 β2 α3 + β1 β2 β3 ] (15.20)
where α x (i) represents atom i in state α x and we have made a small change in notation
from the second line onwards, where αi represents atom i in state αz . These final eight
combinations of α and β are just the binary representations of the numbers zero to
seven, so generalizing, we have

N−1
− 12
|χ = N | j (15.21)
j=0
where N = 2N and | j represents the state of the three qubits equivalent to the binary
representation of the number j; our example treated the case where N = 8, but (15.21)
holds for any number of qubits. We see therefore that the application of the magnetic
field has transformed the state from one representing the number zero, to one that
is a linear combination of the representations of all the numbers from zero to seven.
We note that this operation is unitary, because the system is governed by the time-
dependent Schrödinger equation. It is also reversible as the original state can be
restored simply by applying a field in the opposite direction.
We shall call the register just discussed the x-register and we now suppose that we
have another register (the y-register) containing two qubits (numbered 4, 5), which
are initially in the state α. We now perform what is called a controlled NOT (or
CNOT) operation; this acts on the state of a particular qubit in the y-register (known
as the “target qubit”) leaving it alone or reversing its state, depending on the state
of a particular qubit in the x register (the “control qubit”). In particular, if qubit(2)
is zero, qubit(4) remains zero, while if qubit(2) is one qubit(4) is changed to one.
(In principle this could be achieved by focusing the magnetic field created by the
magnetic dipole associated with qubit(2) onto qubit(4) and applying a further field to
cancel this out or reinforce it, depending on whether qubit(2) is in the state α or β,
respectively.) The state of qubit(5) is subjected to the same procedure, using qubit(3)
as the control. Because the state of the first three qubits is the linear combination
(15.21), the five qubits end up in an entangled state that can be expressed as
1
|ψ = N − 2 (|0|0 + |1|1 + |2|2 + |3|3 + |4|0 + |5|1 + |6|2 + |7|3
1

N−1
= N− 2 | j|y j ) (15.22)
j=0
where the first and second kets in a product represents the state of the x and y
registers, respectively, and |y j is defined by the first line. Because the last four states
of the y-register are the same as the first four, we have an example of a function that
is periodic in the variable defined by the values in the x-register, and this has been
created by unitary operations on a set of qubits.
The above is a simple example of the generation of a periodic function by
performing unitary operations on qubits. Moreover, we know in advance what its
periodicity is going to be. A more interesting case is where a state similar to (15.22)
is created by some other process, such that we do not know what the period is. In this
case we would expect to be able to determine its period by subjecting it to a Fourier
transform: this will have maxima corresponding to its fundamental frequency and/or
some or all of its harmonics. It turns out that this period can be found very efficiently
by a quantum computation as we shall now explain.
Worked Example 15.2 If the y register contains a single qubit, explain how to construct a
state similar to (15.22), but with period 2.
Solution We first place the qubit in state α, then subject it to a controlled NOT, where the
control bit is qubit 3 of the x register. This produces the state
|ψ = N − 2 (|0|0 + |1|1 + |2|0 + |3|1 + |4|0 + |5|1 + |6|0 + |7|1

1
so the state of the y register has period 2 as required.
The quantum Fourier transform

Classically, the Fourier transform ỹk of a function y j can be written as

N−1
− 12 2πi
ỹk = N exp jk y j (15.23)
j=0
N
where the functions ỹk and y j are evaluated at the points k = 0, 1...(N − 1) and
j = 0, 1...(N − 1), respectively. We note that this expression is generally applicable,
provided the spaces spanned by j and k are appropriately scaled. It is convenient to
assume that N = 2n where n is an integer and we shall do so from now on. If y j is
periodic with period r and N/r = m where m is an integer, (15.23) becomes

m−1 r−1
− 12 2πi
ỹk =N exp k( j + lr) y j+lr
l=0 j=0
N

m−1 r−1
− 12 2πi 2πi
=N exp klr exp jk y j
l=0
N j=0
N
⎡ ⎤ r−1
⎢⎢⎢ 1 − exp (2πik)) ⎥⎥⎥ 2πi
− 2 ⎢⎢
1
⎥
=N ⎢⎣ ⎥⎥⎦ exp jk y j (15.24)
1 − exp 2πik j=0
N
m
where the expression in square brackets equals the sum over l in the line above
because the latter is a geometric series. Unless k = pm, where p is an integer ≤ r,
this term equals zero, because the numerator is zero and the denominator is finite.
However, if k = pm both are zero and their ratio equals m. If N/r is not an integer,
these statements are true to a good approximation provided N >> r. It follows that the
period r can be determined from the positions of the peaks in the Fourier transform.
Classical “fast Fourier transform” methods have been developed that allow this
calculation to be performed with considerable efficiency, but this could be greatly
exceeded by a quantum calculation as we shall see.
Consider the quantum transformation

N−1
− 12 2πi
| j → N exp jk |k (15.25)
k=0
N
where each of | j and |k describe the states of N qubits. If |ψ represents the state of
two registers entangled as in (15.22) and we apply the transformation (15.25) to the
x-register only, we get
1

N−1
|ψ = N − 2 | j|y j
j=0
⎛ ⎞⎟
⎜
N−1
⎜⎜⎜ − 1 N−1 2πi ⎟⎟
→N − 12 ⎜⎜⎝N 2 exp jk |k⎟⎟⎟⎠ |y j
j=0 k=0
N
⎛ ⎞⎟
⎜⎜⎜ 1 N−1
N−1 2πi ⎟⎟⎟
⎜⎜⎜⎜N − 2 ⎟⎟⎟ |k
1
= N− 2 ⎝ exp jk |y j ⎠
k=0
N j=0

N−1
= |ỹk |k (15.26)
k=0
where

N−1
−1 2πi
|ỹk = N exp jk |y j (15.27)
j=0
N
|ỹk represents the state of the qubits in the y register, which are now entangled
with the transformed states, |k, of the x-register. We note that each |ỹk is a linear
combination of n products of the spin eigenfunctions, while |k is a single product
that represents the number k. Comparing (15.27) with (15.23), we see that |ỹk is a
representation of the Fourier transform of |y j . We can also use the fact that y j is
periodic so that |y j+r = |y j to follow a similar procedure as we did for the classical
case above and write (15.27) as
⎡ ⎤ r−1
⎢⎢⎢ 1 − exp (2πik) ⎥⎥⎥ 2πi
−1 ⎢⎢ ⎥
|ỹk = N ⎢⎣ ⎥⎥⎦ exp jk |y j (15.28)
1 − exp 2πik j=0
N
m
We may now think that we have calculated the whole Fourier transform of |y j in a
single operation. However, as is the case for all quantum computations, only a small
part of the outcome can be extracted by a single measurement. Suppose we were to
attempt to measure the state of the y-register by measuring the z components of its
component atoms; this would cause the state to collapse into a single product of spin
eigenfunctions, which would give us little or no information about the previous state
of the y-register. Remembering that the single piece of information we are seeking
is the period, r, of the function yk , we shall show that this can be obtained, not by
operating on |ỹk , but by measuring the state of the x-register, which contains the
values of k. The probability of obtaining a particular value of k following such a
measurement is |k|ψ|2 = ỹk |ỹk , using (15.26). Referring to (15.28) we see that the
term in square brackets is zero unless k = pm, where p is an integer, in which case it
equals m, so that

m2
r−1 r−1
2πi
ỹk |ỹk = 2 exp ( j − j )k y j |y j
N j=0 j =0 N
m2 r
=
N2
1
= (15.29)
r
remembering that N = mr and that the |y j are orthonormal. We note that the
probabilities are all equal and they sum to unity, because there are r maxima less
than N in the Fourier transform. We also note that this result is exact only if r is a
submultiple of N, but is a good approximation in the general case, provided N >> r.
Thus, a measurement of k is almost certain to yield a value equal to a multiple of N/r.
To obtain r itself, we would have to repeat the procedure a number of times and look
for the lowest common multiple of the measured values of N/k. Alternatively, we
could test each result we obtain against the original data as this often involves a very
short conventional calculation: for example, if the quantum Fourier transform is used
to determine prime factors, their correctness can be tested by a single multiplication.
We note that once the entangled state representing the periodic function has been
established, all subsequent transformations and measurements, which actually lead
to a value of the period of the function represented by the y-register, are carried on
the x-register only.
We illustrate the above by considering the particular case defined in (15.22);
using (15.26) and (15.27) we see that the wave function |ψ can be written as the
sum of the following eight terms:

⎫
|ỹ0 |0 = (1/4)(α4 α5 + α4 β5 + β4 α5 + β4 β5 )α1 α2 α3 ⎪ ⎪
⎪
⎪
⎪
⎪
|ỹ1 |1 = 0 ⎪
⎪
⎪
⎪
⎪
⎪
|ỹ2 |2 = (1/4)(α4 α5 + iα4 β5 − β4 α5 − iβ4 β5 )α1 β2 α3 ⎪
⎪
⎪
⎪
⎪
⎪
⎪
|ỹ3 |3 = 0 ⎪
⎪
⎬
⎪ (15.30)
|ỹ4 |4 = (1/4)(α4 α5 − α4 β5 + β4 α5 − β4 β5 )β1 α2 α3 ⎪ ⎪
⎪
⎪
⎪
⎪
⎪
|ỹ5 |5 = 0 ⎪
⎪
⎪
⎪
⎪
⎪
|ỹ6 |6 = (1/4)(α4 α5 − iα4 β5 − β4 α5 + iβ4 β5 )β1 β2 α3 ⎪
⎪
⎪
⎪
⎪
⎪
⎪
|ỹ7 |7 = 0 ⎭
where we have represented |k by products of the spin states α and β, which represent
0 and 1 respectively. Because |y j = |y j+4 , the contributions from these terms to
|ỹk |k have doubled up in the case where k is even and cancelled out when k is odd.
The probability of obtaining one of the allowed values of k is proportional to ỹk |ỹk
and equals 0.25 in all cases. When we measure the x-register we therefore obtain a
value of k equal to 0, 2, 4 or 6. If we get zero, we get no information, but otherwise
we can deduce that r = 4, 2 or 4/3. Repeating the whole calculation a small number
of times is very likely to lead us to conclude that r = 4.
We now describe in a little more detail how, in principle, the quantum Fourier
transform (15.25) could be carried out. We first write the number k in its binary form
n
l=1 kl 2 , where kl = 0 or 1. Substituting into (15.25) we get
n−l
⎛ ⎞

1
1
1 ⎜⎜⎜ 2πi
n ⎟⎟⎟
| j → 2−n/2 ... exp ⎜⎜⎜⎝ n j kl 2n−l ⎟⎟⎟⎠ |k1 |k2 ..|kn
k1 =0 k2 =0 k =0
2 l=1
n

n
1
= 2−n/2 exp 2πi jkl 2−l |kl
l=1 kl =0

n
= 2−n/2 αl + exp 2πi j2−l βl (15.31)
l=1
where, in the last line, we have again replaced |0 and |1 by the corresponding spin
states αl and βl . We now write j in its expanded binary form, so that the exponent in
(15.31) can be written as

n
−l
2πi j2 = 2πi jm 2n−m−l (15.32)
m=0
where jm = 0 or 1. We substitute (15.32) into (15.31) dropping all terms with m ≤ n−l
in the above summation because the exponential of 2πi times an integer equals one.
This yields
⎡ ⎛ ⎞ ⎤

n ⎢
⎢ ⎜
⎜
n ⎟⎟ ⎥⎥⎥
⎢⎢⎢ ⎜⎜⎜ n−m−l ⎟⎟⎟⎟ βl ⎥⎥⎥
| j → 2−n/2 α
⎣⎢ l + exp ⎝⎜2πi j m 2 ⎠ ⎦ (15.33)
l=1 m=n−l+1
>
| j1 H R2 R3 C C
>
| j2 H R2
>
| j3 H C
FIGURE 15.4 Quantum Fourier transform. The boxes labelled H represent Hadamard
gates that perform a π/2 rotation of spin about the y axis. The boxes labelled R2 and
R3 rotate the spin about the z axis so as to introduce phase changes of π/2 and π/4,
respectively if the relevant control bit equals 1. The three boxes labelled C are CNOT
gates, whose combined effect is to swap the states of qubits 1 and 3.
Our earlier example treated the case where the x register contained three qubits in
which case (15.33) can be written as

| j →2−3/2 α1 + exp (iπ j3 ) β1 α2 + exp (i ( j2 π + j3 π/2)) β2

× α3 + exp (i ( j1 π + j2 π/2 + j3 π/4)) β3 (15.34)
We see, therefore, that the transformation (15.25) can be effected by changing

the phase of each β by an amount specified in (15.34) and leaving the phases of the
αs unchanged. This can be achieved using a “controlled phase gate” by which we
mean one that applies a specified phase change to a target bit if and only if the value
of the control bit equals one. Referring again to Chapter 11, we see from (11.14) that
the application of a magnetic field parallel to z for a time t changes the relative phase
of β and α by ω p t and, because the overall phase of the wave function is arbitrary,
we can attribute all of this phase change to β. In principle, therefore, we can generate
the desired phase change by applying the field created by the control bit to the target
bit for a given time. (NB: we should also apply an external field adjusted to cancel
out the control field when the control bit is zero—cf. the earlier discussion of the
controlled NOT gate).
Hopefully this will all become clearer when we discuss the particular example
illustrated in figure 15.4, which represents the effect of applying several spin
rotations to a 3-qubit number. We start by considering the effect of the operations
on the first qubit whose initial state is | j1 . The first Hadamard gate, H, rotates the
1
spin through π/2 about the y axis to produce the state, 2− 2 (α1 ± β1 ), the sign being
plus or minus depending on whether | j1 is α1 or β1 respectively. The following
operation R2 applies a field parallel to z so as to change the phase of β1 by π/2 if and
only if j2 = 1; R3 changes the phase by π/4 if and only if j3 = 1. The state of | j1 has
therefore now become

α1 + exp i ( j1 π + j2 π/2 + j3 π/4) β1
The qubit | j2 is operated on by the Hadamard gate H and by R2 and changes in a
similar way to become

α2 + exp i ( j2 π + j3 π/2) β2
while | j3 is operated on only by H to become

α3 + exp i ( j3 π) β2
If we compare the above expressions with (15.34), we see that these gates have
created a state of the three qubits similar to the one we were aiming at, but with
the labels 1 and 3 interchanged. The states of these qubits are then swapped by the
operation of the three CNOT gates shown in figure 15.4 to produce the state (15.34).
The total number of operations involved in a quantum Fourier transform is easily
estimated. Referring to figure 15.4, we see that the first qubit is subject to one H
followed by (n − 1) R2 ’s, the second to one H plus (n − 2) R2 ’s, and so on. There are
then about n/2 swap gates making a total number of around n2 operations. This is
in contrast to the fastest classical computation, which involves 2n n operations. The
potential gain is huge for large values of n (faster by a factor of about 5 × 104 if n = 20
and 2 × 1013 for n = 50) and this has motivated the considerable scientific effort that
has been devoted to the possible realization of such a quantum calculation.
As we stressed from the beginning our discussion has been confined to how “in
principle” a quantum Fourier transform could be carried out, but we now briefly
turn to what might be possible in practice. The practical problems involved in using
the spins associated with single atoms are formidable, but some progress has been
made using liquids made up of molecules that contain atoms with unpaired nuclear
spins. When a magnetic field is applied to such a liquid, the nuclear spins tend to
line up parallel to it to create a macroscopic magnetic moment. If a radio frequency
field tuned to the energy difference between the parallel and antiparallel nuclear
spin states is applied, this magnetic moment can be rotated. This process, which
is known as nuclear magnetic resonance (NMR), allows the magnetic moment to be
treated as a qubit much as described above. As the nuclei contained in the molecules
making up the liquid have different resonant frequencies, they can be manipulated
independently, and it is also possible to arrange for them to interact in such a way
as to create a CNOT and other quantum gates. Because the states are represented
by macroscopically sized spins, they are not collapsed by a measurement in the way
described earlier and this part of the calculation has to be performed in a different
way. Indeed, it can be argued that a calculation based on NMR is closer to a many-
dimensional classical analogue calculation than to a true quantum calculation. Using
NMR techniques, a quantum calculation based on seven qubits has been carried out
to implement Shor’s algorithm for the factorization of a number into its prime factors.
This involved generating a four-qubit periodic function, finding that its period is four
and deducing that the factors of the number fifteen are five and three! However,
although NMR has provided a robust realization of a quantum computation, seven is
probably close to the maximum number of qubits that can be employed in this way.
This is because each qubit is identified with the resonance of a particular nucleus in
the molecule and the number of these is equal to the number of different nuclear sites
in the molecule. If molecules with a larger variety of spins were used, their resonant
frequencies could be too close to each other to allow them to be distinguished by
an applied field—unless this is applied for a time greater than the inverse of the
frequency difference, in which case the process is slowed to the point where its
advantage is lost.
This example illustrates the enormous potential power of the quantum computer,
the essential feature being the almost miraculous way in which a superposition of the
results of n calculations can be generated by a single operation. The measurement
process limits the amount of this information we can retrieve, but in appropriate cases
very powerful results can be achieved. We should, however, remember the immense
obstacles that lie in the way of any practical application of these ideas. Although
entangled states of two particles can be generated almost routinely, extending this to
more than a few is difficult, and a hundred or so really seems impossible. However,
there are many examples in the past of the seemingly impossible being achieved and
we should beware of underestimating human technological capacity. Whether more
“in principle” objections may arise if and when we understand the measurement
process better will be speculated on in the next chapter.
15.5 PROBLEMS
15.1 Construct a variant of Table 15.1 in which Eve makes different guesses about the settings of Alice’s
apparatus.
15.2 Confirm that the state defined by Equation (15.5) is the same as that given in (15.4)
15.3 Verify the equivalence of equations (15.12) and (15.13).
15.4 Describe the operation of a quantum Fourier transform on the system described in worked example
12.3 and explain how it can be used to obtain the period of this function.
2
QUANTUM COMPUTERS
This chapter is excerpted from

Quantum Mechanics II, Advanced Topics
by S. Rajasekar, R. Velusamy
© 2015 Taylor & Francis Group. All rights reserved.
Learn more
CHAPTER 7
Quantum Computers
7.1 INTRODUCTION
Present day computers perform computations using two-state binary logic.
They led to an amazing revolution in data manipulation and processing. The
components of a computer are subject to various laws of physics. What will
happen if the components of a computer become very small such that they are
subjected to the principles of quantum mechanics? Alternatively, can a real
quantum system be used to build a computer functioning in the quantum
mechanical regime? This is one of the major issues in quantum computing.
The name quantum computing refers to calculations using logic based on the
probability amplitude concept.
Classical computers of the present decade are able to answer one question
at a time. In contrast a quantum computer will have the ability to carry out
more than one problem simultaneously. Essentially quantum computers ma-
nipulate quantum states instead of classical bits. In a quantum computer the
eigenstates of, for example, a two-level system are renamed 0 and 1. Now, the
two level quantum system becomes a qubit (that is, quantum binary digit)
[1-4]. The concept of the quantum computer was introduced first by Paul Be-
nioff (1980) [5]. Richard Feynman [6,7] contributed to the early development of
quantum computation. The first paper on quantum computing was published
by David Deutsch [8] in the year 1985.
During the past one decade or so, many quantum algorithms have emerged.
Among them the most remarkable successes of quantum computation are
Shor’s efficient algorithms for integer factorization and the computation of
discrete logarithms [9,10]. Peter Williston Shor has shown that quantum com-
puters would solve the problem of finding discrete logarithms (mod N ). He
predicted that a quantum computer can perform prime factoring in polynomial
time: t ∝ k p where p is a constant and k is the number of bits in the number
1/3
to be factored. For this problem a classical computer is believed to take eck
time where c is a constant. Shor’s breakthrough created an avalanche of re-
search activity in quantum computation and quantum information theory. In
161
162 Quantum Mechanics II: Advanced Topics
addition to Shor’s factorization algorithm, Deutsch–(Richard)Jozsa algorithm

[8,11] and Lov Kumar Grover’s rapid search algorithm [12] are capable of per-
forming certain computational tasks exponentially faster compared to their
classical counterparts. In the present chapter we discuss the basic aspects of
quantum computing.
7.2 WHAT IS A QUANTUM COMPUTER?

In a classical information theory ‘bit’ is an indivisible unit. It takes the values
such as yes or no, true or false or simply 0 or 1. A sequence of bits is used
to represent classical information. In a classical computer, logical gates are
employed to evaluate Boolean functions of a set of input bits.
7.2.1 Qubits
Quantum information can be represented by the elementary units called quan-
tum bits abbreviated as qubits or qbits. A qubit is two levels of a quantum
system (like the spin of an electron). For example, spin-up, | ↑, represents 1
(true) and spin-down, | ↓, represents 0 (false). Note that | ↑ to | ↓ can be
achieved by a magnetic field and dissipates no heat. All information can be
encoded into a sequence of qubits. In principle, any two-state system can be
used as a quantum bit. Some examples are presented in table 7.1.
What is the difference between a classical bit and a qubit? A qubit can
be in a state other than |0 and |1. It is possible to form a combination
of states
called
states given by |ψ = α|0 + β|1. Denoting
superposition
1 0
|0 = and |1 = the quantum state |ψ is written in vector
0 1
α
notation as . For example, we can represent the spin of an electron
β
TABLE 7.1 Examples of two-state quantum systems. Here |V , |H, |L

and |R represent vertical, horizontal, left-circular and right-circular
polarizations respectively. |+ and |− denote spin-up and spin-down
respectively. |E0 and |E1 represent ground and excited states respec-
tively.
S.No. |0 |1 Qubit
1. |V |H Photon – Linear polarization

2. |L |R Photon – Circular polarization
3. |+ |− Electron, nucleus – Spin
4. |E0 |E1 Atoms, quantum dots – Energy levels
Quantum Computers 163
in the horizontal direction as the sum of the up and down states. When we
measure a qubit, the result will be either 0 with probability |α|2 or 1 with
probability |β|2 . Hence, |α|2 + |β|2 = 1. A classical bit has either 0 state or 1
state whereas a qubit can exist between |0 and |1 until it is observed.

1
|ψ1 ⊗ |ψ2 denotes tensor product of |ψ1 and |ψ2 . If |ψ1 = and
2i

2
|ψ2 = then
3
⎡ ⎤ ⎡ ⎤
1 × 2 2
1 2 ⎢ 1×3 ⎥ ⎢ 3 ⎥
|ψ1 ⊗ |ψ2 = ⊗ =⎢ ⎥ ⎢
⎣ 2i × 2 ⎦ = ⎣ 4i ⎦ .
⎥ (7.1)
2i 3
2i × 3 6i
If |ψ1 = a|0 + b|1 and |ψ2 = c|0 + d|1 then
|ψ1 ⊗ |ψ2 = |ψ1 ψ2

= ac|0|0 + ad|0|1 + bc|1|0 + bd|1|1
= ac|00 + ad|01 + bc|10 + bd|11. (7.2)
Multiple bits have more states. With two classical bits 0 and 1 there are
four possible states 00, 01, 10, 11. But a general two qubit system can be
represented by
|ψ = α00 |00 + α01 |01 + α10 |10 + α11 |11 (7.3)

with |αx |2 = 1 where x = 00, 01, 10, 11.

As infinite range of values of α and β are possible with |α|2 + |β|2 = 1, in
principle a qubit can store an infinite amount of data. But this is misleading
because a measurement of the qubit changes its state to yield either 0 or 1.
Measurement collapses the state of qubit from the superposition of |0 and |1
to |0 with a probability |α|2 or |1 with probability |β|2 . So, from a measure-
ment we can obtain only a single bit of information about the qubit’s state.
Only if infinitely many identical qubits are prepared and then measurements
are performed we can determine α and β. As no quantum state can be copied
because such an act will lead to the collapse of the superposition state into
one of its constituent state, it is impossible to set-up identical states. Hence, in
principle, it is impossible to find α and β exactly. The information contained
in a qubit is enormous if we do not measure it. That is, nature conceals a
great deal of information. This hidden quantum information falls at the cen-
ter of what makes quantum mechanics a powerful modern emerging tool for
information processing.
Solved Problem 1:
Write the Pauli matrices σx , σy and σz in operator form and state their effect
on a qubit.

1
Defining |0 = and 0| = 1 0 one can find |00| as
0

1 1 0
|00| = 1 0 = . (7.4)
0 0 0
Then
σx = |01| + |10|, (7.5)

σy = −i|01| + i|10|, (7.6)
σz = |00| − |11|. (7.7)
The action of the Pauli matrices σx and σz on a qubit is
σx |0 = |1, σx |1 = |0, (7.8)

σz |0 = |0, σz |1 = −|1. (7.9)
We note that σx gives rise to bit flip while σz causes phase flip. What is the
effect of σy ?
7.2.2 Quantum Gates

An elementary quantum logic gate is a unitary transformation. A quantum
gate acts on a qubit or pair of qubits. Quantum gates are represented by
matrices or operators. Any unitary matrix can specify a valid gate. We can
represent them in Dirac notation also. In quantum computers a unitary trans-
formation is applied to a given initial state of a set of qubits through several
quantum gates. The final outcome of a quantum computation is contained in
the final state of the qubits.
There are certain major differences between classical and quantum gates.
1. Fan-in1 is not possible in quantum circuits.
2. In classical circuits wires are joined together to form a single wire. In

quantum circuits this irreversible operation is not possible.
3. Fan-out2 is also not possible. That is, making a number of copies of a
bit is not possible.
4. Quantum gates do not permit feedback loops from one part of the circuit
to another part.
1A term defining the maximum number of digital inputs allowed by a logic gate.
2 It defines the maximum number of digital inputs that the output of logic gates can
feed.
7.2.3 Quantum Computer

Quantum computation is defined as an arbitrary transformation on a Hilbert
space spanned by the complete set of all possible states of bits. The differ-
ence between quantum computers and a system of interacting spins is that
the computation must be modular, each logical operation considers only a
few spins. Essentially, quantum computers will perform computations at the
atomic scale.
In a quantum computer, the execution of a program can be thought of as a
dynamical process and is governed by the Schrödinger equation. Consequently,
a state vector ψ is used to describe the state of the computer. Here ψ is a
linear superposition of all the binary states of the bits xm ∈ {0, 1}:

ψ(t) = αx |x1 , x2 , · · · , xm , |αx |2 = 1 . (7.10)
xm ∈{0,1} x
The time evolution of the state is governed by a unitary operator U on a

vector space.
7.3 WHY IS A QUANTUM COMPUTER?

Anything a quantum computer can perform can also be done in a classical
computer. Then, why should one think of a quantum computer? In the follow-
ing we list some of the difficulties with classical computers and the advantages
of quantum computers.
1. A quantum computer is very efficient over a classical computer.
Example 1:
Consider a quantum state of a modest number of qubits, for example 100
lines in a Hilbert space of dimensions 2100 ∼ 1030 . To perform a compu-
tation a classical computer has to work with matrices of exponentially
large size and this would take a very long time.
Example 2:
A single computation acting on say, 300 qubits can achieve the same
effect as 2300 computations acting simultaneously on classical bits.
Example 3:
To factor a 400 digit number, a powerful workstation would require
about 10 years. But a quantum computer could complete the same task
in just a few minutes.
2. There are a number of problems for which the underlying process can be
sped-up tremendously through quantum algorithms. Consider a number
N of L digits so that N ≈ 10L . To determine its factors, in the least case,
√ √
it is required to divide N by numbers up to N . That is N ∼ 10L/2
operations are essential. Hence, the number of operations would increase
with L exponentially. The best known classical algorithm requires s =
1/3 2/3
Ae1.9L (log L) (A is a constant) number of operations for factorizing
an L digit number. Therefore, it is not considered an efficient algorithm.
To factorize a 130 digit number at the rate of ∼ 1012 operations per
second, a classical computer would require ∼ 42 days. It would require
∼ 10 years for a 400 digit number. However, a quantum algorithm of
Peter Williston Shor requires time ∝ L3 .
3. Computations cannot be reversible in a classical computer (why can’t a
computer run backwards?). In quantum theory, reverse time evolution
is specified by the unitary operator U −1 = U † . A consequence of this is
that computations can be reversible in a quantum computer.
4. Calculations in a classical computer lead to dissipation in order to damp
out an attempt by the system to make a transition. In contrast, in a
quantum computer dissipation cannot be used and further the accuracy
of a computation is built-in.
5. In a classical computer errors in the initial data may grow exponentially
with the number of steps involved. This is because, the classical dy-
namics involves the symplectic group that is noncompact. In quantum
mechanics, inaccuracies in the initial data do not grow. This is because
it uses the compact unitary group.
7.4 FUNDAMENTAL PROPERTIES

In the following we discuss the fundamental properties of quantum systems
that are relevant to information processing.
7.4.1 Software, Hardware and CPU [1,13]

Superposition:
A quantum computer can exist in an arbitrary linear combination of clas-
sical Boolean states. These states evolve in parallel as per a unitary transfor-
mation.
Interference:
Parallel computation paths in the superposition, like a particle’s path
through an interferometer, can cancel one another or reinforce depending on
their relative phase.
Entanglement:
Certain states of a complete quantum system do not form definite states
of its parts. For more details see sec.10.2.
Nonlocality and uncertainty:

An unknown quantum state cannot be copied (cloned) accurately. It cannot
be observed without being disturbed.
A quantum computer has a register with n qubits. A qubit has 0 and
1 classical states so that the register has 2n classical states. The state of a
quantum computer is described by a 2n -dimensional vector, x, indexed by i =
000 · · · 00, 000 · · · 01, 000 · · · 10, · · · , 111 · · · 11 in binary notation. Moreover,

2
||x|| = |xj |2 = 1 (7.11)
j
and |xj |2 is the probability that the register is in state j. We call x the wave
function (ψ) of the register.
In a quantum computer, the software is represented by ψ and the hardware
by a Hamiltonian. The Hamiltonian describes the dynamics of the central
processing unit (CPU). The hardware generates a unitary evolution of ψ(t)
representing the state of the software at time t. The software is a finite string
of bits with a logical meaning. It includes the inputs (such as programs and
data), the output and a scratch pad necessary to store intermediate results.
The states, for example, | ↓ and | ↑ represent a bit with logical values 0 and
1 respectively.
7.4.2 Two-Bit Gates for Universal Computation

In a classical computer logic gates are used to process information. David
Deutsch has shown a way to obtain a universal quantum computation. Tom-
maso Toffoli [14] showed how the AND and XOR gates can be implemented
reversibly. Recall that conventional AND and XOR gates are not reversible
because a reversible gate must contain the same number of input and output
bits. However, XOR can be implemented reversibly with a two-bit gate where
one output bit may return the conventional XOR. ⊕ is used to denote for the
exclusive-or operation. a1 ⊕ a2 (a1 and a2 are the binary values of the two
input bits) is given by a one output bit, while the second output bit returns
the original value of a1 (or a2 ). To implement AND reversibly, a three-bit gate
is used where a1 and a2 are passed through unchanged and the third bit is
XORed with the AND of the first two, returning (a1 · a2 ) ⊕ a3 . Because this
three-bit gate has both the XOR and the AND functions, it can be considered
as a universal reversible gate. This gate is called Toffoli gate.
7.4.3 NOT, Z and Hadamard Gates

A simple classical gate is the NOT gate that changes 0 to 1 and 1 to 0. An
analogous quantum NOT gate transforms states in a particular basis into
TABLE 7.2 The truth table of the quantum NOT gate.

Input Output
|0 |1
|1 |0
α|0 + β|1 α|1 + β|0
states orthogonal to them. The unitary operation UNOT is given by
UNOT |0 = |1 , (7.12a)

UNOT |1 = |0 . (7.12b)
Unlike the digital gates, the quantum gates are assumed to act on superposi-
tion states. The UNOT provides the transformation
UNOT (α|0 + β|1) = α|1 + β|0 . (7.13)
Here α and β are the amplitudes of the states. If we represent |0 and |1 in
column matrix then the output of the NOT gate is

α 0 1 α β
X = = . (7.14)
β 1 0 β α
The truth table of the quantum NOT gate is given in the table 7.2.
In classical gates, the NOT gate is the only nontrivial single-bit gate. In
quantum mechanics there are many nontrivial qubit gates with |α|2 +|β|2 = 1.
Examples are the Z gate and Hadamard (H) gate. They are given by

1 0 1 1 1
Z= , H= √ . (7.15)
0 −1 2 1 −1
These gates are very useful. The truth table of them are given in tables 7.3 and
7.4 respectively. These gates are represented pictorially as shown in Fig. 7.1.
Consider the Hadamard transformation given by

1 1 1 1 1 1 1
H= √ , H =√ = √ (|0 + |1),
2 1 −1 0 2 1 2

0 1 1 1
H =√ = √ (|0 − |1). (7.16)
1 2 −1 2
It acts on a single qubit. Its effect is to rotate the state about the y-axis.
Interestingly, there are infinitely many 2 × 2 unitary matrices and so in-
finitely many qubit gates. Remember that the classical gate NOT gate is the
TABLE 7.3 The truth table of the quantum Z gate.

Input Output
|0 |0
|1 −|1
α|0 + β|1 α|0 − β|1
TABLE 7.4 The truth table of the Hadamard gate.

Input Output
1
|0 √ (|0 + |1)
2
1
|1 √ (|0 − |1)
2
1
√ (|0 + |1) |0
2
1
√ (|0 − |1) |1
2
1 1
α|0 + β|1 √ (α + β)|0 + √ (α − β)|1
2 2
α | 0 > + β | 1> X α |1 > + β |0 >
α | 0 > + β | 1> Z α |0 > β |1 >
α | 0 > + β | 1> α
H ( |0 > + |1>)
2
β
+ ( |0 > | 1>)
2
FIGURE 7.1 Qubit logic gates.

single one-bit. Any single qubit unitary gate can be decomposed as

−iβ/2
iα e 0 cos(γ/2) − sin(γ/2)
U = e
0 eiβ/2 sin(γ/2) cos(γ/2)
−iδ/2
e 0
× , (7.17)
0 eiδ/2
where α, β, γ and δ are real numbers. In fact, one can build-up a qubit gate
using a finite set of quantum gates called universal gates.
Solved Problem 2:
If X, H and Z denote the quantum NOT, Hadamard and Z gates respectively,
show that HXH = Z.
We obtain

1 1 1 0 1 1 1 1
HXH = √ √
2 1 −1 1 0 2 1 −1

1 1 1 1 1
=
2 −1 1 1 −1

1 0
=
0 −1
= Z. (7.18)
7.4.4 CNOT (XOR) and Toffoli Gates

CNOT stands for controlled NOT. It is a two qubit gate that modifies the
state of one of the qubits depending on the state of the other control qubit.
The effect of CNOT on the target state is shown in table 7.5. In this table if
we treat the first two columns as the input and third as the output then this
table is the truth table of classical XOR gate.
In operator form CNOT is
CNOT = |0000| + |0101| + |1011| + |1110| . (7.19)
TABLE 7.5 The truth table of the quantum CNOT gate.

Control Target Final
initial
0 0 0
0 1 1
1 0 1
1 1 0
TABLE 7.6 The truth table of Toffoli gate.

Inputs Outputs
a b c a b c
0 0 0 0 0 0
0 0 1 0 0 1
0 1 0 0 1 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 1 1 0 1
1 1 0 1 1 1
1 1 1 1 1 0
The first qubit is the control and the target is the second qubit. The first
two terms in Eq. (7.19) indicates that if the control qubit is in the state |0
then the target state remains the same. The target state is changed when the
control state is |1. The last two terms in Eq. (7.19) represent these. Because
the state of the second qubit is dependent on the first qubit’s state, the two
qubits become entangled on passing through the CNOT gate. Combination
of the CNOT and the Hadamard gates can be used to realize both quantum
superposition and entanglement. We notice that the control and the target
qubits are XORed and stored in the target qubit. The matrix representation
of the CNOT operation is given by
⎛ ⎞ ⎛ ⎞⎛ ⎞
|00 1 0 0 0 |00
⎜ |01 ⎟ ⎜ 0 1 0 0 ⎟ ⎜ |01 ⎟
UNOT ⎜ ⎟ ⎜ ⎟⎜ ⎟
⎝ |10 ⎠ = ⎝ 0 0 0 1 ⎠ ⎝ |10 ⎠ . (7.20)
|11 0 0 1 0 |11
A reversible quantum gate is Toffoli gate. It has three input bits, say a, b
and c and three outputs a , b and c . The truth table of Toffoli gate is given in
table 7.6. a and b are treated as control bits and are unaffected by the target
bit c. But c is inverted if both a and b are 1.
Solved Problem 3:
√
Given |ψ = α|0 + β|1 and an EPR pair (|00 + |11) / 2 find the state of
the complete system and the effect of CNOT on it.
We obtain

1 1 u1
√ [α|0 (|00 + |11) + β|1 (|00 + |11)] = √ , (7.21a)
2 2 u2
where
⎛ ⎞ ⎛ ⎞
α β
⎜0⎟ ⎜0⎟
u1 = ⎜ ⎟
⎝0⎠ , u2 = ⎜ ⎟
⎝0⎠ . (7.21b)
α β
Performing CNOT we get
⎛ ⎞
0
1 1 u1 ⎜β ⎟
√ [α|0 (|00 + |11) + β|1 (|10 + |01)] = √ , u3 = ⎜ ⎟
⎝β ⎠ .
2 2 u3
0
(7.22)
7.4.5 Symbols for Quantum Circuits

The schematic symbols used to denote some unitary operations in quantum
circuits are given in Fig. 7.2 with their matrix representations. The connections
are represented by the symbols shown in Fig. 7.3. If a gate U acts on an n-
qubit, we depict it as in Fig. 7.4.
By a measurement on the n-qubit register of a quantum computer, we
mean measuring the observable
n
2 −1
x= i|ii| (7.23)
i=0
and it is represented in circuits by the ammeter symbol as in Fig. 7.4. In a

measurement we get two quantities, a collapsed state |k and its probability
|k|U |ψ|2 , and hence it is indicated by a double-line in Fig. 7.4.
Solved Problem 4:
Find the output state |ψ1 of the circuit given in Fig. 7.5 for the input state
|ψ0 = α|0 + β|1.
We have

1 0 0 1
Z= , X= (7.24)
0 −1 1 0
and

1 0 α
|ψ0 = α|0 + β|1 = α +β = . (7.25)
0 1 β
Further,

1 0 α α
Z|ψ0 = = = α|0 − β|1 . (7.26)
0 −1 β −β
(i) NOT 1 0 0 0
a x b 0 0 1 0
0 1 0 0
b x a 0 0 0 1
(ii) Controlled-NOT 1 0 0 0
a a 0 1 0 0
0 0 0 1
b + b +a 0 0 1 0
(iii) Toffoli 1 0 0 0 0 0 0 0
a a 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
b b 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
c + c + ab 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0
FIGURE 7.2 Circuit symbols and matrix representations of logic gates.
(i) Measurement Projection on to a basis
(ii) Qubit Wire carrying a simple

qubit
(iii) Classical bit Wire carrying a simple

classical bit
n
(iv) n qubits Wire carrying n qubits
FIGURE 7.3 Symbols for connections in quantum circuits.
n ψ U ψ
U
FIGURE 7.4 A quantum circuit.

ψ0 ψ1
Z X
FIGURE 7.5 A quantum circuit with Z and X gates.
Then

0 1 α −β
|ψ1 = XZ|ψ0 = = = α|1 − β|0 . (7.27)
1 0 −β α
7.4.6 Evaluation of Functions

Let us describe the calculation of functions by quantum computers. Consider
a function
f : {0, 1, · · · , 2m − 1} → {0, 1, · · · 2n − 1} , (7.28)
where m and n are positive integers. A classical computer calculates f by
evolving the inputs 0, 1, · · · , 2m − 1 into the outputs f (0), f (1), · · · , f (2m − 1).
Quantum computers use two registers. Input is stored in the first register and
the second is for output. The quantum state of the first register is represented
as |x. Output may be represented by |y. The function evaluation is computed
by a unitary evolution operator Uf that acts on the two registers, that is,
Uf |x|0 = |x|f (x) = |x, f (x) , (7.29)
where the output is initially set to 0. The values of f (0), · · · , f (2m − 1) found
by applying Uf only once to a superposition of all input as
2m −1

1
|ψ = Uf |x |0
2m/2 x=0
m
2 −1
1
= |x|f (x) . (7.30)
2m/2 x=0
7.5 QUANTUM ALGORITHMS

One can simulate a classical circuit using a quantum circuit. That is, it is
possible to perform classical computations on quantum computers. But the
advantage of quantum computing is that powerful functions may be computed
by making use of quantum parallelism the fundamental feature of many quan-
tum algorithms. It allows a quantum computer to evaluate f (x) for many
different values of x simultaneously. This parallelism is not immediately use-
ful because a measurement would give f (x) for a single value of x only as in
the case of a classical computer.
Quantum computation needs much more than that quantum parallelism

to be useful. This is achieved in Deutsch’s algorithm [8,15] which combines
quantum parallelism with interference. Using Deutsch’s algorithm, informa-
tion about a f (x) can be obtained very quickly compared with a classical
computer. Deutsch’s algorithm is a simple case of a more general Deutsch–
Jozsa algorithm [11]. It suggests that quantum computers may be capable of
solving certain problems more efficiently than classical computers.
There are three classes of quantum algorithms that provide an advantage
over classical algorithms.
1. There is the class of algorithms based on quantum Fourier transform.
Examples are the Deutsch–Jozsa algorithm of finding whether a given
function is a constant or not and the Shor’s algorithms for factoring and
discrete logarithm.
2. The second class is quantum search algorithms. Their principles were
discovered by Grover [16]. The goal of a quantum search algorithm is
given a search space of size N finding an element of that search space
having a known property.
√ A quantum search algorithm achieves this
in approximately N operations whereas a classical computer requires
about N operations.
3. Another class of quantum algorithms is quantum simulation, where a
quantum computer is explored to simulate a quantum system.
7.5.1 Deutsch’s Algorithm

The first and the simplest quantum algorithm is Deutsch’s problem. Let f (x)
denote one bit functions with x = 0 or 1. There are only four possibilities:
f1 (0) = 0, f1 (1) = 0.
f2 (0) = 0, f2 (1) = 1.
(7.31)
f3 (0) = 1, f3 (1) = 0.
f4 (0) = 1, f4 (1) = 1.
Given an unknown f the problem is to determine which one of the above four
classes it belongs to. In a classical algorithm we can calculate f (0) and f (1)
and then find its class by comparing the values of f (0) and f (1) with the
Eqs. (7.31). Therefore, we wish to evaluate f at 0 and 1. But a quantum al-
gorithm requires only one evaluation. Deutsch proposed a quantum algorithm
for the above problem which is based on the principle that the superposition
of quantum states provide the possibility to perform computation on many
states simultaneously. (The generalization of the Deutsch algorithm is the
Deutsch–Jozsa algorithm.) The algorithm consists of three steps.
Consider the operation UA
1 1
UA |0 = √ [|0 + |1] , UA |1 = √ [|0 − |1] . (7.32)
2 2
Applying n times UA to an n-bit quantum register in the state |0 we have

|ψ = UA ⊗ UA ⊗ · · · UA |000 · · · 0
1 1 1
= √ (|0 + |1) ⊗ √ (|0 + |1) ⊗ · · · √ (|0 + |1)
2 2 2
1
= n/2
[|00 · · · 0 + |00 · · · 1 + · · · + |11 · · · 1]
2
2n −1
1
= |i . (7.33)
2n/2 i=0
That is, n applications of UA yields a register state that has 2n distinct terms.
Note that in classical case n elementary operations can only give one state of
the register giving one number.
Let us start with two qubits. One bit is set to the state |0 and the other
is to the state |1. The total state is |01. In the first step we apply the gate
UA to each qubit. This gives
1 1 1
√ [ |0 + |1 ] ⊗ √ [ |0 − |1 ] = [ |00 − |01 + |10 − |11 ] . (7.34)
2 2 2
In the second step compute f on the superposition state given by Eq. (7.34).
This is realized by a two-bit gate Uf (Eq. (7.29)) acting on the basis vector
|x, y → |x, y ⊕ f (x) , x, y = 0, 1 (7.35)
where ⊕ denotes addition mod 2. The last step is to apply UA again on each
qubit.
Let us apply the above algorithm assuming f = f1 . The first step yields the
superposition state given by Eq. (7.34). (This is independent of the function.)
The second step gives

1
|ψ = Uf [ |00 − |01 + |10 − |11 ]
2
1
= [ |0, 0 ⊕ f (0) − |0, 1 ⊕ f (0) + |1, 0 ⊕ f (1) − |1, 1 ⊕ f (1) ]
2
1
= [ |00 − |01 + |10 − |11 ] . (7.36)
2
The final step is the application of UA on |ψ given by Eq. (7.36). We obtain

1 1 1 1 1
|ψ = √ (|0 + |1) √ (|0 + |1) − √ (|0 + |1) √ (|0 − |1)
2 2 2 2 2

1 1 1 1
+ √ (|0 − |1) √ (|0 + |1) − √ (|0 − |1) √ (|0 − |1)
2 2 2 2
1
= [ |00 + |01 + |10 + |11 − |00 + |01 − |10 + |11
4
+|00 + |01 − |10 − |11 − |00 + |01 + |10 − |11]
= |01 . (7.37)
If f = f2 then the second step gives

1
|ψ = [ |0, 0 ⊕ 0 − |0, 1 ⊕ 0 + |1, 0 ⊕ 1 − |1, 1 ⊕ 1 ]
2
1
= [ |00 − |01 + |11 − |10 ] . (7.38)
2
Then UA on |ψ results in
1
|ψ = [ |00 + |01 + |10 + |11 − |00 + |01 − |10 + |11
4
+|00 − |01 − |10 + |11 − |00 − |01 + |10 + |11 ]
= |11 . (7.39)
In a similar manner for f = f3 and f = f4 we obtain |ψ = −|11 and

|ψ = −|01 respectively. Therefore, the final state of the two qubits is
|01 if f = f1
|11 if f = f2
(7.40)
−|11 if f = f3
−|01 if f = f4 .
Thus, by comparing the final state of |ψ with Eq. (7.40) we can identify
whether the unknown f is f1 or f2 or f3 or f4 .
The essential features of the above quantum algorithm are:
1. The crucial elements are the superposition and linearity of quantum
mechanics. |ψ in Eq. (7.40) is computed on the superposition states
|00, |01, |10 and |11 simultaneously.
2. The final state |ψ is due to an interference of various parts of the su-
perposition.
3. If it is desired to know whether f is a constant (f = f1 or f4 ) or balanced
(f = f2 or f3 ) then it is enough to measure the final state of the first
qubit. If the first qubit is |0 then f is a constant. f is balanced if the
first qubit is |1. Notice that the algorithm does not say whether f is f1
or f4 and f2 or f3 . However, nowhere we learn about either f (0) or f (1).
We are able to find out that the f is a constant or not by computing f
once. In classical computation we must evaluate f twice before making
a decision.
The quantum circuit to implement Deutsch’s algorithm is given in Fig. 7.6.
The input state is |ψi = |01 and the output is

|0 − |1
|ψf = ±|f (0) ⊕ f (1) √ . (7.41)
2
So, by measuring the first qubit, we may determine f (0) ⊕ f (1) and hence
0 H a a H
Uf
1 H b b + f(a)
ψi ψ
f
FIGURE 7.6 Quantum circuit to implement Deutsch’s algorithm.
whether f (x) is balanced or not. We cannot determine f (x). But determine

a global property of f (x), namely, f (0) ⊕ f (1) with one evaluation of f (x)
only. So, a clever choice of function and final transformation allows efficient
determination of useful information about the function. The above is achieved
much faster compared to a classical computer.
7.5.2 Grover’s Quantum Search Algorithm

In this subsection we explain the quantum search algorithm [12,16,17] and
describe some of the exciting ways it can be used.
The kind of search problem that can be solved by a quantum search algo-
rithm is following. Consider a function f (x) with integer arguments 0 to N .
Let the value of it be 0 everywhere except for x = ω. The problem is to find
ω using few calls to f (x). This is analogous to finding the name of person in a
telephone directory with the telephone number given. The data-base we wish
to search is of size N . Classically, the probability of the value of a randomly
chosen element to be ω is 1/N . Therefore, to have a 50 − 50 chance of getting
ω we must call the data-base at least √ N/2 times. But a quantum algorithm
can reduce the calls to approximately N .
Lov Kumar Grover, a computer scientist at Lucent Technologies Bell Lab-
oratories proposed a quantum search algorithm. In the following we discuss
Grover’s algorithm following mainly the review of Sudarshan [17]. We can
model an oracle or a unitary operator Uω (λ) as a black-box function f (x). It
computes f (x) for an input x. It will return 1 if and only if x = ω and return
0 if x = ω. A quantum circuit that has the ability to recognize solutions to the
search problem is called a quantum oracle which is represented by the unitary
operator Uω .
We begin with the state |0 0. The two zero’s represent two registers of
qubits where all the qubits are set to the 0 state. We can use Hadamard
transformation to bring this initial state into superposition of states
1
|φ = √ [ |00 + |10 + |20 + · · · + |N − 10] . (7.42)
N
In matrix form, the transformation is given by Eq. (7.16). In Grover’s algo-

rithm the first register is assumed to be big enough to represent the largest ele-
ment. In the second register there is only one qubit. By applying the Hadamard
transformations on the individual qubits of the initial state we get
N −1
1 |1 − |0
|φ = √ |i √ . (7.43)
N i=0 2
The number of steps needed for this is O(log N ). The second register is ini-
tialized to a state different from |0. The action of the oracle Uω is
Uω |i, j = |i, j ⊕ f (i) . (7.44)
|i is the index register, |j is the oracle single qubit which is flipped if f (i) = 1
and unchanged otherwise. We can find whether i is a solution of the problem
by preparing |i|0, applying the oracle and checking whether the oracle qubit
is flipped to |1. We have
⎡ ⎤

1 ⎣ |1 − |0 |1 − |0 ⎦
Uω |φ = √ |i √ − |ω √ . (7.45)
N i=ω 2 2
The action of Uω on |φ is to change the sign of the component in the direc-
tion of |ω. This reflects |φ in the Hilbert space of dimension N about the
hyperplane orthogonal to |ω. At this instant the value of ω is unknown to
us. We can find the value of ω by consulting the oracle a certain minimum
number of times.
Now, we construct another operator Us which performs a reflection in
such a way that the component of |φ along |s is preserved and the signs of
the component in the hyperplane perpendicular to |s is changed. Here one
iteration is the unitary transformation RGrov = Us Uω . Let θ be the angle
between |s and |ω. Then the action of one iteration on |φ is to rotate its
component along |s through an angle 2θ that is away from the hyperplane
perpendicular to the vector |ω. Successive iterations with various choices of |s
makes |φ close to |ω and moreover away from the hyperplane perpendicular
to |ω. The number of queries required to obtain the correct value √ of |ω with
large probability when |φ is measured after the iterations is π N /4. So,
Grover’s algorithm has a quadratic speedup compared to the best classical
algorithm.
7.5.3 Quantum Fourier Transform

The discrete Fourier transform is defined by
N −1
1 i2πjk/N
fj = √ e gk . (7.46)
N k=1
This transforms a set of N numbers {g0 , g1 , · · · , gN −1 } (can be complex) into

another set of numbers {f0 , f1 , · · · , fN −1 }. The quantum Fourier transform
UFT is defined, on n qubits by its action on basis states |j where 0 ≤ j ≤
2n − 1, as
2n −1
1 i2πjk/N
UFT |j → √ e |k . (7.47)
N k=0
It can be easily verified that UFT is a unitary√operator: The matrix of the
transformation is M (UFT ) = [Mjk ] = ei2πjk/N / N . This transformation can
be realized as a quantum circuit.
Many of the quantum algorithms are based on quantum Fourier trans-
form. Shor’s fast algorithm for factoring and discrete logarithm are two most
interesting examples of algorithms based on the quantum Fourier transform.
Classically, the fast Fourier transform takes about N log N = n2n steps to
Fourier transform N = 2n numbers. A quantum computer requires only n2
steps. So, there is an exponential saving of time with a quantum computer
compared to a classical computer. But it is to be noted that the set {fj } can-
not be measured directly because a measurement would collapse each qubit
into |0 or |1. Though quantum computation can be done more efficiently,
creating the initial state {gk } and measuring the result are difficult.
7.5.4 Applications of Quantum Search

Let us point out some of the applications of quantum search.
1. An effective search algorithm for hard problems, like constrained opti-
mization, is the so-called randomized algorithm. In it a set of random
numbers is used to find a trajectory through some search space. Quan-
tum search is able to speed-up randomized algorithms.
2. Quantum search can be applied to determine the statistical properties
mean, variance, maxima and minima of functions, etc.
3. With quantum Fourier transform one can count effectively the number
of possible solutions of a problem without finding them.
4. Quantum search is useful for experimental physicists to prepare desired
superposition states. For example, to create a superposition of indices
corresponding to prime numbers we can design an oracle f (x) which
returns 1 if x is a prime and 0 otherwise.
7.5.5 Shor’s Algorithm

In 1994 Shor [9] developed an efficient quantum algorithm to compute the pe-
riod of a periodic function. The period finding routine can be used to factorize
large numbers in polynomial time. Consider the problem of factorizing a large
number N into exactly two large prime numbers [17]. Classically,√ to find the
two prime numbers we have to check all the numbers from 1 to N .
In Shor’s algorithm, randomly a number a < N , ar = 1 (mod N ) for an
even integer value of r is chosen. It can be shown that for most choices of a,
N shares a common factor having ar/2 + 1 or ar/2 − 1. Once r is found then
applying a classical Euclid’s algorithm one can easily compute the common
factor of N and also ar/2 ± 1. Thus, the problem of factorizing N is solved.
Let us choose
fN,a(x) = ax (mod N ), x = 0, 1, 2, · · · . (7.48)
Because ar = 1 (mod N ) the period of fN,a is r. Evaluate fN,a on a |φ given

by
N −1
1
|φ = √ |i0 . (7.49)
N i=0
Next, we setup a unitary oracle UfN,a such that
N −1
1 x
UfN,a |φ = √ |ia (mod N ) = |ψ . (7.50)
N i=0
The second register has a function with period r. Therefore, if we perform

a measurement on it and obtain |u then the first register will collapse to a
linear combination of the values of x. This results in f (x) = u. Due to the
periodicity of f these values of x form x0 + jr, j = 0, 2, · · · , xmax /r where
xmax is the biggest number contained in the first register. We have f (x0 ) = u.
Suppose t = xmax /r is an integer. The measurement is found to reduce |ψ to
xmax
−1
1
|φ = |x0 + jr |u . (7.51)
xmax /r j=0
Now, to get the value of r apply a quantum Fourier transform on the first
register (of the state |φ). The effect is

UFT |φ → f (k) |k |u , (7.52)
k
where f (k) = 1 if k is a multiple of xmax /r otherwise 0. The value of k

determined by the measurement of the first register will be of the form k =
λxmax /r. λ and r are unknown. But if λ and r do not have a common factor
then k/xmax = λ/r can be reduced to an irreducible fraction to read r and λ.
On the other hand, if λ and r have a common factor then we conclude that
the algorithm fails. In this case we repeat the analysis with another value of
a. It is possible to show that the number of steps taken by the algorithm to
get the correct answer is O(log N ). This is indeed an exponential speed-up
compared to the classical case.
7.5.6 Quantum Factorization of Integers

Let us describe the quantum factorization of integers by considering the num-
ber 20. First, choose a number a randomly such that the greatest common
divisor of it and N is 1. Consider the periodic function
f (x) = ax (mod N ), x = 0, 1, · · · . (7.53)
For N = 20, select a = 9. Then from Eq. (7.53) we have
f (0) = 1 (mod 20) = 1.

f (1) = 9 (mod 20) = 9.
f (2) = 92 (mod 20) = 81 (mod 20) = 1.
f (3) = 93 (mod 20) = 729 (mod 20) = 9.
f (4) = 94 (mod 20) = 6561 (mod 20) = 1.
From the above, the period T of f (x) is obtained as T = 2. This period can be
determined by employing the method described earlier. To find N , calculate
Z = aT /2 = 91 = 9. The greatest common divisor of (Z + 1, N ) = (9 + 1, 20) =
(10, 20) is 10. The greatest common divisor of (Z −1, N ) = (9−1, 20) = (8, 20)
is 4. These two numbers 4 and 10 are factors of 20. In this way two factors of
a number N can be obtained if the quantum algorithm gives the period T of
f (x).
7.6 FEATURES OF QUANTUM COMPUTATION

Some of the essential (but not sufficient) features of quantum computers [18]
are summarized below:
1. Input, output, program and memory are represented by qubits.
2. A unitary transformation of the computer can represent a computation
step.
3. All computations are reversible.
4. Only one-to-one operations are possible and therefore qubits cannot be
copied.
5. The values of qubits may depend on the method used to infer them and
on the co-measured qubits.
6. A measurement may be performed on any qubit at any stage of compu-
tation. However, a qubit cannot be measured by an experiment with a
desired accuracy.
7. During a computation, a quantum computer proceeds all paths at once
which when managed cleverly may speed-up the computation.
8. A subroutine should not leave any qubits over its computed answer. This
is because the computational paths with different information cannot
interfere.
In order to perform a quantum computation one should make proper use of
the above features.
7.7 QUANTUM COMPUTATION THROUGH NMR

The essential requirement of a quantum computer are two-level isolated quan-
tum systems. The physical systems explored so far to build quantum hard-
wares range from optical photons, cavity quantum electrodynamics, quantum
dots, trapped ions to nuclear spins. The basic requirements of a quantum
computer are:
1. The quantum states must be sufficiently isolated from the surroundings
so that they have very low decoherence.
2. They must be made to evolve as per the unitary transformations per-
formed.
3. It should be possible to prepare the initial state.
4. Suitable measurement technique must be devised for measuring quan-
tum information because a measurement destroys quantum information
and replaces it with classical information.
As a candidate for quantum computing, nuclear magnetic resonance
(NMR) is attractive because of the spin’s long coherence times and also due
to the complexity of operations performed on modern spectrometers. Most
atomic nuclei have spin and it causes them to act like tiny magnets. These
nuclear magnets interact with magnetic fields thereby allowing them to be
controlled with high precision. In certain cases, such as in hydrogen, this nu-
clear spin can assume two values, spin-up and spin-down. This is a two-state
quantum system. Therefore, a hydrogen nucleus can be regarded as a qubit. In
a molecule, different nuclei can be differentiated by their different resonance
frequencies. Consequently the molecule can act as a quantum computer with
each hydrogen providing one qubit. For example, naturally occurring cyto-
sine has five hydrogen atoms in each molecule. It is in fact easy to replace
three of them with deuterium, thereby leaving the two hydrogens to serve a
two-qubit computer. This system with a conventional NMR spectrometer has
been used to demonstrate certain quantum algorithms. Various nonselective
pulses, transition and spin-selective pulses, rf gradients, coherence transfer via
J-coupling and simultaneous multi-site excitation have been proposed to con-
struct universal quantum gates and implement quantum algorithms for qubit
systems. For some details see refs.[13,19-22].
7.8 WHY IS MAKING A QUANTUM COMPUTER

EXTREMELY DIFFICULT?
If quantum computers would be so marvelous, why don’t we just build one?
There are several technical problems in setting up a quantum computer. We
list some of them:
1. A notable serious problem is decoherence. It is the modification of the
quantum state due to interaction with an environment. It can alter the
value of a qubit that is uncontrollable.
2. Errors in classical information are discrete. In quantum information they
are continuous.
3. To check whether errors have occurred, we must perform a quantum
measurement. But a measurement will affect the state of the system.
That is, errors cannot be diagnosed without introducing further errors.
4. To obtain the outcome of a computation, a readout system must carry
out a measurement. Any imperfection in the measurement process gives
rise to a readout error.
5. A transistor or any conventional computer element cannot be useful to
perform quantum computation.
6. The various degrees of freedom of the device (such as the elastic vi-
brations of the device, the excitation of its conduction electrons, etc.)
interact strongly with one another and also with the state of the device.
As a result even approximate unitary evolution is impossible.
7.9 CONCLUDING REMARKS

Quantum algorithms for solving both linear and nonlinear differential, equa-
tions [23-27], quantum field theories [28] and simulation of sparse Hamiltonian
systems [29], chemical dynamics [30] and electronic structure Hamiltonians
[31] have been proposed.
Several groups working on quantum computation are focusing on length-
ening the lifetime of the quantum bits of information and also quickening
the pace of computation. Quantum computing using coherent photon con-
version [32], fullerene based electron spin [33,34], trapped polar molecules
[35], Josephson junction arrays [36], scanning tunneling microscopy [37], an-
tiferromagnetic rings [38], one-dimensional optical lattice [39] and quantum
walk [40] have been proposed. Simulation of electronic structure Hamiltoni-
ans [41], many-body Fermi systems [42], calculations of molecular properties
[43], molecular energies [44] using quantum computers were reported. Imple-
mentation of Deutsch’s algorithm on an ion-trap quantum computer [45] and
experimental realization of it in a one-way quantum computer [46] have been
achieved. Magnetic resonance realization of decoherence-free quantum com-

putation [47], performance of adiabatic quantum computation subject to de-
coherence [48], role of entanglement and correlations in mixed-state quantum
computation [49], quantum discord and the power of one qubit [50] enhance-
ment of quantum computation using quantum chaos [51] and geometric phase
shift in quantum computation using superconducting nano circuits [52] were
analyzed.
7.10 BIBLIOGRAPHY
[1] B. Schumacher, Phys. Rev. A 51:2738, 1995.
[2] G.P. Berman, G.D. Doolen, R. Mainieri and V.I. Tsifrinovich, Introduc-
tion to Quantum Computers. World Scientific, Singapore, 1998.
[3] M. Nielsen and I.L. Chuang, Quantum Computation and Quantum In-
formation. Cambridge University Press, Cambridge, 2002.
[4] V. Sahni, Quantum Computing. Tata McGraw–Hill, New Delhi, 2007.
[5] P.A. Benioff, Phys. Rev. Lett. 48:1581, 1980.
[6] R. Feynman, Found. Phys. 16:507, 1986.
[7] R. Feynman, Int. J. Theor. Phys. 21:467, 1982.
[8] D. Deutsch, Proc. Roy. Soc. London A 400:97, 1985.
[9] P.W. Shor, “Algorithms for quantum computation: Discrete logarithms
and factoring,” in the Proceedings of 35th Annual Symposium on the
Foundations of Computer Science. IEEE Press, Los Alamos, 1994.
[10] P.W. Shor, SIAM J. Comp. 26:1484, 1997.
[11] D. Deutsch and R. Jozsa, Proc. Royal Soc. London A 439:553, 1992.
[12] L.K. Grover, in Proceedings, 28th Annual ACM Symposium on the The-
ory of Computation. ACM Press, New York, 1996 pp. 212.
[13] C.H. Bennett, Physics Today, October 1995, pp. 24.
[14] T. Toffoli, Reversible Computing. Technical Report MIT/LCS/TM-151 ,
1980.
[15] D. Deutsch, A. Berenco and A. Ekert, Proc. Royal Soc. London A
449:669, 1995.
[16] L.K. Grover, Phys. Rev. Lett. 79:325, 1997.
[17] E.C.G. Sudarshan, Current Science 84:511, 2003.
[18] K. Svozil, J. Univ. Comp. Sci. 2:311, 1996.

[19] K. Dorai, T.S. Maohesh Arvind and A. Kumar, Current Science 79:1447,
2000.
[20] D.P. DiVincenzo, Phys. Rev. A 51:1015, 1995.
[21] D.G. Cory, M.D. Price and J.F. Havel, Physica D 120:82, 1998.
[22] N.A. Gershenfeld and I.L. Chuang, Science 275:350, 1997.
[23] S.K. Leyton and T.J. Osborne, arXiv:0812.4423, 2008.
[24] A.W. Harrow, A. Hassidin and S.L. Lloyd, Phys. Rev. Lett. 103:150502,
2009.
[25] X.D. Cai, Z.E. Su., M.C. Chen, M. Gu, M.J Zhu, L. Li, N.L. Liu, C.Y. Lu
and J.W. Pan, Phys. Rev. Lett. 110:230501, 2013.
[26] B.D. Clader, B.C. Jacobs and C.R. Spouse, Phys. Rev. Lett., 110:250504,
2013.
[27] D.W. Berry, J. Phys. A: Math. Theor. 4:105301, 2014
[28] S.P. Jordan, K.S.M. Lee and J. Preskill, Science 336:1130, 2012.
[29] D.W. Berry, G. Ahokas, R. Cleve and B.C. Sanders, Commun. Math.
Phys. 270:359, 2007.
[30] J. Karsal, S.P. Jordan, P.J. Love, M. Mohseni and A.A. Guzik, Proc.
Natl. Acad. Sci. 105:18681, 2008.
[31] J.D. Whitfield, J.D. Biamonte and A.A. Guzik, Mol. Phys. 109:735,
2011.
[32] N.K. Langford, S. Ramelow, R. Prevedel, W.J. Munro, G.J. Milburn
and A. Zeilinger, Nature 478:360, 2011.
[33] W. Harneit, Phys. Rev. A 65:032322, 2002.
[34] S.C. Benjamin, A. Ardavan, G.A.D. Briggs, D.A. Britz, D. Gunlycke,
J. Jefferson, M.A.G. Jones, D.F. Leigh, B.W. Lovett, A.N. Khobystov,
S.A. Lyon, J.J.L. Morton, K.Porfyrakis, M.R. Sambrook and A.M. Tyry-
shkin, J. Phys.: Condens. Matter 18:S867, 2006.
[35] D. DeMille, Phys. Rev. Lett. 88:067901, 2002.

[36] L.B. Ioffe and M.V. Feigelman, Phys. Rev. Lett. 66:224503, 2002.
[37] G.P. Berman, G.W. Brown, M.E. Hawley and V.I. Tsifrinovich, Phys.
Rev. Lett. 87:097902, 2001.
[38] F. Troiani, A. Ghirri, M. Affronte, S. Carretta, P. Santini, G. Amoretti,

S. Piligkos, G. Timco and R.E.P. Winpenny, Phys. Rev. Lett. 94:207208,
2005.
[39] J.K. Pachos and P.L. Knight, Phys. Rev. Lett. 91:107902, 2003.
[40] A.M. Childs, Phys. Rev. Lett. 102:180501, 2009.
[41] J.D. Whitfield, J. Biamonte and A. Aspuru-Guzik, Mol. Phys. 109:735,
2011.
[42] D.S. Abrams and S. Lloyd, Phys. Rev. Lett. 79:2586, 1997.
[43] B.P. Lanyon, J.D. Whiifield, G.G. Gillett, M.E. Goggin, M.P. Almeida,
I. Kassal, J.D. Biamonte, M. Mohseni, B.J. Powell, M. Barbieri,
A. Aspuru-Guzik and A.G. White, Nature Chemistry 2:106, 2010.
[44] A. Aspuru-Guzik, A.D. Dutoi, P.J. Love and M. Head-Gordon, Science
309:1704, 2005.
[45] S. Gulde, M. Riebe, G.P.T. Lancaster, C. Becher, J. Eschner, H. Haffner,
F. Schmidt Kaler, I.L. Chuang and R. Blatt, Nature 421:48, 2003.
[46] M.S. Tame, R. Prevedel, M. Paternostro, P. Bohi, M.S. Kim and
A. Zeilinger, Phys. Rev. Lett. 98:140501, 2007.
[47] J.E. Ollerenshaw, D.A. Lidar and L.E. Kay, Phys. Rev. Lett. 91:217904,
2003.
[48] M.S. Sarandy and D.A. Lidar, Phys Rev. Lett. 95:250503, 2005.
[49] A. Datta and G. Vital, Phys. Rev. A 75:042310, 2007.
[50] A. Datta, A. Shaji and C.M. Caves, Phys. Rev. Lett. 100:050502, 2008.
[51] T. Prosen and M. Znidaric, J. Phys. A: Math. Gen. 34:L681, 2001.
[52] S.L. Zhu and Z.D. Wang, Phys. Rev. A 66:042322, 2002.
7.11 EXERCISES
7.1 Assume that a qubit can be expressed as |ψ = cos (θ/2) |0 +
sin (θ/2) eiφ |1 with θ ∈ [0, π] while φ ∈ [0, 2π]. Express the two qubits
|ψ|φ in separable form and also find |ψ⊗2 .
7.2 Obtain the matrix representation of the Hadamard gate.
7.3
Express the Hadamard terms of the Pauli matrices σ1 =
gate in
0 1 1 0
and σ3 = .
1 0 0 −1
7.4 Determine α, β, γ and δ of the decomposition matrices for the Hadamard

gate.
7.5 Find the unitary matrix for the two qubit gate given in Fig. 7.7 and
show that it is equivalent to controlled NOT gate.
a a
b X aXb
FIGURE 7.7 An equivalent controlled NOT gate.
7.6 If X, H and Z denote the quantum NOT, Hadamard and Z gates re-
spectively, find HZH.
7.7 Consider the initial state
λ μ
|ψ = √ (|000 + |011) + √ (|100 + |111).
2 2
Find the state after applying a CNOT gate (using the first qubit as the
control qubit and the second as the target) followed by Hadamard gate
on first qubit.

1 1 0
7.8 Suppose M0 = |00| = 0 1 = and M2 =
0 0 0
0 0 0
0 1 = are two measurement operators. If |ψ =
1 0 1
a|0 + b|1 find the probability of measuring |0.

1 0
7.9 If S = is a quantum phase gate then form its truth table.
0 i

1 0
7.10 Form the truth table for the T gate defined as T = .
0 eiπ/4
7.11 Consider the two circuits shown in Fig. 7.8. The left-side circuit is the
swap gate which exchanges the state of two qubits. Show that the two
circuits in Fig. 7.8 are equivalent.
x +
x + +
FIGURE 7.8 Two equivalent circuits.
7.12 In the notation |a|b = |ab where a is the control bit and b is the target
bit, find the outputs of the quantum circuit shown in Fig. 7.9 for the
inputs |00, |01, |10 and |11.
a H
b +
ψi ψ0
FIGURE 7.9 A quantum circuit with a Hadamard gate.
7.13 Construct the truth table for the Toffoli gate shown in Fig. 7.10 and
show that it stimulates NAND gate.
a a
b b
1 + c
FIGURE 7.10 A Toffoli gate.
7.14 Find the output of the circuit given in Fig. 7.11, which can be used to
implement the Deutsch’s algorithm, for the input |ψi = |0 |1 = |01.
0 Η a a Η
Uf
1 Η b b + f(a)
ψi ψ1 ψ2 ψf
FIGURE 7.11 A quantum circuit of Deutsch’s algorithm.

3
QUANTUM COMPUTING
This chapter is excerpted from

Quantum Principles and Particles, Second Edition
by Walter Wilcox
© 2020 Taylor & Francis Group. All rights reserved.
Learn more
Appendix G: Quantum Computing
G.1 INTRODUCTION
It is strongly suspected that computers that function as quantum mechanics simulators, so-
called quantum computers, will prove to be inherently more powerful than conventional or
classical computers. The main reason for this is that quantum computers, whose functions are
based on manipulating coherent quantum amplitudes, will have a huge advantage in algorithmic
speed. A number of fundamental algorithms require fewer logical steps to solve on a quantum
computer than its conventional counterpart. Another intrinsic advantage is in the expansion of
the memory space of computations. The state space of such machines will someday overwhelm
conventional machines in terms of the storage and manipulation of large data sets.
Quantum computers are now a reality, but we are only in the initial stages of understanding
the things such machines are capable of doing. I cannot in any way do justice to the burgeoning
field of quantum computation and information here, but I will attempt to impart some of the
excitement of the concepts involved and make connections to helpful references that can paint a
more complete picture. In any case, a student in quantum mechanics is actually in a very advan-
tageous position to understand, utilize, and manipulate such new resources, and so a modest
introductory tutorial on this topic seems very appropriate.
G.2 COMPUTATIONAL BASICS
What is a quantum computer?* First, let us distinguish it from what we are terming a classical
computer. A classical computer works its way serially through a problem, one step at a time. This
mode of operation has been greatly improved upon over the past several decades by incorporating
the concept of parallel processing: a problem can be broken into pieces and many independent
calculations can be done simultaneously. However, a quantum computer will do better: it can
manipulate all possibilities at once without the need to break the problem into pieces with the
attendant overheads. The classical computer works on irreversible steps of logic, pulling items
out of an inventory, whereas the quantum computer works on reversible global amplitudes that
are immediately accessible. The logic necessary for a quantum computer is a generalization of the
ways we learned how to manipulate spin 1/2 amplitudes in Chapter 1. Quantum computation
involves all the concepts we learned about in our quantum excursions: indeterminism, interfer-
ence, uncertainty, and superposition. There will only be a change in terminology here, with no
change in the underlying quantum concepts. Mathematically, quantum computation is just an
application of linear algebra, but it is important to get used to the language in this new field.
Let us first think about the basic algorithmic elements of a quantum computer. The basic com-
putational component of a classical computer is the bit, which is a logical unit that can take on
only two values, conventionally labeled 0 and 1, whereas the basic unit on a quantum computer
* See the early overview article for a more eloquent orientation: L. Grover, “Quantum Computing,” The Sciences, July/
August 1999, 24–30.
565
566 Appendix G: Quantum Computing
is a two-valued qubit (quantum bit), whose general structure we learned about in Chapter 1. The
general state of this qubit |ψ〉 is the linear superposition
| yñ = a | 0ñ + b | 1ñ , (G.1)
where bra–ket notation is being used, and the states are orthonormal: á0 | 0ñ = á1 | 1ñ = 1,
á0 | 1ñ = á1 | 0ñ = 0. α and β are complex numbers with the normalization condition:
áy | yñ = | a |2 + | b | 2 = 1. Thus |0〉 is simply “spin up” (| 0ñ º | +ñ from Chapter 1), and |1〉 is “spin
down” (|1ñ º | -ñ ):
æ1ö æ0ö
0 « ç ÷ , 1 « ç ÷. (G.2)
ç0÷ ç1÷
è ø è ø
The states |0〉 and |1〉 are called the computational basis states, and are the analog of the bits 0 and
1 in conventional computer logic. The column–matrix equivalent form of the state in Equation
G.1 is of course
æaö
y = ç ÷. (G.3)
çb÷
è ø
After normalization, the qubit parameter space (or manifold) is characterized by two numbers.
Going back to bra–ket notation, the most general state may be written
æ q if q ö
| yñ = ç cos | 0ñ + e sin | 1ñ ÷ (G.4)
è 2 2 ø
(cf. Equations 1.80 and 1.222 in Chapter 1 and Equation 10.100 in Chapter 10) outside of an irrel-
evant overall phase, for the real parameters θ and ϕ. Based upon our experience with spin 1/2,
we know that θ and ϕ may be interpreted as the spherical coordinate direction angles associated
with the vector pointing in the geometrical “up” spin direction; θ is the polar angle and ϕ is the
azimuthal one. This one-to-one mapping of the state in Equation G.4 to a direction in an internal
space is embodied in the so-called Bloch sphere, shown in Figure G.1.
Defining a set of labels xi=(0,1) for qubit i, a direct product of qubits, | x1 , x2 ,... ñ º | x1 ñÄ | x2 ñ Ä ...,
may be used as computational basis states for the computer state just as a conventional spin basis
for a set of particles, | m1 , m2 ,...ñ º | m1 ñÄ | m2 ñ Ä ..., can be used for the spin state, just as we studied
in Chapter 8. So, for a two-qubit system, the basis states can be taken to be |0,0〉, |1,0〉, |0,1〉, and
|1,1〉. The state of such a system can be in a mixture of such basis states, for example
| yñ = a | 0, 0ñ + b | 1, 0ñ + c | 0,1ñ + d | 1,1ñ , (G.5)
where | a |2 + | b |2 + | c |2 + | d |2 = 1. Such a multiqubit state is said to be “entangled.”

Now consider a system of n qubits. The number of different states of such a system is 2n. The
computational memory of a conventional one terabyte (1012 bytes) machine would be approxi-
mately equivalent to a quantum computer with only n = 40 qubits. Computer hardware has
improved at an exponential rate for well over 50 years. A conventional encapsulation of this
Appendix G: Quantum Computing 567
FIGURE G.1 The Bloch sphere representation of the state of a single qubit.
progress is embodied in Moore’s law,* which states that market forces drive a doubling in compu-
tational power roughly every 2 years. However, this level of advancement in conventional mem-
ory would be equivalent to simply adding a single additional qubit to a quantum computer in the
same amount of time!
A new computational field has emerged in which conventional computers are used to sim-
ulate quantum ones. Such simulations can be used for testing and reliability considerations.
Conventional parallel computers with better algorithms have so far kept pace with their quantum
cousins. However, a point will come where quantum computers, which are capable of doing 2n
mathematical operations simultaneously, will outpace all conventional ones. This point of separa-
tion is termed quantum supremacy.
G.3 SOME LOGIC GATE CONCEPTS
In conventional computers, logic is performed by so-called logic gates on bits. Four examples are
shown in Figure G.2. The NOT gate is the only single-bit logic gate. The three others are called
AND, OR, and NOR gates. They have incoming bits labeled a and b; the output bit is determined
by the logic of the gate, which is represented by a symbol. Notice that in the last three cases the
action is irreversible: 2 bits in, 1 bit out. In each case, an associated truth table is also given for the
gate. The horizontal lines represent the causal flow from left to right.
Quantum logic gates are fundamentally different. The number of gates on input and output are
always the same. In contrast to the conventional computer single-bit gate, there are an unlimited
number of single-qubit logic gates. In fact, the operations on single-qubit gates are equivalent
to 2 × 2 unitary matrices U in linear algebra, and the action on the gates is always reversible.
* Named after Gordon Moore, a computer entrepreneur who made his observation/forecast in 1975. More technically,
the law involves the number of transistors on a central processing unit (CPU). This rate has held roughly constant until
the present (2019), but this trend must end eventually, as microprocessors are reaching the limits of the classical world,
where quantum indeterminacy is definitely not an advantage. The latest prognostication is that the law will last until
around 2025.
FIGURE G.2 Some standard logic gates for conventional computers.
Some standard single-qubit operations and their associated unitary transformations are given
in Figure G.3. Note that such operations are specified by the action on the computational basis
| x1 , x2 ñ ® U | x1 , x2 ñ, which is analogous to the truth tables for conventional logic gates. Multiple
operations may be performed on a qubit, with the right-flowing causal order indicated by a hori-
zontal line. We found it useful in Chapter1 to explain the action of operators on quantum ket-
states by the use of Process Diagrams, in which there was an understood causal flow of symbols
from right to left. Similarly, workers in the quantum information field have found it useful to
illustrate multiple qubit operations as such a flow. Qubits are conventionally shown as flowing
horizontal lines, with operations taking place on them in causal order from left to right.
In addition to the single-qubit operations, there are also operations involving multiple qubits.
One of the two-qubit types of logic gates is called controlled operations, in that one qubit state is
used to control the output of another qubit. The symbolic form of the controlled-U operation is
shown next. Note that the gates are labeled from top to bottom.
The control qubit is used to set a condition, whereas the target qubit is conditionally modified
with one of the single-qubit logic gates, U. The control qubit is said to be “set” when its computa-
tional basis x-value is 1. That is, when qubit 1 is the control and qubit 2 is the target, one has the
controlled U(1) unitary operation:
FIGURE G.3 Some single-qubit logic gates and associated matrices.
ì | x1 , x2 ñ , x1 = 0,
U (1 ) ï (G.6)
| x1 , x2 ñ ¾¾¾ ®í
ï| x ñU | x ñ , x = 1.
î 1 2 1
When control and target are reversed, one has the controlled U(2) operation:
ì | x1 , x2 ñ , x2 = 0,
U (2) ï (G.7)
| x1 , x2 ñ ¾¾¾ ®í
ïU | x ñ | x ñ , x = 1.
1 2 2
î
A fundamental controlled two-qubit operation, called CNOT, is defined by
CNOT(1)
| x1 , x2 ñ ¾¾¾¾¾®| x1 , x1 Å x2 ñ , (G.8)
when the first qubit is the control, and where the addition of the labels on the target qubit, x1 Å x2 ,
is done in mod(2) arithmetic. It is symbolized by
This operation is actually equivalent to a controlled Pauli X operation:

The equivalence is the subject of Problem G.3.

There are many other conditional qubit operations involving three or more qubits. For exam-
ple, the following gate symbol shows a Toffoli gate, which is just a multiqubit generalization of
the two-qubit CNOT gate. In this case, both control gates must be “set” for the third gate to act.
G.4 OUTLINE OF ALGORITHMS

What are some of the known algorithms that quantum computers are expected to excel at?*
◾ Quantum Fourier transform. We have already encountered the quantum version of

the traditional Fourier transform in Appendix B, Equations B.9 and B.10. It is a unitary
transformation on qubits, and so can be considered a logic gate for quantum informa-
tion. For a set of 2n qubits, the number of logic gates necessary is of order n2. This beats
the traditional Fast Fourier Transform (FFT) that requires n2n classical logic gates. The
efficient implementation of the quantum Fourier transform is a key ingredient in many
quantum algorithms, including the following.
◾ Factorization of numbers. Calculating the prime factors of a very large odd com-
posite number N is considered essentially impossible for a conventional computer,
but turns out to be considerably less computationally intensive for a quantum one. A
quantum computer uses (log N ) 2 (log log N )(log log log N ) (base 2 logarithms) logic
gates, whereas a conventional computer, using a so-called number field sieve, uses
~ exp(c (log N )1/ 3 (log log N )2/ 3 ) gates, where c » 1.9 . Such factorizations, which are easy
to assign but hard to decode, are used every day for commercial encryption purposes,
which means that quantum computers could decipher such communications. This is
obviously an impetus for the development of study of such machines! The quantum fac-
torization code was developed by Peter Shor in 1994.†
◾ Quantum search algorithms. The problem of doing searches through data is intrinsi-
cally more efficient on quantum computers than classical ones. It can be shown that a
search through N items can be done with N logic steps as opposed to the classical
* See the Wiki “Quantum Algorithms” (https://en.wikipedia.org/wiki/Quantum_algorithm) for a more detailed list.
† P. Shor, “Algorithms for Quantum Computation: Discrete Logarithms and Factoring,” Proceedings of the 35th Annual
Symposium on Foundations of Computer Science, IEEE Press (1994).

number of steps N. This algorithm can also be used to speed up cryptographic searches.
The algorithm was developed by Lov Grover in 1996.*
◾ Quantum simulations. Is it possible to do an actual quantum simulation† of quantum
systems that arise in atomic, nuclear, or particle physics? Classical simulations of quan-
tum systems use the Monte Carlo algorithm described in Appendix E. This is a way
of summing over a huge set of possible states. Is it possible to simulate such theories
directly on a set of spatially arrayed qubits? This possibility was speculated upon by
Feynman in a visionary talk in 1981.‡ His point was that to simulate the responses of
quantum systems, the best thing to do is to make them quantum mechanical also. There
is an impressive amount of work in this direction already.§
G.5 COMPUTER REALIZATIONS

How does one build a quantum computer? One needs a physical realization of the qubit, an abil-
ity to maintain its quantum state, as well as an ability to control their interactions. In addition,
a quantum computer has to be completely isolated from its environment if it is to maintain its
quantum state. One also needs a way to control input and output. Such machines will in fact be
hybrid devices with classical interfaces controlling and interacting with the quantum comput-
ing device. Many companies and organizations are working on such devices, and many different
ideas are being tested. The race is on to build these machines and demonstrate their usefulness.
It is likely that anything one writes concerning the operational state of these devices will be found
to be obsolete within a few years. However, there will always be a need to summarize existing tech-
nologies for the incoming student. As of the writing of this appendix (2019), the leading edge of the
maturing technologies seems to be based upon the following types of devices.
◾ Superconducting Josephson circuits. Superconducting circuits called Josephson cir-

cuits or junctions may be put into a coherent state between various isolated low-lying
charge, flux, or phase states. Such devices can be conveniently designed and imple-
mented on integrated chips.
◾ Trapped ions. Individual charged atoms or ions can be trapped using an oscillating
electric field in a so-called Paul trap. Tuning with lasers can also place the atoms in a
superposition of two of their standard atomic states.
◾ Quantum dots. Small spheres can be fabricated on superconducting silicon chips on

which an electron is placed, whose operation is controlled by microwaves. The electronic
spin state or electron position state in a quantum potential well can form the qubits.
◾ Topological quasiparticles. Two-dimensional quasiparticle combinations called any-

ons may be formed from electrons on braided integrated circuits. The braiding forms
topological structures with conserved quantum numbers.
* L. Grover, “A Fast Quantum Mechanical Algorithm for Database Search”, Proceedings of the 28th Annual ACM
Symposium on the Theory of Computing, ACM Press, 212 (1996). L. Grover, “Quantum Mechanics Helps in Searching
for a Needle in a Haystack,” Phys. Rev. Lett. 79, 325 (1997).
† T. Johnson, S. Clark, and D. Jaksch, “What Is a Quantum Simulator?” EPJ Quantum Technology 1, 10 (2014).
‡ R. Feynman, “Simulating Physics with Computers,” Int. J. Theor. Phys. 21, 467 (1982). Such devices were also consid-
ered in Yu. Manin, “Computable and Noncomputable” (in Russian), Sov. Radio. 13 (1980).
§ See, for example, the articles in A. Trabesinger, ed., “Quantum Simulation,” Nat. Phys. 8 (2012). A recent imposing
simulation is described in J. Zhang et al., “Observation of a Many-Body Dynamical Phase Transition with a 53-Qubit
Quantum Simulator,” Nature 551, 601 (2017).
This is just a mere sampling of the technologies that are being tested.* The list given now for the
leading candidates may be completely different in just a few years!
A major problem with such machines is the tendency for the quantum state created to lose
quantum coherence, or “decohere.” It turns out the system decoherence time decreases as the
number of qubits increases. The decoherence time for n qubits is roughly 1/n times shorter than
the decoherence time for an individual qubit.† Maintaining a quantum state in the macroscopic
world is hard to do! The decoherence time for Josephson circuits is the shortest of the tech-
nologies listed, on the order of microseconds, whereas the decoherence time for trapped ions is
the greatest, on the order of seconds. Decoherence times for quantum dots falls somewhere in
between, and it is thought that the quasiparticle approach could provide a very stable system.
Besides the coherence issue, one must also consider the timescale necessary for individual gate
processes to occur, which vary greatly over the various technologies. The time necessary for the
algorithm to complete is the gate process speed times the number of gates, and this must be much
smaller than the system decoherence time for a workable machine.
Part of the cure for the decoherence issue are quantum error-correction and fault tolerance
codes. A major theoretical discovery in the 1990s was that quantum computers could reliably
compute despite the imperfections and faults introduced by quantum noise. The theory of such
quantum error protection is remarkably well developed. The basic idea is to fight entanglement
with entanglement and redundancy. Amazingly, it turns out that reliable computation can be
performed with faulty logic gates, as long as the probability of error on gates is below a certain
threshold. However, the reliability encoding thus introduced means many more qubits must be
3
introduced to control the “working” ones. In order to factor a 300 digit number (» 210 ) using
Shor’s algorithm, it is optimistically estimated‡ to require about 104 qubits, but with error correc-
tion and encoding, it could take 103 × 104 = 107 qubits to actually work. Thus, unless qubits turn
out to be easily protectable (as is possible with the quasiparticle approach) or as easy to form as
transistors on an integrated circuit, this could be a problem!
G.6 REFERENCES
A short list of some popular and recent introductory textbooks on quantum computing follows.
P. Kaye, R. Laflamme, and M. Mosca, An Introduction to Quantum Computing (Oxford University Press,
2007).
N. Mermin, Quantum Computer Science: An Introduction (Cambridge University Press, 2007).
M. Nielson and I. Chuang, Quantum Computation and Quantum Information (Cambridge University
Press, 2010).
E. Rieffel and W. Polak, Quantum Computing: A Gentle Introduction (MIT Press, 2011).
N. Yanofsky and M. Mannucci, Quantum Computing for Computer Scientists (Cambridge University Press,
2008).
PROBLEMS
G.1 The qubit state
1
| yñ =
2
(
| 0ñ + | 1ñ )
* See the Wiki “Quantum computing” (https://en.wikipedia.org/wiki/Quantum_computing).
† M. Dyakonov, “Is Fault-Tolerant Quantum Computation Really Possible?” Future Trends in Microelectronics Workshop,
4–18 (Wiley, 2007).

‡ Dyakonov, “Fault-Tolerant Quantum Computation.”
is represented on the Bloch sphere at the point (1,0,0) in (x, y, z) coordinate space,
because comparing to Equation G.4 one has θ = π/2 and ϕ = 0. Given this initial state,
find the action of the single-qubit operators H, Z, S, and T on |ψ〉 and the associated
final position on the Bloch sphere in (x, y, z) space.
G.2 Show the single-qubit identity
HZH = X .
G.3 Show that the CNOT operation is equivalent to the controlled Pauli X operation, as
discussed and illustrated in Section G.3.
G.4 Show the identity
That is, it is possible to interchange control and target qubits for this operation?
G.5 Show the symbolic identity
Notice the CNOT operation has switched sides.
G.6 Prove directly that the quantum Fourier transform defined in Appendix B (Equations
B.9 and B.10) is unitary and therefore can be considered a qubit gate operation.
4
Quantum Gates, Quantum Circuit and
Quantum Computation
4.1 Introduction
Now that we have introduced qubits to store information, it is time to consider
operations acting on them. If they are simple, these operations are called
gates, or more precisely quantum gates, in analogy with those in classical
logic circuits. More complicated quantum circuits are composed of these
simple gates. A collection of quantum circuits for executing a complicated
algorithm, a quantum algorithm, is a part of a quantum computation.
DEFINITION 4.1 (Quantum Computation) A quantum computation

is a collection of the following three elements:
(1) A register or a set of registers,
(2) A unitary matrix U , which is taylored to execute a given quantum al-

gorithm, and
(3) Measurements to extract information we need.
More formally, we say a quantum computation is the set {H, U, {Mm}},

n
where H = C2 is the Hilbert space of an n-qubit register, U ∈ U(2n ) repre-
sents the quantum algorithm and {Mm } is the set of measurement operators.
The hardware (1) along with equipment to control the qubits is called a
quantum computer.
Suppose the register is set to a fiducial initial state, |ψin = |00 . . . 0, for
example. A unitary matrix Ualg is designed to represent an algorithm which
we want to execute. Operation of Ualg on |ψin yields the output state |ψout =
Ualg |ψin . Information is extracted from |ψout by appropriate measurements.
Actual quantum computation processes are very different from those of a
classical counterpart. In a classical computer, we input the data from a key-
board or other input devices and the signal is sent to the I/O port of the
computer, which is then stored in the memory, then fed into the micropro-
cessor, and the result is stored in the memory before it is printed or it is
65
66 QUANTUM COMPUTING
displayed on the screen. Thus information travels around the circuit. In con-
trast, information in quantum computation is stored in a register, first of all,
and then external fields, such as oscillating magnetic fields, electric fields or
laser beams are applied to produce gate operations on the register. These
external fields are designed so that they produce desired gate operation, i.e.,
unitary matrix acting on a particular set of qubits. Therefore the information
sits in the register and they are updated each time the gate operation acts on
the register.
One of the other distinctions between classical computation and quantum
computation is that the former is based upon digital processing and the latter
upon hybrid (digital + analogue) processing. A qubit may take an arbitrary
superposition of |0 and |1, and hence their coefficients are continuous com-
plex numbers. A gate is also an element of a relevant unitary group, which
contains continuous parameters. An operation such as “rotate a specified
spin around the x-axis by an angle π” is implemented by applying a partic-
ular pulse of specified amplitude, angle and duration. These parameters are
continuous numbers and always contain errors. These aspects might cause
challenging difficulties in a physical realization of a quantum computer.
Parts of this chapter depend on [1, 2] and [3].
4.2 Quantum Gates

We have so far studied the change of a state upon measurements. When
measurements are not made, the time evolution of a state is described by
the Schrödinger equation. The system preserves the norm of the state vector
during time evolution. Thus the time development is unitary. Let U be
such a time-evolution operator; U U † = U † U = I. We will be free from the
Schrödinger equation in the following and assume there exist unitary matrices
which we need. Physical implementation of these unitary matrices is another
important area of quantum information processing and is a subject of the
second part of this book.
One of the important conclusions derived from the unitarity of gates is that
the computational process is reversible.
4.2.1 Simple Quantum Gates

Examples of quantum gates which transform a one-qubit state are given below.
We call them one-qubit gates in the following. Linearity guarantees that the
action of a gate is completely specified as soon as its action on the basis
{|0, |1} is given. Let us consider the gate I whose action on the basis
vectors are defined by I : |0 → |0, |1 → |1. The matrix expression of this
Quantum Gates, Quantum Circuit and Quantum Computation 67
gate is easily found as

10
I = |00| + |11| = . (4.1)
01
Similarly we introduce X : |0 → |1, |1 → |0, Y : |0 → −|1, |1 → |0,
and Z : |0 → |0, |1 → −|1, whose matrix representations are

01
X = |10| + |01| = = σx , (4.2)
10

0 −1
Y = |01| − |10| = = −iσy , (4.3)
1 0

1 0
Z = |00| − |11| = = σz . (4.4)
0 −1
The transformation I is the trivial (identity) transformation, while X is the

negation (NOT), Z the phase shift and Y = XZ the combination of them. It
is easily verified that these gates are unitary.
The CNOT (controlled-NOT) gate is a two-qubit gate, which plays
quite an important role in quantum computation. The gate flips the sec-
ond qubit (the target qubit) when the first qubit (the control qubit) is
|1, while leaving the second bit unchanged when the first qubit state is |0.
Let {|00, |01, |10, |11} be a basis for the two-qubit system. In the following,
we use the standard basis vectors with components
t t t t
|00 = (1, 0, 0, 0) , |01 = (0, 1, 0, 0) , |10 = (0, 0, 1, 0) , |11 = (0, 0, 0, 1) .
The action of the CNOT gate, whose matrix expression will be written as
UCNOT , is
UCNOT : |00 → |00, |01 → |01, |10 → |11, |11 → |10.
It has two equivalent expressions
UCNOT = |0000| + |0101| + |1110| + |1011|

= |00| ⊗ I + |11| ⊗ X, (4.5)
having a matrix form ⎛ ⎞

1 00 0
⎜0 10 0⎟
UCNOT =⎜
⎝0
⎟. (4.6)
00 1⎠
0 01 0
The second expression of the RHS in Eq. (4.5) shows that the action of UCNOT
on the target qubit is I when the control qubit is in the state |0, while it is σx
when the control qubit is in |1. Verify that UCNOT is unitary and, moreover,
2
idempotent, i.e., UCNOT = I.
Let {|i} be the basis vectors, where i ∈ {0, 1}. The action of CNOT on
the input state |i|j is written as |i|i ⊕ j, where i ⊕ j is an addition mod 2,
that is, 0 ⊕ 0 = 0, 0 ⊕ 1 = 1, 1 ⊕ 0 = 1 and 1 ⊕ 1 = 0.
EXERCISE 4.1 Show that the UCNOT cannot be written as a tensor prod-
uct of two one-qubit gates.
EXERCISE 4.2 Let (a|0 + b|1) ⊗ |0 be an input state to a CNOT gate.
What is the output state?
It is convenient to introduce graphical representations of quantum gates. A
one-qubit gate whose unitary matrix representation is U is depicted as
The left horizontal line is the input qubit state, while the right horizontal line
is the output qubit state. Therefore the time flows from the left to the right.
A CNOT gate is expressed as

where • denotes the control bit, while denotes the conditional negation.
There may be many control bits (see CCNOT gate below).
More generally, we consider a controlled-U gate,
V = |00| ⊗ I + |11| ⊗ U, (4.7)
in which the target bit is acted on by a unitary transformation U only when
the control bit is |1. This gate is denoted graphically as
EXERCISE 4.3 (1) Find the matrix representation of the “upside down”
CNOT gate (a) in the basis {|00, |01, |10, |11}.
(2) Find the matrix representation of the circuit (b).

(3) Find the matrix representation of the circuit (c). Find the action of the
circuit on a tensor product state |ψ1 ⊗ |ψ2 .
The CCNOT (Controlled-Controlled-NOT) gate has three inputs, and

the third qubit flips when and only when the first two qubits are both in the
state |1. The explicit form of the CCNOT gate is
UCCNOT = (|0000| + |0101| + |1010|) ⊗ I + |1111| ⊗ X. (4.8)
This gate is graphically expressed as
The CCNOT gate is also known as the Toffoli gate.
4.2.2 Walsh-Hadamard Transformation

The Hadamard gate or the Hadamard transformation H is an important
unitary transformation defined by
1
UH : |0 → √ (|0 + |1)
2
(4.9)
1
|1 → √ (|0 − |1).
2
It is used to generate a superposition state from |0 or |1. The matrix repre-
sentation of H is

1 1 1 1 1
UH = √ (|0 + |1)0| + √ (|0 − |1)1| = √ . (4.10)
2 2 2 1 −1
A Hadamard gate is depicted as
There are numerous important applications of the Hadamard transforma-

tion. All possible 2n states are generated, when UH is applied on each qubit
of the state |00 . . . 0:
(H ⊗ H ⊗ . . . ⊗ H)|00 . . . 0
1 1 1
= √ (|0 + |1) ⊗ √ (|0 + |1) ⊗ . . . √ (|0 + |1)
2 2 2
n
2 −1
1
= √ |x. (4.11)
2n x=0
Therefore, we produce a superposition of all the states |x with 0 ≤ x ≤ 2n − 1

simultaneously. This action of H on an n-qubit system is called the Walsh
transformation, or Walsh-Hadamard transformation, and denoted as
Wn . Note that
W1 = UH , Wn+1 = UH ⊗ Wn . (4.12)
EXERCISE 4.4 Show that Wn is unitary.
EXERCISE 4.5 Show that the two circuits below are equivalent:
This exercise shows that the control bit and the target bit in a CNOT gate
are interchangeable by introducing four Hadamard gates.
EXERCISE 4.6 Let us consider the following quantum circuit
(4.13)
where q1 denotes the first qubit, while q2 denotes the second. What are the
outputs for the inputs |00, |01, |10 and |11?
4.2.3 SWAP Gate and Fredkin Gate

The SWAP gate acts on a tensor product state as
USWAP |ψ1 , ψ2 = |ψ2 , ψ1 . (4.14)

The explict form of USWAP is given by

USWAP = |0000| + |0110| + |1001| + |1111|
⎛ ⎞
1000
⎜0 0 1 0⎟
=⎜⎝0 1 0 0⎠.
⎟ (4.15)
0001
Needless to say, it works as a linear operator on a superposition of states. The
SWAP gate is expressed as
Note that the SWAP gate is a special gate which maps an arbitrary tensor
product state to a tensor product state. In contrast, most two-qubit gates
map a tensor product state to an entangled state.
EXERCISE 4.7 Show that the above USWAP is written as

USWAP = (|00| ⊗ I + |11| ⊗ X)(I ⊗ |00| + X ⊗ |11|)
(|00| ⊗ I + |11| ⊗ X). (4.16)
This shows that the SWAP gate is implemented with three CNOT gates as
given in Exercise 4.3 (3).
The controlled-SWAP gate
is also called the Fredkin gate. It flips the second (middle) and the third
(bottom) qubits when and only when the first (top) qubit is in the state |1.
Its explicit form is
UFredkin = |00| ⊗ I4 + |11| ⊗ USWAP. (4.17)
4.3 Correspondence with Classical Logic Gates

Before we proceed further, it is instructive to show that all the elementary
logic gates, NOT, AND, XOR, OR and NAND, in classical logic circuits can
be implemented with quantum gates. In this sense, quantum information

processing contains the classical one.
4.3.1 NOT Gate

Let us consider the NOT gate first. It is defined by the following logic
function,
0 x=1
NOT(x) = ¬x = (4.18)
1 x=0
where ¬x stands for the negation of x. Under the correspondence 0 ↔
|0, 1 ↔ |1, we have already seen in Eq. (4.2) that the gate X negates the
basis vectors as
X|x = |¬x = |NOT(x), (x = 0, 1). (4.19)
Now let us measure the output state. We employ the following measurement
operator:
M1 = |11|. (4.20)
M1 has eigenvalues 0 and 1 with the eigenvectors |0 and |1, respectively.
When the input is |0, the output is |1 and the measurement gives the value
1 with the probability 1. If, on the other hand, the input is |1, the output
is |0 and the measurement yields 1 with probability 0, or in other words, it
yields 0 with probability 1. It should be kept in mind that the operator X
acts on an arbitrary linear combination |ψ = a|0 + b|1, which is classically
impossible. The output state is then X|ψ = a|1 + b|0.
We show in the following that the CCNOT gate implements all classical
logic gates. The first and the second input qubits are set to |1 to obtain the
NOT gate as
UCCNOT |1, 1, x = |1, 1, ¬x. (4.21)
4.3.2 XOR Gate

Since a quantum gate has to be reversible, we cannot construct a unitary gate
corresponding to the classcial XOR gate whose function is x, y → x⊕y (x, y ∈
{0, 1}), where x⊕y is an addition mod 2; 0⊕0 = 0, 0⊕1 = 1⊕0 = 1, 1⊕1 = 0.
Clearly this operation has no inverse. This operation may be made reversible
if we keep the first bit x during the gate operation, namely, if we define
f (x, y) = (x, x ⊕ y), x, y ∈ {0, 1}. (4.22)
We call this function f , also the XOR gate. The quantum gate that does this
operation is nothing but the CNOT gate defined by Eq. (4.5),
UXOR = UCNOT = |00| ⊗ I + |11| ⊗ X. (4.23)

Note that the XOR gate may be also obtained from the CCNOT gate.
Suppose the first qubit of the CCNOT gate is fixed to |1. Then it is easy to
verify that
UCCNOT |1, x, y = |1, x, x ⊕ y. (4.24)
Thus the CCNOT gate can be used to construct the XOR gate.
4.3.3 AND Gate

The logical AND gate is defined by

1 x=y=1
AND(x, y) ≡ x ∧ y ≡ x, y ∈ {0, 1}. (4.25)
0 otherwise
Clearly this operation is not reversible and we have to introduce the same sort
of prescription which we employed in the XOR gate.
Let us define the logic function
f (x, y, 0) ≡ (x, y, x ∧ y), (4.26)
which we also call AND. Note that we have to keep both x and y for f to be
reversible since x = x ∧ y = 0 implies both x = y = 0 and x = 0, y = 1. The
unitary matrix that computes f is
UAND = (|0000| + |0101| + |1010|) ⊗ I

+|1111| ⊗ X. (4.27)
It is readily verified that
UAND |x, y, 0 = |x, y, x ∧ y, x, y ∈ {0, 1}. (4.28)
Observe that the third qubit in the RHS is 1 if and only if x = y = 1 and 0
otherwise. Thus the CCNOT gate may be employed to implement the AND
gate. It follows from Eq. (4.28) that the AND gate is denoted graphically as
4.3.4 OR Gate
The OR gate represents the logical function

0 x=y=0
OR(x, y) = x ∨ y = x, y ∈ {0, 1}. (4.29)
1 otherwise
This function OR is not reversible either and special care must be taken.
Let us define
f (x, y, 0) ≡ (¬x, ¬y, x ∨ y), x, y ∈ {0, 1}, (4.30)
which we also call OR. Although the first and the second bits are negated, it
is not essential in the construction of the OR gate. These negations appear
due to our construction of the OR gate based on the de Morgan theorem
x ∨ y = ¬(¬x ∧ ¬y). (4.31)
They may be removed by adding extra NOT gates if necessary.

Let |x, y, 0 be the input state. The unitary matrix that represents f is
UOR = |0011| ⊗ X + |0110| ⊗ X + |1001| ⊗ X + |1100| ⊗ I. (4.32)
EXERCISE 4.8 Verify that the above matrix UOR indeed satisfies
UOR |x, y, 0 = |¬x, ¬y, x ∨ y, x, y ∈ {0, 1}. (4.33)
Now it is obvious why negations in the first and the second qubits appear in
the OR gate. Since we have already constructed the NOT gate and AND gate,
we take advantage of this in the construction of the OR gate. The equality
(4.31) leads us to the following diagram:
Accordingly, the first and the second qubits are negated. The unitary matrix
obtained from this diagram is
UOR = (I ⊗ I ⊗ X)
·(|0000| ⊗ I + |0101| ⊗ I + |1010| ⊗ I + |1111| ⊗ X)
·(X ⊗ X ⊗ I). (4.34)
The matrix products are readily evaluated to yield
UOR = (|0000| ⊗ X + |0101| ⊗ X + |1010| ⊗ X + |1111| ⊗ I)

·(X ⊗ X ⊗ I)
= |0011| ⊗ X + |0110| ⊗ X + |1001| ⊗ X + |1100| ⊗ I,
which verifies Eq. (4.32).

Observe that the OR gate is implemented with the X and the CCNOT gates
and, moreover, the X gate is obtained from the CCNOT gate by putting the
first and the second bits to |1.
If we want to have a gate VOR |x, y, 0 = |x, y, x ∨ y, we may multiply
X ⊗ X ⊗ I to UOR from the left so that VOR = (X ⊗ X ⊗ I)UOR .
EXERCISE 4.9 Show that the NAND gate can be obtained from the CC-
NOT gate. Here NAND is defined by the function

0 x=y=1
NAND(x, y) = ¬(x ∧ y) = x, y ∈ {0, 1}. (4.35)
1 otherwise
In summary, we have shown that all the classical logic gates, NOT, AND,
OR, XOR and NAND gates, may be obtained from the CCNOT gate. Thus
all the classical computation may be carried out with a quantum computor.
Note, however, that these gates belong to a tiny subset of the set of unitary
matrices.
In the next section, we show that copying unknown information is impos-
sible in quantum computing. However, it is also shown that this does not
restrict the superiority of quantum computing over the classical counterpart.
4.4 No-Cloning Theorem

We copy classical data almost every day. In fact, this is amongst the most
common functions with digital media. (Of course we should not copy media
that are copyright protected.) This cannot be done in quantum information
theory! We cannot clone an unknown quantum state with unitary operations.
THEOREM 4.1 (Wootters and Zurek [4], Dieks [5]) An unknown quantum
system cannot be cloned by unitary transformations.
Proof. Suppose there would exist a unitary transformation U that makes a

clone of a quantum system. Namely, suppose U acts, for any state |ϕ, as
U : |ϕ0 → |ϕϕ. (4.36)
Let |ϕ and |φ be two states that are linearly independent. Then we should
have U |ϕ0 = |ϕϕ and U |φ0 = |φφ by definition. Then the action of U on
1
|ψ = √ (|ϕ + |φ) yields
2
1 1
U |ψ0 = √ (U |ϕ0 + U |φ0) = √ (|ϕϕ + |φφ).
2 2
If U were a cloning transformation, we must also have

1
U |ψ0 = |ψψ = (|ϕϕ + |ϕφ + |φϕ + |φφ),
2
which contradicts the previous result. Therefore, there does not exist a unitary
cloning transformation.
Clearly, there is no way to clone a state by measurements. A measurement
is probabilistic and non-unitary, and it gets rid of the component of the state
which is in the orthogonal complement of the observed subspace.
EXERCISE 4.10 Suppose U is a cloning unitary transformation, such that

|Ψ ≡ U |ψ|0 = |ψ|ψ
|Φ ≡ U |φ|0 = |φ|φ
for arbitrary |ψ and |φ.
(1) Write down Ψ|Φ in all possible ways.
(2) Show, by inspecting the result of (1), that such U does not exist.
It was mentioned in the end of the previous section that a quantum com-
puter can simulate arbitrary classical logic circuits. Then how about copying
data? It should be kept in mind that the no-cloning theorem states that we
cannot copy an arbitrary state |ψ = a|0 + b|1. The loophole is that the
theorem does not apply if the states to be cloned are limited to |0 and |1.
For these cases, the copying operator U should work as
U : |00 → |00, : |10 →
|11.
We can assign arbitrary action of U on a state whose second input is |1 since
this case does not happen. What we have to keep in our mind is only that U
be unitary. An example of such U is
U = (|0000| + |1110|) + (|0101| + |1011|), (4.37)
where the first set of operators renders U the cloning operator and the second
set is added just to make U unitary. We immediately notice that U is nothing
but the CNOT gate introduced in §4.2.
Therefore, if the data under consideration are limited within |0 and |1,
we can copy the qubit states even in a quantum computer. This fact is used
to construct quantum error correcting codes.
4.5 Dense Coding and Quantum Teleportation

Now we are ready to introduce two simple applications of qubits and quantum
gates: dense coding and quantum teleportation. The Bell state has
been delivered beforehand, and one of the qubits carries two classical bits of
information in the dense coding system. In the quantum teleportation, on
the other hand, two classical bits are used to transmit a single qubit. At first
glance, the quantum teleportation may seem to be in contradiction with the
no-cloning theorem. However, this is not the case since the original state is
destroyed.
Entanglement is the keyword in both applications. The setting is common

for both cases. Suppose Alice wants to send Bob information. Each of them
has been sent each of the qubits of the Bell state
1
|Φ+ = √ (|00 + |11) (4.38)
2
in advance. Suppose Alice has the first qubit and Bob has the second.
4.5.1 Dense Coding
FIGURE 4.1
Communication from Alice to Bob using dense coding. Each qubit of the Bell
state |Φ+ has been distributed to each of them beforehand. Then two bits
of classical information can be transmitted by sending a single qubit through
the quantum channel.
Alice: Alice wants to send Bob a binary number x ∈ {00, 01, 10, 11}. She
picks up one of {I, X, Y, Z} according to x she has chosen and applies the
transformation on her qubit (the first qubit of the Bell state). Applying the
transformation to only her qubit means she applies an identity transformation
to the second qubit which Bob keeps with him. This results in
x transformation U state after transformation

1
0 = 00 I ⊗I |ψ0 = √ (|00 + |11)
2
1
1 = 01 X ⊗I |ψ1 = √ (|10 + |01)
2 (4.39)
1
2 = 10 Y ⊗I |ψ2 = √ (|10 − |01)
2
1
3 = 11 Z ⊗I |ψ3 = √ (|00 − |11).
2
Alice sends Bob her qubit after the transformation given above is applied.
Note that the set of four states in the rightmost column is nothing but the
four Bell basis vectors.
Bob: Bob applies CNOT to the entangled pair in which the first qubit, the
received qubit, is the control bit, while the second one, which Bob keeps, is
the target bit. This results in a tensor-product state:
Received state Output of CNOT 1st qubit 2nd qubit

1 1
|ψ0 √ (|00 + |10) √ (|0 + |1) |0
2 2
1 1
|ψ1 √ (|11 + |01) √ (|1 + |0) |1
2 2 (4.40)
1 1
|ψ2 √ (|11 − |01) √ (|1 − |0) |1
2 2
1 1
|ψ3 √ (|00 − |10) √ (|0 − |1) |0
2 2
Note that Bob can measure the first and second qubits independently since
the output is a tensor-product state. The number x is either 00 or 11 if the
measurement outcome of the second qubit is |0, while it is either 01 or 10 if
the meansurement outcome is |1.
Finally, a Hadamard transformation H is applied on the first qubit. Bob
obtains
Received state 1st qubit UH |1st qubit
1
|ψ0 √ (|0 + |1) |0
2
1
|ψ1 √ (|1 + |0) |0
2 (4.41)
1
|ψ2 √ (|1 − |0) −|1
2
1
|ψ3 √ (|0 − |1) |1
2
FIGURE 4.2
Quantum circuit implementation of the dense coding system. The leftmost
Hadamard gate and the next CNOT gate generate the Bell state. Then a
unitary gate U , depending on the bits Alice wants to send, is applied to the
first qubit. Bob applies the rightmost CNOT gate and the Hadamard gate to
decode Alice’s message.
The number x is either 00 or 01 if the measurement of the first qubit results

in |0, while it is either 10 or 11 if it is |1. Therefore, Bob can tell what x is
in every case.
Quantum circuit implementation for the dense coding is given in Fig. 4.2
4.5.2 Quantum Teleportation

The purpose of quantum teleportation is to transmit an unknown quan-
tum state of a qubit using two classical bits such that the recipient reproduces
exactly the same state as the original qubit state. Note that the qubit itself is
not transported but the information required to reproduce the quantum state
is transmitted. The original state is destroyed such that quantum teleporta-
tion should not be in contradiction with the no-cloning theorem. Quantum
teleportation has already been realized under laboratory conditions using pho-
tons [6, 7, 8, 9], coherent light field [10], NMR [11], and trapped ions [12, 13].
The teleportation scheme introduced in this section is due to [11]. Figure
4.3 shows the schematic diagram of quantum teleportation, which will be
described in detail below.
Alice: Alice has a qubit, whose state she does not know. She wishes to
send Bob the quantum state of this qubit through a classical communication
channel. Let
|φ = a|0 + b|1 (4.42)
be the state of the qubit. Both of them have been given one of the qubits of
the entangled pair
1
|Φ+ = √ (|00 + |11)
2
as in the case of the dense coding.
FIGURE 4.3
In quantum teleportation, Alice sends Bob two classical bits so that Bob
reproduces a qubit state Alice used to have.
Alice applies the decoding step in the dense coding to the qubit |φ =
a|0 + b|1 to be sent and her qubit of the entangled pair. They start with the
state
1
|φ ⊗ |Φ+ = √ a|0 ⊗ (|00 + |11) + b|1 ⊗ (|00 + |11)
2
1
= √ (a|000 + a|011 + b|100 + b|111) , (4.43)
2
where Alice has the first two qubits while Bob has the third. Alice applies
UCNOT ⊗ I followed by UH ⊗ I ⊗ I to this state, which results in
(UH ⊗ I ⊗ I)(UCNOT ⊗ I)(|φ ⊗ |Φ+ )

1
= (UH ⊗ I ⊗ I)(UCNOT ⊗ I) √ (a|000 + a|011 + b|100 + b|111)
2
1
= [a(|000 + |011 + |100 + |111) + b(|010 + |001 − |110 − |101)]
2
1
= [|00(a|0 + b|1) + |01(a|1 + b|0)
2
+|10(a|0 − b|1) + |11(a|1 − b|0)]. (4.44)
If Alice measures the two qubits in her hand, she will obtain one of the states
|00, |01, |10 or |11 with equal probability 1/4. Bob’s qubit (a qubit from the
Bell state initially) collapses to a|0 + b|1, a|1 + b|0, a|0 − b|1 or a|1 − b|0,
respectively, depending on the result of Alice’s measurement. Alice then sends
Bob her result of the measurement using two classical bits.
Notice that Alice has totally destroyed the initial qubit |φ upon her mea-
surement. This makes quantum teleportation consistent with the no-cloning
theorem.
Bob: After receiving two classical bits, Bob knows the state of the qubit in
his hand;
Received bits Bob’s state Decoding
00 a|0 + b|1 I
01 a|1 + b|0 X (4.45)
10 a|0 − b|1 Z
11 a|1 − b|0 Y
Bob reconstructs the intial state |φ by applying the decoding process shown
above. Suppose Alice sends Bob the classical bits 10, for example. Then Bob
applies Z to his state to reconstruct |φ as follows:
Z : (a|0 − b|1) → (a|0 + b|1) = |φ.
Figure 4.4 shows the actual quantum circuit for quantum teleportation.
FIGURE 4.4
Quantum circuit implementation of quantum teleportation. Alice operates
gates in the left side. The first Hadamard gate and the next CNOT gates
generate the Bell state |Φ+ from |00. The bottom qubit is sent to Bob
through a quantum channel while the first and the second qubits are measured
after applying the second set of the CNOT gate and the Hadamard gate on
them. The measurement outcome x is sent to Bob through a classical channel.
Bob operates a unitary operation Ux , which depends on the received message
x, on his qubit.
EXERCISE 4.11 Let |ψ = a|00 + b|11 be a two-qubit state. Apply a

Hadamard gate to the first qubit and then measure the first qubit. Find the
second qubit state after the measurement corresponding to the outcome of
the first qubit measurement.
4.6 Universal Quantum Gates

It can be shown that any classical logic gate can be constructed by using a
small set of gates, AND, NOT and XOR, for example. Such a set of gates
is called the universal set of classical gates. Since the CCNOT gate can
simulate these classical gates, quantum circuits simulate any classical circuits.
It should be noted that the set of quantum gates is much larger than those
classical gates which can be simulated by quantum gates. Thus we want to
find a universal set of quantum gates from which any quantum circuits, i.e.,
any unitary matrix, can be constructed.
In the following, it will be shown that
(1) the set of single qubit gates and
(2) CNOT gate
form a universal set of quantum circuits (universality theorem).
We will prove the following Lemma before stating the main theorem. Let
us start with a definition. A two-level unitary matrix is a unitary matrix
which acts non-trivially only on two vector components. Suppose V is a two-
level unitary matrix. Then V has the same matrix elements as those of the
unit matrix except for certain four elements Vaa , Vab , Vba and Vbb . An example
of a two-level unitary matrix is
⎛ ∗ ⎞
α 0 0 β∗
⎜ 0 10 0 ⎟
V =⎜ ⎟
⎝ 0 0 1 0 ⎠ , (|α| + |β| = 1),
2 2
−β 0 0 α
where a = 1 and b = 4.
LEMMA 4.1 Let U be a unitary matrix acting on Cd . Then there are

N ≤ d(d − 1)/2 two-level unitary matrices U1 , U2 , . . . , UN such that
U = U 1 U 2 . . . UN . (4.46)
Proof. The proof requires several steps. It is instructive to start with the case
d = 3. Let ⎛ ⎞
ad g
U= b e⎝ h⎠
cf j
be a unitary matrix. We want to find two-level unitary matrices U1 , U2 , U3
such that
U3 U2 U1 U = I.
Then it follows that
U = U1† U2† U3† .
(Never mind the daggers! If Uk is two-level unitary, Uk† is also two-level

unitary.) We prove the above decomposition by constructing Uk explicitly.
(i) Let ⎛ ⎞
a∗ b∗
u u 0
U1 = ⎝−b a 0⎠,
u u
0 0 1

where u = |a|2 + |b|2 . Verify that U1 is unitary. Then we obtain
⎛ ⎞
a d g
⎝
U 1 U = 0 e h ⎠ ,
c f j
where a , . . . , j are some complex numbers, whose details are not necessary.
Observe that, with this choice of U1 , the first component of the second row
vanishes.
(ii) Let
⎛ a∗ ∗ ⎞ ⎛ ∗ ⎞
u 0 cu a 0 c∗
U2 = ⎝ 0 1 0 ⎠ = ⎝ 0 1 0 ⎠ ,

− uc 0 ua −c 0 a

where u = |a |2 + |c |2 = 1. Then
⎛ ⎞ ⎛ ⎞
1d g 1 0 0
U2 U1 U = ⎝ 0 e h ⎠ = ⎝ 0 e h ⎠ ,
0 f j 0 f j
where the equality d = g = 0 follows from the fact that U2 U1 U is unitary,
and hence the first row must be normalized.
(iii) Finally let ⎛ ⎞

1 0 0
U3 = (U2 U1 U )† = ⎝ 0 e∗ f ∗ ⎠ .
0 h∗ j ∗
Then, by definition, U3 U2 U1 U = I is obvious. This completes the proof for
d = 3.
Suppose U is a unitary matrix acting on Cd with a general dimension d.
Then by repeating the above arguments, we find two-level unitary matrices
U1 , U2 , . . . , Ud−1 such that
⎛ ⎞
1 0 0 ... 0
⎜0 ∗ ∗ ... ∗⎟
⎜ ⎟
Ud−1 . . . U2 U1 U = ⎜
⎜ 0 ∗ ∗ . . . ∗ ⎟,
⎟
⎝ ... ... ⎠
0 ∗ ∗ ... ∗
namely the (1, 1) component is unity and other components of the first row
and the first column vanish. The number of matrices {Uk } to achieve this
form is the same as the number of zeros in the first column, hence (d − 1).
We then repeat the same procedure to the (d − 1) × (d − 1) block unitary
matrix using (d−2) two-level unitary matrices. After repeating this, we finally
decompose U into a product of two-level unitary matrices
U = V1 V2 . . . VN ,
where N ≤ (d − 1) + (d − 2) + . . . + 1 = d(d − 1)/2.
EXERCISE 4.12 Let U be a general 4 × 4 unitary matrix. Find two-level

unitary matrices U1 , U2 and U3 such that
⎛ ⎞
1000
⎜0 ∗ ∗ ∗⎟
U3 U2 U1 U = ⎜ ⎟
⎝0 ∗ ∗ ∗⎠.
0∗∗∗
EXERCISE 4.13 Let

⎛ ⎞
1 1 1 1
1⎜ 1 i −1 −i ⎟
U= ⎜⎝
⎟. (4.47)
2 1 −1 1 −1 ⎠
1 −i −1 i
Decompose U into a product of two-level unitary matrices.

Let us consider a unitary matrix acting on an n-qubit system. Then this
unitary matrix is decomposed into a product of at most 2n (2n − 1)/2 =
2n−1 (2n − 1) two-level unitary matrices. Now we are in a position to state
the main theorem.
THEOREM 4.2 (Barenco et al.)[14] The set of single qubit gates and
CNOT gate are universal. Namely, any unitary gate acting on an n-qubit
register can be implemented with single qubit gates and CNOT gates.
Proof. We closely follow [1] for the proof here. Thanks to the previous
Lemma, it suffices to prove the theorem for a two-level unitary matrix. Let
U be a two-level unitary matrix acting nontrivially only on |s and |t ba-
sis vectors of an n-qubit system, where s = sn−1 2n−1 + . . . + s1 2 + s0 and
t = tn−1 2n−1 + . . .+ t1 2 + t0 are binary expressions for decimal numbers s and
t. This means that matrix elements Uss , Ust , Uts and Utt are different from
those of the unit matrix, while all the others are the same, where |s stands for
|sn−1 |sn−2 . . . |s0 , for example. We can construct Ũ , the non-trivial 2 × 2
unitary submatrix of U . Ũ may be thought of as a unitary matrix acting on
a single qubit, whose basis is {|s, |t}.
STEP 1: U is reduced to Ũ ∈ U(2).

The basis vectors |s and |t may be put together to form a basis for a
single qubit using the following trick. This is done by introducing Gray
codes. For two binary numbers s = sn−1 . . . s1 s0 and t = tn−1 . . . t1 t0 , a
Gray code connecting s and t is a sequence of binary numbers {g1 , . . . , gm }
where the adjacent numbers, gk and gk+1 , differ in exactly one bit. Moreover,
the sequence satisfies the boundary conditions g1 = s and gm = t.
Suppose s = 100101 and t = 110110, for example. An example of a Gray
code connecting s and t is
s = g1 = 100101
g2 = 11̂0101
g3 = 11011̂1
g4 = 110110̂ = t,
where the digit with ˆ has been renewed. It is clear from this construction
that if s and t differ in p bits, the shortest Gray code is made of p+1 elements.
It should be also clear that if s and t are of n digits, then m ≤ (n + 1) since
s and t differ at most in n bits.
With these preparations, we consider the implementation of U . The strat-
egy is to find gates providing the sequence of state changes
|s = |g1 → |g2 → . . . → |gm−1 . (4.48)
Then gm−1 and gm differ only in one bit, which is identified with the single
qubit on which Ũ acts. In the example above, we have |g3 = |11011 ⊗ |1
and |t = |g4 = |11011 ⊗ |0. Now the operator Ũ may be introduced so that
it acts on a two-dimensional subspace of the total Hilbert space, in which the
first five qubits are in the state |11011. Then we undo the sequence (4.48)
so that |gm−1 → |gm−2 → . . . → |g1 = |s. Each of these steps can be
easily implemented using simple gates that have been introduced previously
(see below).
Let us consider the following example of a three-qubit system, whose basis
is {|000, |001, . . . , |111}. Let
⎛ ⎞
a000000c
⎜0 1 0 0 0 0 0 0⎟
⎜ ⎟
⎜0 0 1 0 0 0 0 0⎟
⎜ ⎟
⎜0 0 0 1 0 0 0 0⎟
U =⎜ ⎜ ⎟ , (a, b, c, d ∈ C) (4.49)
0 0 0 0 1 0 0 0 ⎟
⎜ ⎟
⎜0 0 0 0 0 1 0 0⎟
⎜ ⎟
⎝0 0 0 0 0 0 1 0⎠
b000000d
be a two-level unitary matrix which we wish to implement. Note that U acts
non-trivially only in the subspace spanned by |000 and |111. The unitarity
FIGURE 4.5
Example of circuit implementing the gate U .
of U ensures that the matrix

ac
Ũ = (4.50)
bd
is also unitary. An example of a Gray code connecting 000 and 111 is
q1 q2 q3
g1 = 0 0 0
g2 = 1 0 0 (4.51)
g3 = 1 1 0
g4 = 1 1 1
Since g3 and g4 differ only in the third qubit, which we call q3 , we have to
bring g1 to g3 and then operate Ũ on the qubit q3 provided that the first and
the second qubits are in the state |11. (Namely we have a controlled-Ũ gate
with the target bit q3 and the control bits q1 and q2 .) After this controlled
operation is done, we have to put |g3 = |110 back to the state |000 as
|110 → |100 → |000.
This operation is graphically shown in Fig. 4.5. Here ◦ denotes the negated
control node. This means that the unitary gate acts on the target bit only
when the control bit is in the state |0. This is easily implemented by adding
two X gates as
It is easy to see that this gate indeed implements U . Suppose the input is
|101, for example. Figure 4.6 shows that the gate has no effect on this basis
vector since U should act as a unit matrix on this vector. The operation of U
FIGURE 4.6
U -gate has no effect on the vector |101.
on the input α|000 + β|111 is

⎛ ⎞⎛ ⎞ ⎛ ⎞
a000 000 c α αa + βc
⎜0 1 0 0 000 0⎟ ⎜ ⎟ ⎜ ⎟
⎜ ⎟⎜0⎟ ⎜ 0 ⎟
⎜0 0 1 0 000 ⎟ ⎜ ⎟
0⎟⎜ 0 ⎟ ⎜ ⎜ 0 ⎟
⎜ ⎟
⎜0 0 0 1 000 0⎟ ⎜0⎟ ⎜ 0 ⎟
U (α|000 + β|111) = ⎜ ⎟⎜ ⎟ = ⎜ ⎟. (4.52)
⎜0 0 0 0 100 0⎟ ⎜0⎟ ⎜ 0 ⎟
⎜ ⎟⎜ ⎟ ⎜ ⎟
⎜0 0 0 0 010 ⎟ ⎜ ⎟
0⎟⎜ 0 ⎟ ⎜ ⎜ 0 ⎟
⎜ ⎟
⎝0 0 0 0 001 0⎠⎝ 0 ⎠ ⎝ 0 ⎠
b000 000 d β αb + βd
If we use the circuit shown in Fig. 4.5, we produce the same result as shown
in Fig. 4.7
FIGURE 4.7
U -gate acting on α|000 + β|111 yields the desired output (aα + cβ)|000 +
(bα + dβ)|111.
This construction is easily generalized to any two-level unitary matrix U ∈

U(2n ). It will be shown below that all the gates in the above circuit can
be implemented with single-qubit gates and CNOT gates, which proves the
universality of these gates.
EXERCISE 4.14 (1) Find the shortest Gray code which connects 000 with
110.
(2) Use this result to find a quantum circuit, such as Fig. 4.5, implementing
a two-level unitary gate
⎛ ⎞
a00000c0
⎜0 1 0 0 0 0 0 0⎟
⎜ ⎟
⎜0 0 1 0 0 0 0 0⎟
⎜ ⎟
⎜0 0 0 1 0 0 0 0⎟ ac
⎜ ⎟
U =⎜ ⎟ , Ũ ≡ b d ∈ U (2).
⎜0 0 0 0 1 0 0 0⎟
⎜0 0 0 0 0 1 0 0⎟
⎜ ⎟
⎝ b 0 0 0 0 0 d 0⎠
00000001
You may use various controlled-NOT gates and controlled-Ũ gates.

STEP 2: Two-level unitary gates are decomposed into single-qubit gates and
CNOT gates.
A controlled-U gate can be constructed from at most four single-qubit gates
and two CNOT gates for any single-qubit unitary U ∈ U(2). Let us prove
several Lemmas before we prove this statement.
LEMMA 4.2 Let U ∈ SU(2). Then there exist α, β, γ ∈ R such that U =

Rz (α)Ry (β)Rz (γ), where
iα/2
e 0
Rz (α) = exp(iασz /2) = ,
0 e−iα/2

cos(β/2) sin(β/2)
Ry (β) = exp(iβσy /2) = .
− sin(β/2) cos(β/2)
Proof. After some calculation, we obtain
i(α+γ)/2
e cos(β/2) ei(α−γ)/2 sin(β/2)
Rz (α)Ry (β)Rz (γ) = . (4.53)
−ei(−α+γ)/2 sin(β/2) e−i(α+γ)/2 cos(β/2)
Any U ∈ SU(2) may be written in the form

a b cos θeiλ sin θeiμ
U= = , (4.54)
−b∗ a∗ − sin θe−iμ cos θe−iλ
where we used the fact that det U = |a|2 + |b|2 = 1. Now we obtain U =
Rz (α)Ry (β)Rz (γ) by making identifications
β α+γ α−γ
θ= ,λ = ,μ = . (4.55)
2 2 2
LEMMA 4.3 Let U ∈ SU(2). Then there exist A, B, C ∈ SU(2) such that
U = AXBXC and ABC = I, where X = σx .
Proof. Lemma 4.2 states that U = Rz (α)Ry (β)Rz (γ) for some α, β, γ ∈ R.
Let

β β α+γ α−γ
A = Rz (α)Ry , B = Ry − Rz − , C = Rz − .
2 2 2 2
Then

β β α+γ α−γ
AXBXC = Rz (α)Ry XRy − Rz − XRz −
2 2 2 2

β β α+γ α−γ
= Rz (α)Ry XRy − X XRz − X Rz −
2 2 2 2

β β α+γ α−γ
= Rz (α)Ry Ry Rz Rz −
2 2 2 2
= Rz (α)Ry (β)Rz (γ) = U,
where use has been made of the identities X 2 = I and Xσy,z X = −σy,z .
It is also verified that

β β α+γ α−γ
ABC = Rz (α)Ry Ry − Rz − Rz −
2 2 2 2
= Rz (α)Ry (0)Rz (−α) = I.
This proves the Lemma.
FIGURE 4.8
Controlled-U gate is made of at most three single-qubit gates and two CNOT
gates for any U ∈ SU(2).
LEMMA 4.4 Let U ∈ SU(2) be factorized as U = AXBXC as in the

previous Lemma. Then the controlled-U gate can be implemented with at
most three single-qubit gates and two CNOT gates (see Fig. 4.8).
Proof. The proof is almost obvious. When the control bit is 0, the target bit
|ψ is operated by C, B and A in this order so that
|ψ → ABC|ψ = |ψ,
while when the control bit is 1, we have
|ψ → AXBXC|ψ = U |ψ.
So far, we have worked with U ∈ SU(2). To implement a general U -gate

with U ∈ U(2), we have to deal with the phase. Let us first recall that any
U ∈ U(2) is decomposed as U = eiα V, V ∈ SU(2), α ∈ R.
LEMMA 4.5 Let

iφ eiφ 0
Φ(φ) = e I =
0 eiφ
and
−iφ/2 iφ/2
φ e 0 e 0 1 0
D = Rz (−φ)Φ = = .
2 0 eiφ/2 0 eiφ/2 0 eiφ
Then the controlled-Φ(φ) gate is expressed as a tensor product of single qubit

gates as
UCΦ(φ) = D ⊗ I. (4.56)
.
Proof. The LHS is
UCΦ(φ) = |00| ⊗ I + |11| ⊗ Φ(φ) = |00| ⊗ I + |11| ⊗ eiφ I

= |00| ⊗ I + eiφ |11| ⊗ I,
while the RHS is

1 0
D⊗I = ⊗I
0 eiφ

= |00| + eiφ |11| ⊗ I = UCΦ(φ) ,
which proves the lemma.

Figure 4.9 shows the statement of the above lemma.
EXERCISE 4.15 Let us consider the controlled-V1 gate UCV1 and the
controlled-V2 gate UCV2 . Show that the controlled-V1 gate followed by the
controlled-V2 gate is the controlled-V2 V1 gate UC(V2 V1 ) as shown in Fig. 4.10.
FIGURE 4.9
Equality UCΦ(φ) = D ⊗ I.
FIGURE 4.10
Equality UCV2 UCV1 = UC(V2 V1 ) .
Now we are ready to prove the main proposition.
PROPOSITION 4.1 Let U ∈ U(2). Then the controlled-U gate UCU can
be constructed by at most four single-qubit gates and two CNOT gates.
Proof. Let U = Φ(φ)AXBXC. According to the exercise above, the

controlled-U gate is written as a product of the controlled-Φ(φ) gate and the
controlled-AXBXC gate. Moreover, Lemma 4.5 states that the controlled-
Φ(φ) gate may be replaced by a single-qubit phase gate acting on the first
qubit. The rest of the gate, the controlled-AXBXC gate is implemented with
three SU(2) gates and two CNOT gates as proved in Lemma 4.3. Therefore
we have the following decomposition:
UCU = (D ⊗ A)UCNOT (I ⊗ B)UCNOT (I ⊗ C), (4.57)
where
D = Rz (−φ)Φ(φ/2)
and use has been made of the identity (D ⊗ I)(I ⊗ A) = D ⊗ A.
Figure 4.11 shows the statement of the proposition.
STEP 3: CCNOT gate and its variants are implemented with CNOT gates
and their variants.
Now our final task is to prove that controlled-U gates with n − 1 control
bits are also constructed using single-qubit gates and CNOT gates. Let us
start with the simplest case, in which n = 3.
FIGURE 4.11
Controlled-U gate is implemented with at most four single-qubit gates and
two CNOT gates.
FIGURE 4.12
Controlled-controlled-U gate is equivalent to the gate made of controlled-V
gates with U = V 2 and CNOT gates.
LEMMA 4.6 The two quantum circuits in Fig. 4.12 are equivalent, where
U = V 2.
Proof. If both the first and the second qubits are 0 in the RHS, all the gates
are ineffective and the third qubit is unchanged; the gate in this subspace
acts as |0000| ⊗ I. In case the first qubit is 0 and the second is 1, the
third qubit is mapped as |ψ → V † V |ψ = |ψ; the gate is then |0101| ⊗ I.
When the first qubit is 1 and the second is 0, the third qubit is mapped as
|ψ → V V † |ψ = |ψ; hence the gate in this subspace is |1010| ⊗ I. Finally
let both the first and the second qubits be 1. Then the action of the gate on
the third qubit is |ψ → V V |ψ = U |ψ; namely the gate in this subspace is
|1111| ⊗ U . Thus it has been proved that the RHS of Fig. 4.12 is
(|0000| + |0101| + |1010|) ⊗ I + |1111| ⊗ U, (4.58)
namely the controlled-controlled-U gate.
This decomposition is explained intuitively as follows. The first V operates

on the third qubit |ψ if and only if the second qubit is 1. V † is in action
if and only if x1 ⊕ x2 = 1, where xk is the input bit of the kth qubit. The
second V operation is applied if and only if the first qubit is 1. Thus the
action of this gate on the third qubit is V 2 = U only when x1 ∧ x2 = 1 and
FIGURE 4.13
Decomposition of the C3 U gate.
I otherwise. This intuitive picture is of help when we implement the U gate

with more control qubits.
EXERCISE 4.16 Prove Lemma 4.6 by writing down the action of each gate
in the RHS of Fig. 4.12 explicitly using bras, kets and I, U, V, V † . (For exam-
ple, UCNOT = |00| ⊗ I + |11| ⊗ X for a two-qubit system.)
A simple generalization of the above construction is applied to a controlled-

U gate with three control bits as the following exercise shows.
EXERCISE 4.17 Show that the circuit in Fig. 4.13 is a controlled-U gate
with three control bits, where U = V 2 .
Now it should be clear how these examples are generalized to gates with
more control bits.
PROPOSITION 4.2 The quantum circuit in Fig. 4.14 with U = V 2 is a

decomposition of the controlled-U gate with n − 1 control bits.
The proof of the above proposition is very similar to that of Lemma 4.6
and Exercise 4.17 and is left as an exercise to the readers.
Theorem 4.2 has been now proved.
Other types of gates are also implemented with single-qubit gates and the
CNOT gates. See Barenco et al. [14] for further details. A few remarks are in
order. The above controlled-U gate with (n − 1) control bits requires Θ(n2 )
elementary gates.∗† Let us write the number of the elementary gates required
∗ We call single-qubit gates and the CNOT gates elementary gates from now on.
† We will be less strict in the definition of “the order of.” In the theory of computational
complexity, people use three types of “order of magnitude.” One writes “f (n) is O(g(n))”
if there exist n0 ∈ N and c ∈ R such that f (n) ≤ cg(n) for n ≥ n0 . In other words, O sets
the asymptotic upper bound of f (n). A function f (n) is said to be Ω(g(n)) if there exist
FIGURE 4.14
Decomposition of the C(n−1) U gate. The number on the top denotes the layer
refered to in the text.
to construct the gate in Fig. 4.14 by C(n). Construction of layers I and III
requires elementary gates whose number is independent of n. It can be shown
that the number of the elementary gates required to construct the controlled
NOT gate with (n − 2) control bits is Θ(n) [14]. Therefore layers II and IV
require Θ(n) elementary gates. Finally the layer V, a controlled-V gate with
(n − 2) control bits, requires C(n − 1) basic gates by definition. Thus we
obtain a recursion relation
C(n) − C(n − 1) = Θ(n). (4.59)
The solution to this recursion relation is
C(n) = Θ(n2 ). (4.60)
Therefore, implementation of a controlled-U gate with U ∈ U(2) and (n − 1)

control bits requires Θ(n2 ) elementary gates.
n0 ∈ N and c ∈ R such that f (n) ≥ cg(n) for n ≥ n0 . In other words, Ω sets the asymptotic
lower bound of f (n). Finally f (n) is said to be Θ(f (n)) if f (n) behaves asymptotically as
g(n), namely if f (n) is both O(g(n)) and Ω(g(n)).
4.7 Quantum Parallelism and Entanglement

Given an input x, a typical quantum computer computes f (x) in such a way
as
Uf : |x|0 → |x|f (x), (4.61)
where Uf is a unitary matrix that implements the function f .
Suppose Uf acts on the input which is a superposition of many states. Since
Uf is a linear operator, it acts simultaneously on all the vectors that constitute
the superposition. Thus the output is also a superposition of all the results;

Uf : |x|0 → |x|f (x). (4.62)
x x
Namely, when the input is a superposition of n states, Uf computes n values

f (xk ) (1 ≤ k ≤ n) simultaneously. This feature, called the quantum paral-
lelism, gives a quantum computer an enormous power. A quantum computer
is advantageous compared to a classical counterpart in that it makes use of
this quantum parallelism and also entanglement.
A unitary transformation acts on a superposition of all possible states in
most quantum algorithms. This superposition is prepared by the action
of the Walsh-Hadamard transformation on an n-qubit register in the state
|00 . . . 0 = |0 ⊗ |0 ⊗ . . . ⊗ |0 resulting in
n
2 −1
1 1
√ (|00 . . . 0 + |00 . . . 1 + . . . |11 . . . 1) = √ |x. (4.63)
2n 2n x=0
This state is a superposition of vectors encoding all the integers between 0

and 2n − 1. Then the linearity of Uf leads to
2n −1
2n −1 2n −1
1 1 1
Uf √ |x|0 = √ Uf |x|0 = √ |x|f (x). (4.64)
2n x=0 2n x=0 2n x=0
Note that the superposition is made of 2n = en ln 2 states, which makes quan-

tum computation exponentially faster than the classical counterpart in a cer-
tain kind of computation.
What about the limitation of a quantum computer? Let us consider the
CCNOT gate, for example. This gate flips the third qubit if and only if the
first and the second qubits are both in the state |1, while it leaves the third
qubit unchanged otherwise. Let us fix the third input qubit to |0. It was
shown in §4.3.3 that the third output is |x ∧ y, where |x and |y are the first
and the second input qubit states, respectively. Suppose the input state is a
superposition of all possible states while the third qubit is fixed to |0. This
can be achieved by the Walsh-Hadamard transformation as

1 1
UH |0 ⊗ UH |0 ⊗ |0 = √ (|0 + |1) ⊗ √ (|0 + |1) ⊗ |0
2 2
1
= (|000 + |010 + |100 + |110). (4.65)
2
By operating CCNOT on this state, we obtain
1
UCCNOT (UH |0 ⊗ UH |0 ⊗ |0) = (|000 + |010 + |100 + |111). (4.66)
2
This output may be thought of as the truth table of AND: |x, y, x ∧ y. It
is extremely important to note that the output is an entangled state and the
measurement projects the state to one line of the truth table, i.e., a single
term in the RHS of Eq. (4.66). The order of the measurements of the three
qubits does not matter at all. The measurement of the third qubit projects
the state to the superposition of the states with the given value of the third
qubit. Repeating the measurements on the rest of the qubits leads to the
collapse of the output state to one of |x, y, x ∧ y.
There is no advantage of quantum computation over classical at this stage.
This is because only one result may be obtained by a single set of measure-
ments. What is worse, we cannot choose a specific vector |x, y, x ∧ y at our
will! Thus any quantum algorithm should be programmed so that the partic-
ular vector we want to observe should have larger probability to be measured
compared to other vectors. This step has no classical analogy and is very
special in quantum computation. The programming strategies to deal with
this feature are [2]
1. to amplify the amplitude, and hence the probability, of the vector that
we want to observe. This strategy is employed in the Grover’s database
search algorithm.
2. to find a common property of all the f (x). This idea was employed
in the quantum Fourier transform to find the order‡ of f in the Shor’s
factoring algorithm.
Now we consider the power of entanglement. Suppose we have an n-qubit
register, whose Hilbert space is 2n -dimensional. Since each qubit has two basis
vectors |0 and |1, there are 2n basis vectors (n |0’s and n |1’s) involved to
span this 2n -dimensional Hilbert space. Imagine that we have a single quan-
tum system, instead, which has the same Hilbert space. One might think
that the system may do the same quantum computation as the n-qubit reg-
ister does. One possible problem is that one cannot measure the “kth digit”
‡ Let m, N ∈ N (m < N ) be numbers coprime to each other. Then there exists P ∈ N such
that mP ≡ 1 (mod N ). The smallest such number P is called the period or the order.
It is easily seen that mx+P ≡ mx (mod N ), ∀x ∈ N.
leaving other digits unaffected. Even worse, consider how many different basis
vectors are required for this system. This single system must have an enor-
mous number, 2n , of basis vectors! Let us consider 20 spin-1/2 particles in
a magnetic field. We can employ the spin-up and spin-down energy eigen-
states of each particle as the qubit basis vectors. Then there are merely 40
energy eigenvectors involved. Suppose we use energy eigenstates of a certain
molecule to replace this register. Then we have to use 220 ∼ 106 eigenstates.
Separation and control of so many eigenstates are certainly beyond current
technology. These simple consideration shows that multipartite implemen-
tation of a quantum algorithm requires an exponentially smaller number of
basis vectors than monopartite implementation since the former makes use of
entanglement as a computational resource.
References
[1] M. A. Neilsen and I. L. Chuang, Quantum Computation and Quantum
Information, Cambridge University Press (2000).
[2] E. Riefell and W. Polak, ACM Computing Surveys (CSUR) 32, 300
(2000).
[3] Y. Uesaka, Mathematical Principle of Quantum Computation, Corona
Publishing, Tokyo, in Japanese (2000).
[4] W. K. Wootters and W. H. Zurek, Nature 299, 802 (1982).
[5] D. Dieks, Phys. Lett. A 92, 271 (1982).
[6] D. Bouwmeester et al., Nature 390, 575 (1997).
[7] D. Boschi et al., Phys. Rev. Lett. 80, 1121 (1998).
[8] I. Marcikic et al., Nature 421, 509 (2003).
[9] R. Ursin et al., Nature 430, 849 (2004).
[10] A. Furusawa et al., Science 282, 706 (1998).
[11] M. A. Nielsen et al., Nature 396, 52 (1998).
[12] M. Riebe et al., Nature 429, 734 (2004).
[13] M. D. Barret et al., Nature 429, 737 (2004).
[14] A. Barenco et al., Phys. Rev. A 52, 3457 (1995).
Chapter 9
Superconducting
Quantum Computing
Devices
• Superconductivity history
• Components of superconducting circuits
• Quantization of superconducting circuits
• Types of qubits: charge, flux, phase and charge-flux
• Universality of quantum gates
• Measurements
Superconductivity manifests macroscopic quantum phenomena. A super-
conducting circuit composed of Josephson junctions, Cooper pair boxes, and
rf-/dc-SQUID, properly miniaturized, becomes quantized and demonstrates
Rabi oscillations and entanglement. In this chapter, we begin with an in-
troduction of the history and elementary theory of superconductivity. Then
we describe the building blocks of superconducting classical circuits and
derive their canonical quantizations. The set up of qubits and supercon-
ducting quantum logic gates are then examined. Finally, ways to make
measurements are discussed. We should remark that SQUID are widely
regarded as the most scalable quantum computing device.
9.1 Introduction
Even though quantum effects are mostly observed in microscopic scales,
they also manifest macroscopically. A particular case of such is supercon-
ductivity. Superconducting devices composed of Josephson junctions (JJ),
407
408 CHAPTER 9. SUPERCONDUCTING DEVICES
Cooper-pair boxes and SQUID (superconducting quantum interference de-

vices) have been developed since the 1980s as magnetometers, gradiome-
ters, gyroscopes, sensors, transistors, voltmeters, etc., to perform measure-
ments on small magnetic fields, and to demonstrate the quantum effects
of tunneling, resonance and coherence [6, 11, 18, 27, 30, 35]. Many in-
dustrial and medical applications have also resulted: maglev trains, super-
conducting power generator, cables and transformers, MRI and NMR for
medical scans, to mention a few. With the advances in solid-state lithogra-
phy and thin-film technology, superconducting devices have the great ad-
vantage of being easily scalable and engineering-designable. For a bulk
superconductor, if its size is reduced smaller and smaller, then the quasi-
continuous electron conduction band therein turns into discrete energy lev-
els. In principle, such energy levels can be used to constitute a qubit.
The first demonstration of quantum-coherent oscillations of a Josephson
“charge qubit” in a superposition of eigenstates was made by Nakamura, et
al. [20] in 1999. Ever since, theoretically and experimentally there has been
steady progress. New proposals for qubits based on charges, flux, phase and
charge-flux have been made, with observations of microwave-induced Rabi
oscillations of 2-level populations in those qubit systems [8, 9, 10, 37, 38].
The organization of this chapter is made as follows: we will first intro-
duce superconductivity in Section 9.2, the Josephson junction in Section
9.3, and the elementary superconducting circuits in Section 9.4. Supercon-
ducting quantum circuits and gates are studied in Sections 9.5 and 9.6, and
conclude with measurements in Section 9.7.
9.2 Superconductivity
We begin by giving a brief historical account [13, 23, 33]. Superconductiv-
ity was discovered in 1911 by the Dutch physicist Heike Kamerlingh Onnes
(1853–1926), who dedicated his career to the exploration of extremely cold
refrigeration. In 1908, he successfully liquefied helium by cooling it to
−452◦ F (4 K). In 1911, he began the investigation of the electrical prop-
erties of metals in extremely cold temperatures, using liquid helium. He
noticed that for solid mercury at cryogenic temperature of 4.2 K, its elec-
tric resistivity abruptly disappeared (as if there were a jump discontinuity).
This is the discovery of superconductivity, and Onnes was awarded the No-
bel Prize of Physics in 1913.
Subsequently, superconductivity was found in other materials. For ex-
ample, lead was found to superconduct at 7 K, and (in 1941) niobium nitride
was found to superconduct at 16 K.
Important understanding of superconductivity was made by Meissner
and Ochsenfeld in 1933 who discovered that superconductors expelled ap-
plied magnetic fields, a phenomenon which has come to be known as the
Meissner effect. In 1935, F. and H. London showed that the Meissner effect
was a consequence of the minimization of the electromagnetic free energy
Chapter 2
Application Areas
2.1 General Reversible Computing Problem . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2 Energy-Optimal Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Parallel Computing and Synchronization . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.1 Asynchronous Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.2 Supercriticality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.3 Performance Effects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Processor Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4.1 Speculative Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4.2 Very Large Instruction Word . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4.3 Anti-Memoization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5 Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.6 Source Code Control Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.7 Fault Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.8 Fault Tolerance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.9 Database Transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.10 Quantum Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.11 Additional Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1 General Reversible Computing Problem

At a high level, the challenge of reversible computing may be stated as follows:
Given a program, the program must be executed in such a way that its forward
progress could be paused at any moment and the direction of its execution can
be reversed to retrace its previous steps exactly. The backward execution can
also be paused at any moment and the forward execution of the program can
be resumed. This ability to pause the forward or backward execution at any
point and the ability to switch the direction of execution is the generalized
challenge of reversible computing. Specific variants and specializations of this
general reversible computing problem arise in different contexts. Historically,
low power computing has been a major motivating factor behind the devel-
opment of reversible computing. Over time, additional areas have emerged in
which reversible computing has found applications.
9
10 Introduction to Reversible Computing
2.2 Energy-Optimal Computing

When contemplating ways to reduce the energy consumed to accomplish a cer-
tain computation, the thought process naturally leads to the determination
of the fundamental lower bound for the same. In this process, it was dis-
covered that the theoretical lower bound on energy is directly related to the
reversibility of computation [Landauer, 1961]. More precisely, there are ways
in which the original (forward) computation could be relaxed into a more gen-
eralized setting of reversible computing, (these ideas are elaborated more later
in Chapter 4 and Chapter 5). Arguments based on thermodynamics helped
keep the treatment beyond any specific hardware technologies [Bennett, 2003].
In an ideal setting, it was shown that no energy need be fundamentally lost
in performing any given computation [Bennett, 1973, 1982]. As a corollary,
this implies that, in theory, arbitrarily large fractions of the energy consumed
for a computation should be recoverable for useful work again, although there
would be an underlying trade-off between the efficiency of such recovery and
the speed of computation (i.e., computation time approaches infinity as the
recoverable fraction approaches unity). Based on the thermodynamics of com-
putation, various hardware technologies have been proposed, designed, and
explored, and some have even been implemented as proofs of concept [Ren
and Semenov, 2011].
The theory about the minimality of energy spent for computation is built
over the most basic bit operation, namely bit erasure (e.g., resetting a bit to
0 independent of whether its current bit value is 0 or 1 [Bub, 2001]). First,
it is argued that bit erasure is the only operation that fundamentally con-
sumes energy in any computation. An equivalent way of saying the same is
the following: any computation can be carried out in such a way that only
the bit erasures performed as part of that computation consume irrecoverable
energy, while the energy used in all other bit operations is fully recoverable
and reusable.
Given that the bit erasures form the sole cause of irrecoverable energy
consumption, the important question that follows is whether every compu-
tation can be performed without bit erasures. This question was answered
in the positive by introducing reversible computing. A notion of the reverse
of any computation is introduced, which is then used in a higher-level algo-
rithm to accomplish any computation without bit erasures (see Chapter 4 and
Chapter 6). In this way, the reduction and recycling of energy is one of the fun-
damental applications of reversible computing, holding far-reaching potential
in the future of computing.
Application Areas 11
2.3 Parallel Computing and Synchronization

Reversible computing finds use in addressing some of the challenges in large-
scale parallel computing such as reduction of synchronization overheads and
increasing the concurrency dynamically. As of this writing, parallel computers
with millions of processing units is a reality [TOP500.org, 2013], and the scale
is only envisioned to increase in the future.
Synchronization is that critical aspect of parallel computation which en-
sures that the overall execution obeys and incorporates all the inter-processor
data dependencies of the application [Grama et al., 2003, Raynal, 2012]. A
runtime component of parallel computing is needed in all applications to
realize proper synchronization, and this runtime synchronization costs the
application some wasted processing time (also called blocked time) at some
processors during different periods of execution. Some of this synchronization
is fundamental in nature, in the sense that the inter-processor data dependen-
cies impose a theoretical total parallel execution time (given by critical path
analysis). However, this lower bound is often difficult to achieve in practice,
and the programs are written with very conservative order of execution. For
example, global barriers are invoked in the program to ensure all processors
reach known points in the program before proceeding further. The cost for
each such synchronization operation becomes significantly large as the num-
ber of processors increases, with some applications spending more than 50%
of their time in synchronization versus actual, useful computation.
Note that any synchronization operation is pure overhead, in the sense that
it only adds a component of execution time (and energy) that is simply absent
in sequential computation. The synchronization problem is an important issue
at the highest scales of hardware, despite some advances in underlying network
hardware technologies to speed up the synchronization operations themselves.
2.3.1 Asynchronous Computing

The synchronization problem can be solved by finding ways to increase con-
currency across processors such that there is increasingly more useful compu-
tation performed per synchronization operation. One approach is to incremen-
tally reorganize operations to overlap some computation with communication
or synchronization operations. The more general method is to use a relaxation
to a generalized asynchronous reversible execution, allowing the application
to uncover maximum concurrency at runtime.
Computation–communication overlap One specialized way to in-
crease concurrency is by using non-blocking synchronization operations,
by which processors perform some local operation while a synchroniza-
tion operation is in progress. For example, non-blocking collective op-
erations such as global barriers or global reductions may be initiated
and completed asynchronously. However, the amount of increased con-

currency uncovered by this approach is limited to the amount of local
computation that can be performed during synchronization.
Generalized asynchronous reversible execution A generalized way
to increase concurrency is to relax the parallel execution model to one
in which all processors can execute the application both forward and
backward, and let processors execute local computation asynchronously
with respect to each other. Communication and synchronization proceed
in the background, and any violations of data dependency order are
detected at runtime and corrected by relying on reversible execution.
Executing backward, the processor is rolled back from its current point of
execution to the point of dependency violation, and, after incorporating
the correction (e.g., new data arriving from another processor), forward
execution is restarted from the corrected point.
In the specialized communication–computation overlap approach, execu-

tion follows conventional computation, that is, it is still fundamentally forward
execution-based, with no tolerance for any data dependency violation. In the
generalized asynchronous reversible execution, the view of execution is fun-
damentally different, that is, execution is assumed to be reversible from the
outset, with a runtime component (supervisor, coordinator, controller, or en-
gine) orchestrating the global execution such that the overall execution even-
tually provides the same answers as one that incorporated all inter-processor
data dependencies. Without reversibility, it is not possible to relax execution
to uncover any more concurrency than the most conservative one that avoids
even transient violations of dependencies.
The best demonstrations of the potential for the reversible execution to
reduce synchronization overheads in large-scale parallel computing has been
in the area of parallel discrete event simulation (PDES). The Time Warp al-
gorithm [Jefferson, 1985] for PDES has been gainfully employed in multiple
large-scale applications (e.g., epidemiological outbreak simulations) using roll-
back-based synchronization implemented on supercomputers. The algorithm
is built on relaxation to a reversible execution, in which local events at a pro-
cessor are processed optimistically even while lower bound guarantees on the
global virtual time are being computed across all processors. Also, theoretical
analyses have been performed to show the gains with rollback dynamics in the
presence of primary and secondary rollbacks in Time Warp [Akyildiz et al.,
1992].
2.3.2 Supercriticality
Critical Path (CP) analysis of a parallel application is the determination of
the inherently sequential path(s) of data dependencies from the start to end
of the computation [Yang and Miller, 1988, Hollingsworth, 1998]. Clearly, the
longest path from start to end is the most critical one. It is well-known that the
critical path(s) in any application determine(s) a fundamental lower bound on

the parallel application’s total computation time. In particular, CP imposes
an absolute upper bound on the achievable parallel efficiency or speedup. How-
ever, an important aspect about this CP-bounded parallel efficiency is that
it rests on the fundamental assumption of conventional forward-only (irre-
versible) computation. If the assumption of irreversibility is relaxed, and the
lower bound is examined with a new assumption of reversible execution, it is
in fact possible to sometimes exceed the theoretical CP-based lower bound on
computation time (and, consequently, upper bound on parallel efficiency and
speedup).
To illustrate, suppose computations appear as a sequence of updates, of
the form
Uij : xi ← fj (Rij ),
where xi is a variable being updated, Rij is the set of all variables that xi
depends on for update j, and fj is a computable expression on that set of
variables. In normal execution, the exact values of all variables in Rij should
be available before the update can be performed. In this model, the chain of
these dependencies gives the CP-bounded computation time.
Now, consider the new computation model in which the computation is
relaxed to be reversible, i.e., fj−1 exists and is available for every j. In this
reversible model, suppose Uij is computed without waiting for the most re-
∗
cent values of Rij . After this out-of-order update, when new values Rij for
Rij are available, the correct new value for xi must be recomputed. This is
accomplished by first invoking fj−1 , then incorporating Rij ∗
, and finally re-
computing Uij . This reversal and recomputation can reduce synchronization
effects via reversible execution, yet it does not defeat the fundamental critical
path-based lower bound on computation time.
To improve the execution beyond the CP limit, consider the following
∗
variation: when new values Rij of Rij are received, a temporary value x∗i =
∗
fj (Rij ) is first computed and compared with the current value of xi that was
computed out of order. If they are equal, that is, if xi = x∗i , then there is no
need to overwrite/update xi because it already has the correct value. There
are two extremely important implications of this obviation of update to xi :
No succeeding nodes in the dependency graph will need updates, that
is, no Uik , j < k, needs to be recomputed (in case they have already
been computed).
Due to computation of Uij ahead of its position in the dependency graph,
its computation is overlapped with other preceding computations Uik for
some k < j, thereby reducing the overall completion time of the graph.
This phenomenon of the potential to defeat the lower bound dictated by the
critical path is called supercriticality [Jefferson and Reiher, 1991]. It not only
preserves the correctness of the final answer, but, more importantly, defeats
the lower bound on computation time if Uij is in the critical path of the over-
all computation Note that supercriticality is only possible due to reversible
execution. In the example, if xi is not equal to x∗i , then f −1 would have to
be invoked to correct the execution to conform to the dependencies. Thus,
reversible computing can be used to sometimes provide supercritical paral-
lel computation that exceeds the parallel efficiency and speedup otherwise
prescribed by the critical path.
2.3.3 Performance Effects

When reversibility is introduced to relieve synchronization costs, the program
must be instrumented to enable forward as well as backward modes of compu-
tation. Two broad approaches are (1) saving copies of variables to a memory
trace before they are modified in the forward mode and copying back from
the trace in reverse mode, or (2) avoid saving values of variables in forward
mode, but instead invoke inverses of individual operations in reverse mode.
In hardware technologies that have high memory latencies (i.e., time taken
to read from or write to memory locations) compared to speed of compu-
tation (such as computing arithmetic operations), it is vastly more efficient
to perform inverse computations rather than store and retrieve values from
memory.
The so-called “memory wall” being faced in the 2000s-2010s exhibits this
situation in which the increasing speeds of central processing units (CPUs)
make memory operations relatively very expensive. This is because of the in-
creasing ratio of CPU clock rates compared to those of memory units, and also
because of multi-core technologies that result in an increase in the number of
CPUs accessing the same number of memory units. This widening gap be-
tween the speeds of arithmetic/logic operations and memory storage/retrieval
operations can be bridged via reversible computing.
Operationally, the performance differences manifest themselves in terms
of memory behavior such as caching effects at all levels (L1, L2, L3), and
Translation Look-aside Buffer (TLB) effects. Memory-based (checkpointing)
reversal suffers from the following drawbacks: (1) the total amount of memory
needed for the reversible program is larger than that without reversible execu-
tion; (2) the time cost of copying values before being modified in the forward
mode adds to the forward execution overhead, potentially slowing down for-
ward execution; and (3) memory subsystem behavior (cache and TLB) can be
negatively impacted due to decrease in locality and due to memory accesses
spilling over cache size limits. Computation-based reversal can relieve these
drawbacks because (1) little additional memory is needed for reversal of arith-
metic operations; (2) the forward code is largely unaffected, thus retaining the
original forward execution speed; and (3) memory subsystem effects are not
significantly altered from the original forward mode.
2.4 Processor Architectures

In processor architecture technology, the need for reversible execution arises
in two distinct ways: (1) speculative execution, and (2) very large instruction
word. In both cases, reversible execution is used to correctly uncover dynamic
parallelism from an otherwise sequentially specified computation.
2.4.1 Speculative Execution

Consider a single sequence of instructions S =< . . . , Ii , . . . > being fetched,
decoded, and executed by a processor. In general, instruction Ii must be ex-
ecuted only after all instructions Ij , j < i are completed, because the set of
variables Ii depends on may be modified by those prior instructions. How-
ever, such dependency may not always be actually present in a small window
of the sequence, and some of the instructions may be safely processed concur-
rently without waiting for the others to finish. For example, I1 = a ← b × c
and I2 = d ← e + f can be processed concurrently even if specified sequen-
tially because there is no intersection of variables being read or modified.
More complex instances involve implied dependencies such as from array op-
erations, dereferences, and register conflicts. The problem is that the correct
execution order cannot be determined statically, a priori. In general, the set
of variables being modified by an instruction is not necessarily known until it
is actually decoded and executed (e.g., when indirect references such as array
indices or pointers are used to refer to the variable being read or modified).
Thus, there is a conflict between the possibility of executing a few instructions
concurrently to increase the overall processing speed and the possibility of the
concurrently executed instructions incorrectly affecting each other that might
result in wrong results.
A way to dynamically exploit the potential concurrency is via specula-
tive execution in which a later instruction is issued even before the earlier
instructions are completed [Dubois et al., 2012]. After the speculatively exe-
cuted instruction is executed, conflict detection is performed to see whether
there was an intersection in the set of affected variables (i.e., a violation in
read/write dependencies). If a conflict is detected, the results of the specula-
tively executed instruction are quashed and that instruction is restarted from
the beginning. Alternatively, fix-up code may be invoked to repair the incor-
rectly (speculatively) computed results, instead of discarding everything and
restarting the speculatively executed instructions from scratch. A fair amount
of processor infrastructure and compiler support is usually needed to accom-
plish speculative execution. For example, at the processor-level, instruction
execution must be relaxed so that modifications to registers are held in tem-
porary (shadow) registers for every speculatively executed instruction, and
the changes are committed from the temporary to actual registers only when
conflict resolution succeeds. Reverse computation could be used to avoid these

temporary registers by invoking an inverse instruction to restore the affected
register value if the speculative instruction was found to be conflicting. Spec-
ulative execution is widely used in many modern processors to increase the
processor instruction throughput.
2.4.2 Very Large Instruction Word

In a manner complementary to speculative execution, suppose each instruc-
tion Ii is in fact a vector of sub-instructions, Ii = [si1 , . . . , sij , . . . , sin ], where
the sub-instructions sij can all be processed concurrently to constitute the ex-
ecution of Ii . Because the number of sub-instructions can be large, the width
of each instruction becomes large, giving the name Very Large Instruction
Word (VLIW) [Fisher, 1983, Dubois et al., 2012]. Determination of which
sub-instructions are possible to execute as an aggregate instruction is accom-
plished within the compiler that generates the VLIW code. While the processor
is responsible for determining the concurrency and reversal of instructions in
speculative execution systems, the compiler is responsible to determine the
concurrency and reversal of sub-instructions in VLIW systems. The VLIW
compiler attempts to generate instructions that have a dense packing of sub-
instructions; however, it may have to reorder sub-instructions in generating
such dense packings. The compiler is then responsible for generating com-
pensation code that reverses the effects of incorrectly (speculatively) ordered
sub-instructions if they result in data conflicts at runtime. The most well-
known packing method is the Trace Scheduling approach [Fisher, 1981, 1983]
in which the path taken by the code in an execution is used to generate the
basic instruction sequence (independent of branch conditions), and reversal or
compensatory code is added to this sequence to recover from deviations from
the assumed path.
2.4.3 Anti-Memoization
A form of reversible computing can be employed in recovering temporary val-
ues that are usually pushed from registers to main memory when a register
conflict occurs (due to register file size limitation or due to named registers
being reused and overwritten across operations). If a register value is poten-
tially about to be lost, it is usually pushed to memory and later loaded back
from memory when it is again needed/used. Because memory operations are
orders of magnitude slower than register speeds, it is desirable to keep op-
erations confined to register accesses as much as possible. Thus, when the
intermediate value that is lost in a register (due to being overwritten) is again
needed, it is sometimes possible to either recompute or reverse compute ear-
lier operations to recover the lost register value, instead of relying on storage
to/retrieval from main memory.
A generalization of such memory versus computation trade-off is the con-
cept of memoization and anti-memoization. The method of storing the value

of an intermediate computation in memory for reuse in later computation is
called memoization [Hoffmann, 1992] (note that the term memoization is dif-
ferent from memorization). Such an optimization that trades off memory for
computation arises either from explicit programmer intent or from automation
techniques such as code generation by compilers. While memoization works
best when memory is cheaper than recomputation, it can in fact degrade per-
formance compared to recomputation when memory access cost is much higher
than recomputation cost. However, if the code has already been written using
memoization, the memoized values must be recovered using recomputation.
This can be done via reverse computing to the most recent position at which
the variable was last stored to memory, and then recomputing the expression
that led to the stored value. We call this approach anti-memoization, which is
the process of undoing memoization. An instance of this high-level approach
has been applied at the level of register value recovery (called register remate-
rialization) [Bahi and Eisenbeis, 2011, 2012] to improve the overall application
performance.
2.5 Debugging
Reversibility of execution is very useful in the process of debugging programs
in an efficient and convenient fashion. When running a program, if an unex-
pected condition or undesirable results occur, the program’s execution needs
to be retraced to find the precise point where the deviation from desired be-
havior actually originated. In order to be able to step backward, the program
state needs to be saved before every forward operation. However, the amount
of saved state can become extremely large because the computer executes
millions of instructions per second; in fact, the accumulated state grows so
quickly that it may be infeasible to store the program trace for long program
execution length. The trace for only a small window of execution may be
stored. Yet, the distance between the point of the bug’s manifestation and the
original source location of the bug may be large, making it infeasible to step
backward to the correct origin of the bug via trace traversal. This is where
reversible computing can be applied—instead of saving/restoring the values of
the variables to/from memory, the inverses of the instructions can be executed
backward to traverse the program in reverse from the bug manifestation point
until the bug’s source is determined.
The difficulty in debugging is especially pronounced in (1) assembly-level
debugging, due to very large sizes of traces; and (2) parallel computing. Re-
versible computing is either a significantly more efficient method or the only
feasible method in these cases.
In debugging programs at the level of its assembly language, since the
number of assembly instructions or machine code is extremely large, the

trace sizes needed to enable backward traversal in assembly code grows ex-
tremely quickly. Reversible computing is the only feasible method to enable
bi-directional movement in assembly instruction streams for efficient debug-
ging. Without reversible computing, assembly-level debugging either slows
down forward execution tremendously (due to the introduction of the high
cost of trace generation operations before every assembly instruction) or is
infeasible because the trace does not fit in the available computer memory.
The problem of debugging has been described and various methods sur-
veyed extensively in the context of high-level programs such as text editors
and user interface systems [Teitelman, 1975, 1984, Archer et al., 1984, Lee-
man, 1986]. General bi-directional movement for debugging in general has
been studied [Boothe, 2000], especially taking care of logging all the rele-
vant states including system call data to provide determinism in repeated
bi-directional movement across already-executed instructions. Assembly-level
debugging via reverse execution was studied and optimizations proposed to
significantly reduce the amount of memory trace needed for backward traver-
sal [Akgul and Mooney III, 2004, Lee, 2007]. While reversible execution has
been successfully applied in parallel computing applications (e.g., [Carothers
et al., 1999]), full-scale application of reversible debugging in large parallel
systems is a relatively open item of research.
2.6 Source Code Control Systems

Source code control systems provide a world view in which modifications to a
set of objects can be tracked, traversed, and manipulated along different logical
timelines. The timelines are formed by sequences of individual or grouped
modifications to objects. In general, the timelines are related to each other
in the form of directed acyclic graphs (DAGs). Most often, each object is a
named file in a file system. Modifications to the file are characterized in terms
of edits or changes to the individual lines, assuming that the file is a text file.
Popular source code control systems such as git [Loeliger and McCullough,
2012, Somasundaram, 2013] and mercurial [O’Sullivan, 2009], as well as older
systems such as svn [Collins-Sussman et al., 2009] and cvs [Thomas and Hunt,
2003], provide reversible sequences of edits to sets of files. They also provide
ways to identify and extract, via user-specified or system-generated naming,
individual paths along the DAG of timelines.
Overall, the systems provide a way to view the evolution of the object
values as a reversible computation that can be traversed forward or backward
and also merge different timelines. When each object is viewed as a program
variable holding data, changes to the values of the variables can be made
in a reversible fashion to save and restore the data values. Thus, although
the granularity of the objects is different from the variables in a conventional

computer program (files often have much larger bit lengths than typical pro-
gram variables), the notion of reversibility in source code control systems is
analogous to that of a program’s state evolution. Concepts common to both
include the undo and commit operations, while the branching and merging are
operations that are somewhat specific to source code control systems.
2.7 Fault Detection

In fault detection, the idea is to utilize reversible computing to periodically
verify if the forward computation was performed correctly, as follows. Given
a code fragment P , after it has been executed forward as F (P ), it is to be
ascertained if there had been a faulty execution of any portion of P (for
example, values of some variables may become incorrect due to low-probability
errors in the memory subsystem that flip one or more bits randomly due to
electrical faults). If the code is executed backward as R(F (P )), then the initial
values of the variables prior to execution of F (P ) will not match the values
restored by R(F (P )); such a mismatch can be used to signal an error condition.
This method of detection relies on two important, reasonable assumptions:
1. The type of errors encountered in the forward path are rare events, and
hence the backward path is not susceptible to the same errors as well.
Because F (P ) executed under errors and R(P ) did not, their net results
can be expected to differ from each other.
2. In the rare event that the backward path also encounters errors, we can
reasonably assume that the forward errors and backward errors do not
cancel each other.
Reversible computing can be used for fault detection and, in some cases,
fault correction. Reverse execution can be used in trapping errors in either
forward code or the reverse code, or even in the implementation of the reverse
compiler. This is achieved by checking the following simple necessary correct-
ness condition at runtime [Bishop, 1997], which, when applied on every local
variable and global variable, is useful in detecting errors in the code or the
compiler.
Suppose a variable var is initialized to expression in the for-

ward execution. At the end of the reverse execution, the final value
of the variable var must equal expression.
Another simple correctness condition is the following, which is a general-

ization of the end-of-tape condition described in [Bishop, 1997]:
Suppose the bit/byte tape is at position P before the forward

execution of a function f , and later the reverse of the function is
executed. Then, by the end of the reverse execution, the tape must
be rewound to the same position P .
2.8 Fault Tolerance

Fault tolerant computation in a parallel or distributed system is the ability
to gracefully continue execution of an application despite transient faults or
failures of system components at runtime. Fault tolerance is an extremely dif-
ficult capability to achieve in parallel systems, particularly when the number
of components in the system is very large. Simplistic schemes rely on period-
ically saving the entire application state to persistent storage and restoring
this state at all processors for recovering from failures. However, such schemes
are woefully non-scalable and break down with large numbers of processors.
More scalable solutions do not rely on global checkpoint/restart views, but use
in-memory solutions. Among them, rollback-based recovery is an important
algorithmic core underlying scalable parallel computing, appearing in the form
of system support, middleware, or applications. For example, efficient rollback-
based fault tolerance approaches (e.g., [Manivannan and Singhal, 1996, Kim
et al., 1996], among many others) rely critically on the ability of processors
to revert their state back to a point in the past.
Thus, processors need the ability to go back to a previous point in execution
dynamically on demand, when they are informed of a fault. The definition of
a fault varies with application. Often, a fault is the detection of a failure of a
processor. In other software-level rollback schemes, a fault is the detection of
a violation of application-specific event order for correctness. For example, in
large-scale Time Warp [Jefferson, 1985, Perumalla, 2007], a primary rollback
results when an event is received with timestamp smaller than the current
virtual time of the receiving processor. When previously sent messages are
taken back as a result of primary rollback, further rollbacks, called secondary
rollbacks, are transitively propagated to other processors.
Figure 2.1 shows the schematic for this general setting [Perumalla and
Park, 2013]. When a processor Pf encounters a fault, it restarts from the
most recently saved checkpoint LCf and informs all other processors {Pr } to
roll back to the point corresponding to the program state of LCf . Every rolling
back processor Pr can invoke reverse code to recover the state corresponding
to LCf .
Note that LCf and LCr are in general different because, for maximum
efficiency, each processor is allowed to asynchronously and infrequently initiate
a checkpoint of its own state to persistent storage. Note also that every rolling

FIGURE 2.1: Schematic of asynchronous recovery sequence using re-

verse computation-based rollback.
Each thin vertical line denotes an update to the local state of a processor.
Each thick vertical line marks a full checkpoint of the processor state to
persistent storage. Note that there are very many processors indicated
by Pr that are affected due to the fault at Pf . All of them need to be
rolled back, although, for simplicity, only one processor is shown in the
illustration.
back (non-faulted) processor Pr need only use reverse computation, but does
not have to access its own checkpoint LCr . The checkpoint is only used by
a processor if and only if it is the faulted processor. This particular aspect
dramatically relieves congestion in the system in terms of lowered pressure on
the memory bus and on the file system.
In Figure 2.1, Pr ’s corresponding state of LCf is joined by the dashed line
between the processors. The faulted processor Pf restarts from LCf , because
the state from LCf to the fault point is assumed to be lost or unavailable due
to failure.
2.9 Database Transactions

The concept of reversal of operations is fundamental to the backbone of
databases, namely, database transactions. Databases provide the key prop-
erties of atomicity, consistency, isolation, and durability (ACID properties)
for any groups of operations called transactions [Date, 2003]. Applications
can be written correctly and conveniently using these properties. Database
systems internally provide sophisticated and elaborate implementations to
provide support for transactions [Berstein and Newcomer, 2009], fundamen-
tally relying on the concepts of reversal and replay of indivisible groups of
operations. Operations are logged into persistent storage, and complex algo-
rithms ensure that the state of the logs and the state of the data stored in the
database are always consistent with each other. Reversibility of a transaction
is key to correct operation because a transaction may be aborted at any time
(either intentionally by the user due to change of mind, or unintentionally
by the user such as from loss of network connection, or automatically by the
system due to faults such as power failures). When a transaction is aborted
mid-way, all operations performed as part of the transaction must be undone
to preserve the critical ACID properties.
In a common example often used to illustrate the reversal of operations for
transactions, two transactions T1 and T2 operate on a database of two bank
accounts A1 and A2 . Transaction T1 attempts to transfer x dollars from A1
to A2 , while T2 attempts to transfer y dollars from A2 to A1 . To transfer, T1
first debits A1 by x dollars and then credits A2 by the same amount. Simi-
larly, T2 first debits A2 by y dollars and credits A1 by the same amount. Thus,
T1 = A1 ← A1 − x; A2 ← A2 + x and T2 = A2 ← A2 − y; A1 ← A2 + y . If the
database state before either transaction is S , then the transaction system
ensures that the final system state after the transactions is only one among
S → T1 , S → T2 , S → T1 → T2 , or S → T2 → T1 , where P → Q de-
notes the state obtained by application of transaction Q on state P . In other
words, it ensures that at most one transaction succeeds, or if both succeed, the
state is exactly as though one transaction is entirely preceded by the other
(i.e., not interleaved). To achieve these semantics, reversal of operations is
employed if and when any transaction is aborted before it is executed to com-
pletion (i.e., “committed”). For example, if T1 is aborted after its first step
A1 ← A1 − x , this partially executed transaction can be undone by executing
the inverse A1 ← A1 + x . Similarly, if T1 completes both steps, but somehow
fails before it is committed, both steps are to be undone, in reverse order; That
is, by executing the inverse A2 ← A2 − x; A1 ← A1 + x . While this simple
example illustrates the reversal of aborted transactions in databases, in prac-
tice the database system infrastructure is much more elaborate and complex
to support very fast operation of a large number of transactions containing
a richer set of operations. Different reversal technologies are employed to roll

back transactions, the superset of which is in the realm of reversible comput-
ing.
2.10 Quantum Computing

Reversible computing is an inherent feature of Quantum Computing [Bennett
et al., 1997, Rieffel and Polak, 2011]. In Quantum Computing, computation is
a sequence of unitary operation of the computer state. Because every unitary
matrix is reversible by definition, the entire sequence is inherently reversible.
2.11 Additional Applications

Reversible computing finds use in different forms and to varying degrees in
several other applications. The adjoint methods in Automatic Differentiation
(AD) can exploit reversible computation in the so-called reverse mode of eval-
uation [Griewank and Walther, 2008]. User-friendly graphical interface-based
applications commonly provide interfaces to allow users to perform certain
operations that can be undone on demand, allowing the user to explore dif-
ferent operations. Sports scoreboard maintenance and recording systems are
built using reversible computing principles to enable automated generation of
inverse actions for normal actions, to deal with inherently error-prone pro-
cesses in real-time scoring [Briggs, 1987]. Computer file systems, such as the
Apple Macintosh Operating System’s Time Machine R
functionality, provide
a reversible view of all changes to the file system contents.
Interesting Contexts
Software for reversible execution found an interest-
ing application in the 1980s when J. Briggs reported a
way to use reverse code generation and reversible ex-
ecution to undo incorrect updates to the scoreboard
in cricket matches [Briggs, 1987]. Reversal code was
automatically generated with the objective of mini-
mization of the state information to be stored to en-
able reversal.
In the game of cricket [Knight et al., 2007], as in other
sports, mistakes and corrections inevitably occur in
recording and publishing the scores even as the game
is in progress. Errors can appear in two ways: (1) the
scoreboard operators may commit errors of omission
or commission in entering events into the comput-
ing system, or (2) the game itself may experience re-
versals of decisions and other sport-specific updates,
such as umpire’s corrections. In each of these types,
there are many occasions where updates are rolled
back and corrected, naturally warranting reversible
execution in the scoring program software.
In an unrelated context, reversibility appears in musi-

cal compositions in the concepts of the mirror canon
and the crab canon (also called cancrizans) in which
the musical notes are mirror images of themselves
(or palindromic) [Hugo, 1904]. A popular reference
to crab canons is the collection by J. S. Bach titled
“The Musical Offering” [Bach, 1747]. The notes of
a crab canon written over a Möbius strip [Pickover,
2007] can be played back and forth ad infinitum.

Quantum Computing

Uploaded by

Copyright:

Available Formats

Quantum Computing

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Quantum Computing

Uploaded by

Copyright:

Available Formats

48$1780

4 - Quantum Gates, Quantum Circuit and

5 - Superconducting Quantum Computing

In practice, there is generally a clear distinction between “unitary evolution”

cf. Chapter 9 (9.23).

15.1 QUANTUM CRYPTOGRAPHY

TABLE 15.1 The properties of a typical set of 12 qubits analyzed

This protocol succeeds because of the collapse resulting from a quantum

combatting this by further public exchange of information, as a result of which Alice

ψ(1, 2) = 2−1/2 [αz (1)βz (2) − βz (1)αz (2)] (15.4)

ψ(1, 2) = αz (1)βz (2) (15.6)

been disentangled. A measurement of the z component of the spin of the second

15.3 CLONING AND TELEPORTATION

where ψ(2) is any allowed state of system 2.

as a process that operates whatever state is represented by ψ(2), we conclude that

FIGURE 15.2 Quantum teleportation. SEP represents a source of entangled pairs of

ψ(3) = Aα(3) + Bβ(3) (15.11)

where the values of A and B are unknown. An experimentalist (Alice, of course)

Ψ(1, 2, 3) = 2−1/2 [Aα(3) + Bβ(3)][α(1)β(2) − β(1)α(2)] (15.12)

This is algebraically identical to the expression

ψ1 (2, 3) = 2−1/2 [α(2)β(3) − β(2)α(3)]

FIGURE 15.3 Two photons (a and b) are simultaneously incident on a semitranspar-

2−1/2 [a(2)b(3) ± b(2)a(3)] (15.16)

After substitution from (15.17) the expressions in (15.16) become

2−1/2 [d(2)c(3) − c(2)d(3)] , if i = 1

15.4 QUANTUM COMPUTING

|ψ = N − 2 (|0|0 + |1|1 + |2|0 + |3|1 + |4|0 + |5|1 + |6|0 + |7|1

so the state of the y register has period 2 as required.

The quantum Fourier transform

sum of the following eight terms:

We see, therefore, that the transformation (15.25) can be effected by changing

15.3 Verify the equivalence of equations (15.12) and (15.13).

This chapter is excerpted from

addition to Shor’s factorization algorithm, Deutsch–(Richard)Jozsa algorithm

7.2 WHAT IS A QUANTUM COMPUTER?

TABLE 7.1 Examples of two-state quantum systems. Here |V , |H, |L

1. |V |H Photon – Linear polarization

If |ψ1 = a|0 + b|1 and |ψ2 = c|0 + d|1 then

|ψ1 ⊗ |ψ2 = |ψ1 ψ2

with |αx |2 = 1 where x = 00, 01, 10, 11.

σx = |01| + |10|, (7.5)

The action of the Pauli matrices σx and σz on a qubit is

σx |0 = |1, σx |1 = |0, (7.8)

7.2.2 Quantum Gates

2. In classical circuits wires are joined together to form a single wire. In

7.2.3 Quantum Computer

The time evolution of the state is governed by a unitary operator U on a

7.3 WHY IS A QUANTUM COMPUTER?

1. A quantum computer is very eﬃcient over a classical computer.

7.4 FUNDAMENTAL PROPERTIES

7.4.1 Software, Hardware and CPU [1,13]

Nonlocality and uncertainty:

7.4.2 Two-Bit Gates for Universal Computation

7.4.3 NOT, Z and Hadamard Gates

TABLE 7.2 The truth table of the quantum NOT gate.

states orthogonal to them. The unitary operation UNOT is given by

UNOT |0 = |1 , (7.12a)

UNOT (α|0 + β|1) = α|1 + β|0 . (7.13)

TABLE 7.3 The truth table of the quantum Z gate.

TABLE 7.4 The truth table of the Hadamard gate.

|ψ = N − 2 (|0|0 + |1|1 + |2|0 + |3|1 + |4|0 + |5|1 + |6|0 + |7|1

σx = |01| + |10|, (7.5)

CNOT = |0000| + |0101| + |1011| + |1110| . (7.19)