Amazon
(online ordering)
Overview
Contents
Preface
About chapters
Figures
Corrections
Updatings
Additions
About author
Related links

ISBN: 0-07-709503-0
Published: May 1999
Binding:  Softcover
Pages: 439 - 246x189
Price: £34.99, DM73

Overview of chapters

(The first pages of each chapter are also available in PostScript)

• Chapter 1 --- FUNDAMENTALS (.ps)
• Chapter 2 --- ELEMENTS (.ps)
• Chapter 3 --- ALGORITHMS (.ps)
• Chapter 4 --- AUTOMATA (.ps)
• Chapter 5 --- COMPLEXITY (.ps)
• Chapter 6 --- CRYPTOGRAPHY (.ps)
• Chapter 7 --- PROCESSORS (.ps)
• Chapter 8 --- INFORMATION (.ps)
• Chapter 9 --- APPENDIX (.ps)

Chapter 1 --- FUNDAMENTALS

Introduction

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.

Learning Objectives

The aim of the chapter is to learn

1. the main reasons why to be interested in quantum computing;
2. the prehistory of quantum computing;
3. the specific properties of quantum computing in comparison with randomized computing;
4. the basic experiments and principles of quantum physics;
5. the basics of Hilbert space theory;
6. the elements of classical reversible computing.

Chapter 2 --- ELEMENTS

Introduction

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.

Learning Objectives

The aim of the chapter is to learn:

1. the basic concepts concerning quantum bits and registers;
2. the concept of quantum entanglement and the examples of its power;
3. the basic examples of quantum gates and of quantum circuits;
4. some examples of universal quantum gates and a method to show universality of quantum gates;
5. the basic quantum arithmetical circuits;
6. the concept of quantum superoperator circuits.

Chapter 3 --- ALGORITHMS

Introduction

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.

Learning Objectives

The aim of the chapter is to learn:

1. the power of quantum superpositions, parallelism and entanglement;
2. the efficient quantum algorithms for several basic promise problems;
3. the quantum Fourier transform and its properties and implementation;
4. Shor's quantum algorithms for integer factorization and discrete logarithm computation;
5. the hidden subgroup problems and their role in quantum computing;
6. a variety of search algorithms due to Grover and others;
7. methods to design efficient quantum algorithms;
8. methods to show lower bounds and limitations of quantum computing.

Chapter 4 --- AUTOMATA

Introduction

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.

Learning Objectives

The aim of the chapter is to learn:

1. the basic models of one-way and two-way quantum finite automata as well as their computational power and space efficiency in comparison with classical finite automata;
2. the basic models of quantum Turing machines and methods of implementing the main classical programming primitives in a reversible way;
3. the types and precision of amplitudes needed to ensure sufficient accuracy of computation on quantum Turing machines;
4. the basic models of quantum cellular automata and partitioned quantum cellular automata, as well as simulations between quantum cellular automata and quantum Turing machines.

Chapter 5 --- COMPLEXITY

Introduction

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.

Learning Objectives

The aim of the chapter is to learn:

1. the way universal quantum Turing machines can be constructed;
2. the basic quantum complexity classes and their properties;
3. the basic relations between classical and quantum complexity classes;
4. the basic results concerning relativized quantum complexity;
5. the basic concepts of quantum communication complexity;
6. a reduction of quantum communication protocols to quantum computation problems;
7. the potential impacts of non-linearity on the power of quantum computing.

Chapter 6 --- CRYPTOGRAPHY

Introduction

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.

Learning Objectives

The aim of the chapter is to learn:

1. several methods of secret key generation by two parties;
2. a method of multiparty secret key generation;
3. the unconditional security of quantum key generation;
4. the basic quantum cryptographic protocols;
5. the problems related to the security of quantum cryptographic protocols;
6. the main principles, circuits and some applications of quantum teleportation;
7. the quantum superdense coding procedure.

Chapter 7 --- PROCESSORS

Introduction

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.

Learning Objectives

The aim of the chapter is to learn:

1. the early proposals for quantum computers;
2. the impacts of imprecision, dissipation and decoherence on quantum computing;
3. the methods of designing and using quantum error-correcting codes;
4. the basics of quantum fault-tolerant techniques;
5. the basics of the main current technologies used, or considered, to develop experimental quantum processors.

Chapter 8 --- INFORMATION

Introduction

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.

1. Quantum information theory. How to rebuild classical information theory on quantum foundations. How to define fundamental concepts of quantum information theory. How to identify and explore the inherently quantum elements of such a theory.
2. Quantum transmissions theory. How to use optimally quantum channels to send classical information and how to use optimally quantum and classical channels to transmit quantum information. How to define and determine the capacity of different quantum channels.
3. Quantum entanglement theory. How to quantify and manipulate entanglement and how to produce good entanglement.

Learning Objectives

The aim of the chapter is to learn:

1. the basic concepts of quantum information theory;
2. the basic concepts of quantum transmission;
3. the basic techniques of quantum data compression;
4. the basic techniques of communication through a noisy channel;
5. the basic modes and measures of entanglement;
6. the basic quantum entanglement concentration and purification techniques.

Chapter 9 --- APPENDIX

Appendix

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)

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.