Synopses & Reviews
The purpose of this monograph is to provide the mathematically literate reader with an accessible introduction to the theory of quantum computing algorithms, one component of a fascinating and rapidly developing area which involves topics from physics, mathematics, and computer science. The author briefly describes the historical context of quantum computing and provides the motivation, notation, and assumptions appropriate for quantum statics, a non-dynamical, finite dimensional model of quantum mechanics. This model is then used to define and illustrate quantum logic gates and representative subroutines required for quantum algorithms. A discussion of the basic algorithms of Simon and of Deutsch and Jozsa sets the stage for the presentation of Grover's search algorithm and Shor's factoring algorithm, key algorithms which crystallized interest in the practicality of quantum computers. A group theoretic abstraction of Shor's algorithms completes the discussion of algorithms. The last third of the book briefly elaborates the need for error-correction capabilities and then traces the theory of quantum error-correcting codes from the earliest examples to an abstract formulation in Hilbert space. This text is a good self-contained introductory resource for newcomers to the field of quantum computing algorithms, as well as a useful self-study guide for the more specialized scientist, mathematician, graduate student, or engineer. Readers interested in following the ongoing developments of quantum algorithms will benefit particularly from this presentation of the notation and basic theory. Series: Progress in Computer Science and Applied Logic, Volume 19 Contents Preface Acknowledgements 1. Quantum Statics 1.1 Context 1.2 Experimental motivation for quantum mechanics 1.3 The basic model 1.4 The basic example: spin-1/2 particles 1.5 Dirac notation 1.6 Unitary transformations 2. Basics of Quantum Computation 2.1 Qubits and tensor products 2.2 The basic strategy of quantum algorithms 2.3 Quantum gates 2.4 Quantum subroutines: addition on a quantum computer 2.5 Quantum subroutines: a teleportation circuit 3. Quantum Algorithms 3.1 Deutsch-Josza algorithm 3.2 Simon's algorithm 3.3 Grover's algorithm 3.4 Shor's algorithm: factoring N=15 3.5 Shor's algorithm: factoring N=pq 3.6 The finite Fourier transform 3.7 Eigenvalues in quantum algorithms 3.8 Group theory and quantum algorithms 4. Quantum Error-Correcting Codes 4.1 Quantum dynamics and decoherence 4.2 Error correction 4.3 Shor's nine qubit error-correcting code 4.4 A seven qubit error-correcting code 4.5 A five qubit error-correction code 4.6 Stabilizers and the five qubit code 4.7 Theoretical aspects of stabilizer codes 4.8 CSS codes 4.9 Abstract quantum error correction 4.10 Further aspects of quantum error-correcting codes Afterword References Index
"Pittenger's book, as the title suggests, explains the mathematics at the basis of quantum computing and the fundamental algorithms, including Shor's factoring, Grover's search and error correction algorithms.... Since quantum computing is a highly interdisciplinary science, the author has tried to capture the attention of a large variety of readers and he has mostly achieved this objective. The book can be used as a formal introductory text for graduate students as well as a fascinating, but still engaging resource for interested readers who are comfortable with linear algebra.... Pittenger helps the reader into focusing attention on the algorithmic aspects rather than the formal content and uses examples as [an] integral part of the book, illustrating the substantial meaning of quantum theory applied to computing. He also proposes some exercises to stimulate an insightful reading.... The bibliography is complete and the interested reader can improve the understanding of the book and of the entire matter by following the numerous references, acquiring in this way more tools for the comprehension of a subject of such complexity...." --SIGACT News "An Introduction to Quantum Computing Algorithms reflects its author's own experience in learning the mathematics and theoretical physics required for the subject, as he writes in the acknowledgements. It is generally written in a pleasant and informal style, with much motivation in between the mathematics.... In just 150 pages this book manages to explain much of the core of quantum computing, and to explain it well." --Quantum Information and Computation (QIC) "If you have a general (fuzzy) background on quantum physics and on computer science, I recommend reading this book.... It is well written, easy to read, with many illustrating examples, and many exercises." --Zentralblatt Math
In 1994 Peter Shor 65] published a factoring algorithm for a quantum computer that finds the prime factors of a composite integer N more efficiently than is possible with the known algorithms for a classical com puter. Since the difficulty of the factoring problem is crucial for the se curity of a public key encryption system, interest (and funding) in quan tum computing and quantum computation suddenly blossomed. Quan tum computing had arrived. The study of the role of quantum mechanics in the theory of computa tion seems to have begun in the early 1980s with the publications of Paul Benioff 6]' 7] who considered a quantum mechanical model of computers and the computation process. A related question was discussed shortly thereafter by Richard Feynman 35] who began from a different perspec tive by asking what kind of computer should be used to simulate physics. His analysis led him to the belief that with a suitable class of "quantum machines" one could imitate any quantum system."
An excellent introductory reference to quantum computing, this book provides a solid understanding of the basics of the theory and an awareness of the broad potential applicability of quantum computation. Includes a detailed overview of the historical context of quantum computing, discusses the most recent developments, and presents interesting applications to a number of areas from encryption systems to database research.
Table of Contents
[see attached for complete TOC] Preface * Acknowledgements * 1. Quantum Statics * 2. Basics of Quantum Computation * 3. Quantum Algorithms * 4. Quantum Error-Correcting Codes * Afterword * References * Index