The
power of quantum computing is based on several phenomena and laws of the
quantum world that are fundamentally different from those one encounters in
classical computing: complex probability amplitudes, quantum interference,
quantum parallelism, quantum entanglement and the unitarity of quantum
evolution. In order to understand these features, and to make a use of them for
the design of quantum algorithms, networks and processors, one has to
understand several basic principles which quantum mechanics is based on, as
well as the basics of Hilbert space formalism that represents the mathematical
framework used in quantum mechanics.
The
chapter starts with an analysis of the current interest in quantum computing.
It then discusses the main intellectual barriers that had to be overcome to
make a vision of the quantum computer an important challenge to current science
and technology. The basic and specific features of quantum computing are first
introduced by a comparison of randomized computing and quantum computing. An
introduction to quantum phenomena is done in three stages. First, several
classical and similar quantum experiments are analysed. This is followed by
Hilbert space basics and by a presentation of the elementary principles of
quantum mechanics and the elements of classical reversible computing.
The
aim of the chapter is to learn
The
basic elements of quantum computing are easy to identify: quantum bits, quantum
registers, quantum gates and quantum networks. However, at this point an
analogy with classical computing ends. Quantum bits, registers, gates and
networks are very different, have other properties and larger power than their
classical counterparts.
A
quantum bit can be in any state within an infinite set of states. A quantum
register of n quantum bits can be, at the same time, in any of the
infinitely many superpositions of basis states. The parallelism a quantum
register can exhibit is striking. The key new feature is that a quantum
register can be in an entangled state. On one side, entangled states with their
non-locality features are a hallmark of quantum mechanics. On the other side,
quantum entanglement is an important resource of quantum information
processing.
There
is a larger variety of quantum gates than of classical gates. There are already
infinitely many one-input/output quantum gates. In addition, almost any
two-input/output quantum gate is universal. A simple two input/output gate
together with one-input rotation gates form a set of universal gates.
The
aim of the chapter is to learn:
Quantum
algorithms make use of several specific features of the quantum world, for
example quantum superposition, to get from classical inputs, through entangled
states, to classical outputs more efficiently than classical algorithms. A
variety of quantum algorithms are presented in this chapter. They range from
pioneering algorithms, simple but powerful, for several promise problems,
through seminal Shor's algorithms and a variety of algorithms for various
search problems and their modifications, due to Grover and others.
Design
of faster-than-classical quantum algorithms for important algorithmic problems
has been an interesting intellectual adventure and achievement. Their existence
keeps being one of the key stimuli to those trying to overcome enormous
technology problems to build (powerful) quantum computers.
Methods
to design quantum algorithms and to show limitations of quantum power have also
been developed gradually and will be presented and illustrated in this chapter.
The
aim of the chapter is to learn:
In
addition to the study of problems of the design and analysis of algorithms and
circuits, as well as of the computational complexity of algorithmic problems,
another main method of theoretical computing to get an insight into the power
of computational resources is to study models of quantum computing devices and
the corresponding complexity classes. This will be done in this chapter for three
most basic models of quantum automata: quantum versions of finite automata,
Turing machines and cellular automata.
Quantum
finite automata are perhaps the most elementary model of quantum automata. They
are in addition the only model so far for which it has been fully proved that
they have larger power than their classical counterparts.
Quantum
Turing machines are the main model to study the most fundamental questions
concerning the power of quantum computing itself and the power of quantum versus
classical computing. Quantum cellular automata are of a special interest. They
seem to be a model much closer to the physical reality than quantum Turing
machines. In addition, it is still a major open problem whether quantum
cellular automata are more powerful than quantum Turing machines.
The
aim of the chapter is to learn:
The
study of complexity questions and of complexity classes, computational and
communicational, has proved to be very enlightenin and important for classical
computation. It has developed a firm theoretical basis for our understanding of
the potentials and limitations of computational resources, models, and modes.
There is reason to expect the same for the complexity investigations in quantum
computation and communication.
It
is of utmost importance to determine whether quantum classification of inherent
computational complexity is indeed different from the classical one. Would this
prove to be the case the very basic foundations of computing would be shaken.
Quantum
computational complexity theory is characterized, as its classical counterpart,
by a number of fundamental open problems concerning the proper inclusions of
complexity classes. In order to get a better insight into these problems, and
to test potential methods to solve them, the relativized quantum complexity
theory is of interest and importance.
It
is also of importance to find out how much quantum features can speed up
computations, shorten communications and achieve efficiency in size or space.
Investigations
of the potential impacts on the power of computing of the existence of slightly
non-linear evolutions in quantum physics are also of interest.
The
aim of the chapter is to learn:
Secure
communication is one of the areas of key importance for modern society in which
quantum information transmission and processing seems to be able to bring
significant contributions. For example, quantum cryptography may be the main
defence against quantum code breaking in the future.
An
important new feature of quantum cryptography is that security of quantum key
generation and quantum cryptographic protocols is based on a more reliable
fact, on the laws of nature as revealed by quantum mechanics, than in the case
of classical cryptography, whose security is based on unproven assumptions
concerning the computational hardness of some algorithmic problems.
It
is difficult to overemphasize the importance of quantum cryptography for an
understanding and utilization of quantum information processing. Quantum
cryptography was the first area in which quantum laws were directly exploited
to bring an essential advantage in information processing.
Closely
related are quantum teleportation and quantum superdense coding--special ways
of the transmission of quantum or classical information usin one of the most
puzzling phenomena of the quantum world--non-locality features of the quantum
entanglement.
The
aim of the chapter is to learn:
Theoretical
investigations concerning quantum algorithms, automata, complexity, information
theory and cryptography are of great interest and importance. However, progress
in the experimental efforts to design quantum information-processing systems is
crucial for seeing properly the overall perspectives of the future designs of
real and powerful quantum computers, and for isolating and solving the problems
that need to be dealt with if powerful quantum computers are ever to be built.
It
has been realized, from the very early days of research in quantum computing,
at least by some, that powerful evolution of isolated quantum systems is hard
to utilize in real quantum processors, because of their interaction with the
environment that can destroy very large but fragile quantum superpositions; and
because of the natural imperfections of (inherently analogue) quantum devices.
In addition, quantum error correction was considered impossible.
Fortunately,
several developments brought the vision of quantum computers closer to reality.
Quantum computation stabilization methods and quantum error correction codes
have turned out to be possible and efficient. Techniques for fault-tolerant
quantum computing have been developed. Finally, some promising technologies to
design quantum gates, circuits, and processors have been identified and are
being experimentally tested.
The
aim of the chapter is to learn:
The
development and the understanding of the basic concepts, methods and results of
quantum information theory and of the faithful transmission of quantum
information in time and space is the most fundamental problem of quantum
information processing. In order to be able to understand and to utilize fully
the information processing available in nature, the concepts of classical
information theory need to be expanded to accumulate quantum information
carriers. Three central problems concerning quantum information and its
communication are dealt with, very briefly, in this chapter.
The
aim of the chapter is to learn:
Our best theories are not only truer than common sense, they make far more sense than common sense does.
David Deutsch, The fabric of reality
(1997)
The first section of this Appendix is devoted to quantum theory. It contains an informal, often popular, overview and discussion of several basic issues of quantum physics. It is written mainly for those in computing with (almost) no knowledge of the subject. Exposition is therefore necessarily without many details needed if one wants to be (fully) precise. For more the reader is referred, for example, to Peres (1993), Bub (1997), Jammer (1966), Penrose (1990, 1994) and Lindley (1996)--ranging these references, roughly, from more technical to more popular. They mainly influenced presentation of the section.
Section
presents some basic concepts and results of Hilbert space theory in more detail
than in Section and it contains additional subjects.
The
third part of the Appendix, on the book web pages only, contains in Section a
survey of the basic concepts, models and results of the complexity theory. This
part is oriented mainly towards people outside of computing with (almost) no
knowledge of the computation and complexity theory. Section contains additional
exercises and Section additional historical and bibliographical references.
Bibliography
Index