An Introduction to Quantum Computing Algorithms

by Pittenger, Arthur O.

• ISBN13: 9780817641276
• ISBN10: 0817641270
• Format: Hardcover
• Copyright: 1999-12-01
• Publisher: Birkhauser

Summary

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 19ContentsPrefaceAcknowledgements1. Quantum Statics1.1 Context1.2 Experimental motivation for quantum mechanics1.3 The basic model1.4 The basic example: spin-1/2 particles1.5 Dirac notation1.6 Unitary transformations2. Basics of Quantum Computation2.1 Qubits and tensor products2.2 The basic strategy of quantum algorithms2.3 Quantum gates2.4 Quantum subroutines: addition on a quantum computer2.5 Quantum subroutines: a teleportation circuit3. Quantum Algorithms3.1 Deutsch-Josza algorithm3.2 Simon's algorithm3.3 Grover's algorithm3.4 Shor's algorithm: factoring N=153.5 Shor's algorithm: factoring N=pq3.6 The finite Fourier transform3.7 Eigenvalues in quantum algorithms3.8 Group theory and quantum algorithms4. Quantum Error-Correcting Codes4.1 Quantum dynamics and decoherence4.2 Error correction4.3 Shor's nine qubit error-correcting code4.4 A seven qubit error-correcting code4.5 A five qubit error-correction code4.6 Stabilizers and the five qubit code4.7 Theoretical aspects of stabilizer codes4.8 CSS codes4.9 Abstract quantum error correction4.10 Further aspects of quantum error-correcting codesAfterwordReferencesIndex

Table of Contents

Preface	vii
Acknowledgments	xi
Quantum Statics	1	(18)
Context	1	(1)
Experimental motivation for quantum mechanics	2	(4)
The basic model	6	(4)
The basic example: spin 1/2 particles	10	(2)
Dirac notation	12	(3)
Unitary transformations	15	(4)
Basic of Quantum Computation	19	(22)
Qubits and tensor products	19	(3)
The basic strategy of quantum algorithms	22	(3)
Quantum gates	25	(8)
Quantum subroutines: addition on a quantum computer	33	(4)
Quantum subroutines: a teleportation circuit	37	(4)
Quantum Algorithms	41	(40)
Deutsch--Jozsa algorithm	41	(3)
Simon's algorithm	44	(2)
Grover's algorithm	46	(8)
Shor's algorithm: factoring N = 15	54	(3)
Shor's algorithm: factoring N = pq	57	(7)
The finite Fourier transform	64	(4)
Eigenvalues in quantum algorithms	68	(6)
Group theory and quantum algorithms	74	(7)
Quantum Error-Correcting Codes	81	(44)
Quantum dynamics and decoherence	81	(4)
Error correction	85	(4)
Shor's nine-qubit error-correcting code	89	(3)
A seven-qubit quantum error-correcting code	92	(4)
A five-qubit error-correcting code	96	(3)
Stabilizers and the five-qubit code	99	(7)
Theoretical aspects of stabilizer codes	106	(7)
CSS codes	113	(2)
Abstract quantum error correction	115	(7)
Further aspects of quantum error-correcting codes	122	(3)
Afterword	125	(2)
References	127	(8)
Index	135