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 tensor products and spectral decomposition is not required, as the necessary material is reviewed in the text.
Author(s): Phillip Kaye, Raymond Laflamme, Michele Mosca
Edition: 1
Publisher: Oxford University Press, USA
Year: 2007
Language: German
Pages: 287
Contents......Page 6
Preface......Page 11
Acknowledgements......Page 12
1.1 Overview......Page 14
1.2 Computers and the Strong Church–Turing Thesis......Page 15
1.3 The Circuit Model of Computation......Page 19
1.4 A Linear Algebra Formulation of the Circuit Model......Page 21
1.5 Reversible Computation......Page 25
1.6 A Preview of Quantum Physics......Page 28
1.7 Quantum Physics and Computation......Page 32
2.1 The Dirac Notation and Hilbert Spaces......Page 34
2.2 Dual Vectors......Page 36
2.3 Operators......Page 40
2.4 The Spectral Theorem......Page 43
2.5 Functions of Operators......Page 45
2.6 Tensor Products......Page 46
2.7 The Schmidt Decomposition Theorem......Page 48
2.8 Some Comments on the Dirac Notation......Page 50
3.1 The State of a Quantum System......Page 51
3.2 Time-Evolution of a Closed System......Page 56
3.3 Composite Systems......Page 58
3.4 Measurement......Page 61
3.5.1 Mixed States......Page 66
3.5.2 Partial Trace......Page 69
3.5.3 General Quantum Operations......Page 72
4.1 The Quantum Circuit Model......Page 74
4.2.1 1-Qubit Gates......Page 76
4.2.2 Controlled-U Gates......Page 79
4.3 Universal Sets of Quantum Gates......Page 81
4.4 Efficiency of Approximating Unitary Transformations......Page 84
4.5 Implementing Measurements with Quantum Circuits......Page 86
5 SUPERDENSE CODING AND QUANTUM TELEPORTATION......Page 91
5.1 Superdense Coding......Page 92
5.2 Quantum Teleportation......Page 93
5.3 An Application of Quantum Teleportation......Page 95
6.1 Probabilistic Versus Quantum Algorithms......Page 99
6.2 Phase Kick-Back......Page 104
6.3 The Deutsch Algorithm......Page 107
6.4 The Deutsch–Jozsa Algorithm......Page 112
6.5 Simon’s Algorithm......Page 116
7.1 Quantum Phase Estimation and the Quantum Fourier Transform......Page 123
7.1.1 Error Analysis for Estimating Arbitrary Phases......Page 130
7.1.2 Periodic States......Page 133
7.1.3 GCD, LCM, the Extended Euclidean Algorithm......Page 137
7.2 Eigenvalue Estimation......Page 138
7.3.1 The Order-Finding Problem......Page 143
7.3.2 Some Mathematical Preliminaries......Page 144
7.3.3 The Eigenvalue Estimation Approach to Order Finding......Page 147
7.3.4 Shor’s Approach to Order Finding......Page 152
7.4 Finding Discrete Logarithms......Page 155
7.5 Hidden Subgroups......Page 159
7.5.1 More on Quantum Fourier Transforms......Page 160
7.5.2 Algorithm for the Finite Abelian Hidden Subgroup Problem......Page 162
7.6 Related Algorithms and Techniques......Page 164
8.1 Grover’s Quantum Search Algorithm......Page 165
8.2 Amplitude Amplification......Page 176
8.3 Quantum Amplitude Estimation and Quantum Counting......Page 183
8.4 Searching Without Knowing the Success Probability......Page 188
8.5 Related Algorithms and Techniques......Page 191
9 QUANTUM COMPUTATIONAL COMPLEXITY THEORY AND LOWER BOUNDS......Page 192
9.1 Computational Complexity......Page 193
9.1.1 Language Recognition Problems and Complexity Classes......Page 194
9.2 The Black-Box Model......Page 198
9.2.1 State Distinguishability......Page 200
9.3 Lower Bounds for Searching in the Black-Box Model: Hybrid Method......Page 201
9.4 General Black-Box Lower Bounds......Page 204
9.5 Polynomial Method......Page 206
9.5.1 Applications to Lower Bounds......Page 207
9.5.2 Examples of Polynomial Method Lower Bounds......Page 209
9.6.1 Examples of Block Sensitivity Lower Bounds......Page 210
9.7 Adversary Methods......Page 211
9.7.1 Examples of Adversary Lower Bounds......Page 213
9.7.2 Generalizations......Page 216
10.1 Classical Error Correction......Page 217
10.1.1 The Error Model......Page 218
10.1.2 Encoding......Page 219
10.2 The Classical Three-Bit Code......Page 220
10.3 Fault Tolerance......Page 224
10.4 Quantum Error Correction......Page 225
10.4.1 Error Models for Quantum Computing......Page 226
10.4.2 Encoding......Page 229
10.4.3 Error Recovery......Page 230
10.5.1 The Three-Qubit Code for Bit-Flip Errors......Page 236
10.5.2 The Three-Qubit Code for Phase-Flip Errors......Page 238
10.5.3 Quantum Error Correction Without Decoding......Page 239
10.5.4 The Nine-Qubit Shor Code......Page 243
10.6 Fault-Tolerant Quantum Computation......Page 247
10.6.1 Concatenation of Codes and the Threshold Theorem......Page 250
A.1 Tools for Analysing Probabilistic Algorithms......Page 254
A.2 Solving the Discrete Logarithm Problem When the Order of a Is Composite......Page 256
A.3 How Many Random Samples Are Needed to Generate a Group?......Page 258
A.4 Finding r Given k/r for Random k......Page 260
A.5 Adversary Method Lemma......Page 261
A.6 Black-Boxes for Group Computations......Page 263
A.7 Computing Schmidt Decompositions......Page 266
A.8 General Measurements......Page 268
A.9.2 Optimality of This Simple Procedure......Page 271
Bibliography......Page 273
B......Page 283
E......Page 284
N......Page 285
Q......Page 286
Z......Page 287
