An Introduction to Quantum Computing Book

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