Jozef Gruska


Leaflet
Amazon
ISBN: 0077095030 
Overview of chapters(The first pages of each chapter are also available in PostScript)
Chapter 1  FUNDAMENTALSIntroductionThe 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 ObjectivesThe aim of the chapter is to learn
Chapter 2  ELEMENTSIntroductionThe 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 nonlocality 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 oneinput/output quantum gates. In addition, almost any twoinput/output quantum gate is universal. A simple two input/output gate together with oneinput rotation gates form a set of universal gates. Learning ObjectivesThe aim of the chapter is to learn:
Chapter 3  ALGORITHMSIntroductionQuantum 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 fasterthanclassical 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 ObjectivesThe aim of the chapter is to learn:
Chapter 4  AUTOMATAIntroductionIn 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 ObjectivesThe aim of the chapter is to learn:
Chapter 5  COMPLEXITYIntroductionThe 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 nonlinear evolutions in quantum physics are also of interest. Learning ObjectivesThe aim of the chapter is to learn:
Chapter 6  CRYPTOGRAPHYIntroductionSecure 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 codingspecial ways of the transmission of quantum or classical information usin one of the most puzzling phenomena of the quantum worldnonlocality features of the quantum entanglement. Learning ObjectivesThe aim of the chapter is to learn:
Chapter 7  PROCESSORSIntroductionTheoretical 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 informationprocessing 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 faulttolerant 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 ObjectivesThe aim of the chapter is to learn:
Chapter 8  INFORMATIONIntroductionThe 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.
Learning ObjectivesThe aim of the chapter is to learn:
Chapter 9  APPENDIXAppendixOur 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. 
For further information click here.