23-04-2012, 12:04 PM
The Temple of Quantum Computing
The Temple of Quantum Computing.pdf (Size: 2.91 MB / Downloads: 33)
Introduction
1.1 What is Quantum Computing?
In quantum computers we exploit quantum effects to compute in ways that are
faster or more efficient than, or even impossible, on conventional computers.
Quantum computers use a specific physical implementation to gain a computa-
tional advantage over conventional computers. Properties called superposition
and entanglement may, in some cases, allow an exponential amount of paral-
lelism. Also, special purpose machines like quantum cryptographic devices
use entanglement and other peculiarities like quantum uncertainty.
Quantum computing combines quantum mechanics, information theory, and
aspects of computer science [Nielsen, M. A. & Chuang, I. L. 2000]. The field
is a relatively new one that promises secure data transfer, dramatic computing
speed increases, and may take component miniaturisation to its fundamental
limit.
This text describes some of the introductory aspects of quantum computing.
We’ll examine some basic quantum mechanics, elementary quantum comput-
ing topics like qubits, quantum algorithms, physical realisations of those algo-
rithms, basic concepts from computer science (like complexity theory, Turing
machines, and linear algebra), information theory, and more.
1
2 Why Another Quantum Computing Tutorial?
1.2 Why Another Quantum Computing Tutorial?
Most of the books or papers on quantum computing require (or assume) prior
knowledge of certain areas like linear algebra or physics. The majority of the
literature that is currently available is hard to understand for the average com-
puter enthusiast, or interested layman. This text attempts to teach basic quan-
tum computing from the ground up in an easily readable way. It contains a lot
of the background in math, physics, and computer science that you will need,
although it is assumed that you know a little about computer programming.
At certain places in this document, topics that could make interesting research
topics have been identified. These topics are presented in the following format:
Question The topic is presented in bold-italics.
1.2.1 The Bible of Quantum Computing
Every Temple needs a Bible right? Well there is one book out there that is by far
the most complete book available for quantum computing, Quantum Computa-
tion and Quantum Information by Michael A. Nielsen and Isaac L. Chuang, which
we’ll abbreviate to QCQI. The main references for this work are QCQI and a
great set of lecture notes, also written by Nielsen. Nielsen’s lecture notes are
currently available at http://www.qinfopeople/nielsen/qicss.
html. An honourable mention goes out to Vadim V. Bulitko who has managed
to condense a large part of QCQI into 14 pages!
QCQI may be a little hard to get into at first, particularly for those without a
strong background in math. So the Temple of Quantum Computing is, in part,
a collection of worked examples from various web sites, sets of lecture notes,
journal entries, papers, and books which may aid in understanding of some of
the concepts in QCQI.
The Temple of Quantum Computing - ⃝c Riley T. Perry 2004 - 2010
Chapter 2
Computer Science
2.1 Introduction
The special properties of quantum computers force us to rethink some of the
most fundamental aspects of computer science. In this chapter we’ll see how
quantum effects can give us a new kind of Turing machine, new kinds of cir-
cuits, and new kinds of complexity classes. This is important as it was thought
that these things were not affected by what the computer was built from, but it
turns out that they are.
A distinction has been made between computer science and information the-
ory. Although information theory can be seen as a part of computer science it
is treated separately in this text with its own dedicated chapter. This is because
The quantum aspects of information theory require some of the concepts intro-
duced in the chapters that follow this one.
There’s also a little mathematics and notation used in this chapter which is
presented in the first few sections of chapter 3 and some basic C and Javascript
code for which you may need an external reference.
2.2 History
The origins of computer science can at least be traced back to the invention of
algorithms like Euclid’s Algorithm (c. 300 BC) for finding the greatest com-
mon divisor of two numbers. There are also much older sources like early
3
4 History
Figure 2.1: Charles Babbage and Ada Byron.
Babylonian cuneiform tablets (c. 2000 - 1700 BC) that contain clear evidence of
algorithmic processes [Gilleland M. ? 2000]. But up until the 19th century it’s
difficult to separate computer science from other sciences like mathematics and
engineering. So we might say that computer science began in the 19th century.
In the early to mid 19th century Charles Babbage, 1791 - 1871 (figure 2.1) de-
signed and partially built several programmable computing machines (see fig-
ure 2.4 for the difference engine built in 1822) that had many of the features of
modern computers. One of these machines called the analytical engine had re-
movable programs on punch cards based on those used in the Jacquard loom,
which was invented by Joseph Marie Jacquard (1752 - 1834) in 1804 [Smithso-
nianNMAH1999]. Babbage’s friend, Ada Augusta King, Countess of Lovelace,
1815 - 1852 (figure 2.1) and the daughter of Lord Byron is considered by some
as the first programmer for her writings on the Analytical engine. Sadly, Bab-
bage’s work was largely forgotten until the 1930s and the advent of modern
computer science. Modern computer science can be said to have started in
1936 when logician Alan Turing, 1912 - 1954 (figure 2.2) wrote a paper which
contained the notion of a universal computer.
The first electronic computers were developed in the 1940’s and led Jon Von
Neumann, 1903 - 1957 (figure 2.3) to develop a generic architecture on which
modern computers are loosely based. Von Neumann architecture specifies an
Arithmetic Logic Unit (ALU), control unit, memory, input/output (IO), a bus,
and a computing process. The architecture originated in 1945 in the first draft
of a report on EDVAC [Cabrera, B. J. ? 2000].
The Temple of Quantum Computing - ⃝c Riley T. Perry 2004 - 2010
History 5
Figure 2.2: Alan Turing and Alonzo Church.
Figure 2.3: Jon Von Neumann.
Computers increased in power and versatility rapidly over the next sixty years,
partly due to the development of the transistor in 1947, integrated circuits
in 1959, and increasingly intuitive user interfaces. Gordon Moore proposed
Moore’s law in 1965, the current version of which states that processor com-
plexity will double every eighteen months with respect to cost (in reality it’s
more like two years) [wikipedia.org 2006]. This law still holds but is starting
to falter, and components are getting smaller. Soon they will be so small, being
made up of a few atoms [Benjamin, S. & Ekert, A. ? 2000] that quantum effects
will become unavoidable, possibly ending Moore’s law.
There are ways in which we can use quantum effects to our advantage in a
classical sense, but by fully utilising those effects we can achieve much more.
The Temple of Quantum Computing - ⃝c Riley T. Perry 2004 - 2010
6 Turing Machines
This approach is the basis for quantum computing.
2.3 Turing Machines
In 1928 David Hilbert, 1862 - 1943 (figure 2.5) asked if there was a universal
algorithmic process to decide whether any mathematical proposition was true.
His intuition suggested ”yes”, then, in 1930 he went as far as claiming that
there were no unsolvable problems in mathematics [Natural Theology 2004].
This was promptly refuted by Kurt G¨odel, 1908 - 1976 (figure 2.5) in 1931 by
way of his incompleteness theorem which can be roughly summed up as follows:
You might be able to prove every conceivable statement about num-
bers within a system by going outside the system in order to come
up with new rules and axioms, but by doing so you’ll only create a
larger system with its own unprovable statements. [Jones, J.Wilson,
W. 1995, p. ?]
Then, in 1936 Alan Turing and Alonzo Church, 1903 - 1995 (figure 2.2) indepen-
dently came up with models of computation, aimed at resolving whether or
not mathematics contained problems that were ”uncomputable”. These were
problems for which there were no algorithmic solutions (an algorithm is a pro-
cedure for solving a mathematical problem that is guaranteed to end after a
number of steps). Turing’s model, now called a called a Turing Machine is
depicted in figure 2.6. It turned out that the models of Turing and Church were
equivalent in power. The thesis that any algorithm capable of being devised
can be run on a Turing machine, as Turing’s model was subsequently called,
was given the names of both these pioneers, the Church-Turing thesis [Nielsen,
M. A. 2002].