An Introduction to Quantum Computing

by Kaye, Phillip; Laflamme, Raymond; Mosca, Michele

• ISBN13: 9780198570493
• ISBN10: 019857049X
• Format: Paperback
• Copyright: 2007-01-18
• Publisher: Oxford University Press

Summary

This concise, accessible text provides a thorough introduction to quantum computing - an exciting emergent field at the interface of the computer, engineering, mathematical and physical sciences. Aimed at advanced undergraduate and beginning graduate students in these disciplines, the text is technically detailed and is clearly illustrated throughout with diagrams and exercises. Some prior knowledge of linear algebra is assumed, including vector spaces and inner products. However, prior familiarity with topics such as quantum mechanics and computational complexity is not required.

Author Biography

Phillip Ronald Kaye was born in Toronto, and raised in Waterloo, Ontario, Canada. In 1995 Phil was accepted to the Faculty of Engineering at the University of Waterloo with an entrance scholarship. He completed his undergraduate degree in Systems Design Engineering in 2000 and was awarded the George Dufault Medal for Excellence in Communication at his convocation. During the Summer months following his undergraduate convocation, Phil worked as an encryption software developer at Research in Motion (RIM), where he continued to work on a part-time basis during his graduate studies. Phil did his Master's degree in the department of Combinatorics and Optimization at Waterloo. His Master's thesis was entitled 'Quantum Networks for Concentrating Entanglement, and a Logical Characterization of the Computational Complexity Class BPP.' Phil is currently a PhD student at the School of Computer Science at the University of Waterloo. Raymond Laflamme completed his undergraduate studies in Physics at Universite Laval. He then moved to Cambridge, UK, where he took Part III of the Mathematical Tripos before doing a PhD in the Department of Applied Mathematics and Theoretical Physics (DAMTP) under the direction of Professor Stephen Hawking. Following posts at UBC, Cambridge and Los Alamos National Laboratory, Raymond moved to the University of Waterloo in 2001 as a Canada Research Chair in Quantum Information. Raymond is a recipient of Ontario's Premier Research Award and a Director of the Quantum Information program of the Canadian Institute for Advanced Research. He was named the Ivey Foundation Fellow of the Canadian Institute for Advanced Research (CIAR) in September of 2005. Michele Mosca obtained a DPhil in quantum computer algorithms in 1999 at the University of Oxford. Since then he has been a faculty member in Mathematics at St. Jerome's University and in the Combinatorics and Optimization department of the Faculty of Mathematics, University of Waterloo, and a member of the Centre for Applied Cryptographic Research. He holds a Premier's Research Excellence Award (2000-2005), is the Canada Research Chair in Quantum Computation (since January 2002), and is a CIAR scholar (since September 2003). He is a co-founder and the Deputy Director of the Institute for Quantum Computing, and a founding member of the Perimeter Institute for Theoretical Physics.

Table of Contents

Preface	p. x
Acknowledgements	p. xi
Introduction and Background	p. 1
Overview	p. 1
Computers and the Strong Church-Turing Thesis	p. 2
The Circuit Model of Computation	p. 6
A Linear Algebra Formulation of the Circuit Model	p. 8
Reversible Computation	p. 12
A Preview of Quantum Physics	p. 15
Quantum Physics and Computation	p. 19
Linear Algebra and the Dirac Notation	p. 21
The Dirac Notation and Hilbert Spaces	p. 21
Dual Vectors	p. 23
Operators	p. 27
The Spectral Theorem	p. 30
Functions of Operators	p. 32
Tensor Products	p. 33
The Schmidt Decomposition Theorem	p. 35
Some Comments on the Dirac Notation	p. 37
Qubits and the Framework of Quantum Mechanics	p. 38
The State of a Quantum System	p. 38
Time-Evolution of a Closed System	p. 43
Composite Systems	p. 45
Measurement	p. 48
Mixed States and General Quantum Operations	p. 53
Mixed States	p. 53
Partial Trace	p. 56
General Quantum Operations	p. 59
A Quantum Model of Computation	p. 61
The Quantum Circuit Model	p. 61
Quantum Gates	p. 63
1-Qubit Gates	p. 63
Controlled-U Gates	p. 66
Universal Sets of Quantum Gates	p. 68
Efficiency of Approximating Unitary Transformations	p. 71
Implementing Measurements with Quantum Circuits	p. 73
Superdense Coding and Quantum Teleportation	p. 78
Superdense Coding	p. 79
Quantum Teleportation	p. 80
An Application of Quantum Teleportation	p. 82
Introductory Quantum Algorithms
Probabilistic Versus Quantum Algorithms	p. 86
Phase Kick-Back	p. 91
The Deutsch Algorithm	p. 94
The Deutsch-Jozsa Algorithm	p. 99
Simon's Algorithm	p. 103
Algorithms with Superpolynomial Speed-Up	p. 110
Quantum Phase Estimation and the Quantum Fourier Transform	p. 110
Error Analysis for Estimating Arbitrary Phases	p. 117
Periodic States	p. 120
GCD, LCM, the Extended Euclidean Algorithm	p. 124
Eigenvalue Estimation	p. 125
Finding-Orders	p. 130
The Order-Finding Problem	p. 130
Some Mathematical Preliminaries	p. 131
The Eigenvalue Estimation Approach to Order Finding	p. 134
Shor's Approach to Order Finding	p. 139
Finding Discrete Logarithms	p. 142
Hidden Subgroups	p. 146
More on Quantum Fourier Transforms	p. 147
Algorithm for the Finite Abelian Hidden Subgroup Problem	p. 149
Related Algorithms and Techniques	p. 151
Algorithms Based on Amplitude Amplification	p. 152
Grover's Quantum Search Algorithm	p. 152
Amplitude Amplification	p. 163
Quantum Amplitude Estimation and Quantum Counting	p. 170
Searching Without Knowing the Success Probability	p. 175
Related Algorithms and Techniques	p. 178
Quantum Computational Complexity Theory and Lower Bounds	p. 179
Computational Complexity	p. 180
Language Recognition Problems and Complexity Classes	p. 181
The Black-Box Model	p. 185
State Distinguishability	p. 187
Lower Bounds for Searching in the Black-Box Model: Hybrid Method	p. 188
General Black-Box Lower Bounds	p. 191
Polynomial Method	p. 193
Applications to Lower Bounds	p. 194
Examples of Polynomial Method Lower Bounds	p. 196
Block Sensitivity	p. 197
Examples of Block Sensitivity Lower Bounds	p. 197
Adversary Methods	p. 198
Examples of Adversary Lower Bounds	p. 200
Generalizations	p. 203
Quantum Error Correction	p. 204
Classical Error Correction	p. 204
The Error Model	p. 205
Encoding	p. 206
Error Recovery	p. 207
The Classical Three-Bit Code	p. 207
Fault Tolerance	p. 211
Quantum Error Correction	p. 212
Error Models for Quantum Computing	p. 213
Encoding	p. 216
Error Recovery	p. 217
Three- and Nine-Qubit Quantum Codes	p. 223
The Three-Qubit Code for Bit-Flip Errors	p. 223
The Three-Qubit Code for Phase-Flip Errors	p. 225
Quantum Error Correction Without Decoding	p. 226
The Nine-Qubit Shor Code	p. 230
Fault-Tolerant Quantum Computation	p. 234
Concatenation of Codes and the Threshold Theorem	p. 237
	p. 241
Tools for Analysing Probabilistic Algorithms	p. 241
Solving the Discrete Logarithm Problem When the Order of a Is Composite	p. 243
How Many Random Samples Are Needed to Generate a Group?	p. 245
Finding r Given k/r for Random k	p. 247
Adversary Method Lemma	p. 248
Black-Boxes for Group Computations	p. 250
Computing Schmidt Decompositions	p. 253
General Measurements	p. 255
Optimal Distinguishing of Two States	p. 258
A Simple Procedure	p. 258
Optimality of This Simple Procedure	p. 258
Bibliography	p. 260
Index	p. 270
Table of Contents provided by Ingram. All Rights Reserved.