| |
| |
| Preface | |
| |
| |
| Acknowledgements | |
| |
| |
| |
| Introduction and Background | |
| |
| |
| |
| Overview | |
| |
| |
| |
| Computers and the Strong Church-Turing Thesis | |
| |
| |
| |
| The Circuit Model of Computation | |
| |
| |
| |
| A Linear Algebra Formulation of the Circuit Model | |
| |
| |
| |
| Reversible Computation | |
| |
| |
| |
| A Preview of Quantum Physics | |
| |
| |
| |
| Quantum Physics and Computation | |
| |
| |
| |
| Linear Algebra and the Dirac Notation | |
| |
| |
| |
| The Dirac Notation and Hilbert Spaces | |
| |
| |
| |
| Dual Vectors | |
| |
| |
| |
| Operators | |
| |
| |
| |
| The Spectral Theorem | |
| |
| |
| |
| Functions of Operators | |
| |
| |
| |
| Tensor Products | |
| |
| |
| |
| The Schmidt Decomposition Theorem | |
| |
| |
| |
| Some Comments on the Dirac Notation | |
| |
| |
| |
| Qubits and the Framework of Quantum Mechanics | |
| |
| |
| |
| The State of a Quantum System | |
| |
| |
| |
| Time-Evolution of a Closed System | |
| |
| |
| |
| Composite Systems | |
| |
| |
| |
| Measurement | |
| |
| |
| |
| Mixed States and General Quantum Operations | |
| |
| |
| |
| Mixed States | |
| |
| |
| |
| Partial Trace | |
| |
| |
| |
| General Quantum Operations | |
| |
| |
| |
| A Quantum Model of Computation | |
| |
| |
| |
| The Quantum Circuit Model | |
| |
| |
| |
| Quantum Gates | |
| |
| |
| |
| 1-Qubit Gates | |
| |
| |
| |
| Controlled-U Gates | |
| |
| |
| |
| Universal Sets of Quantum Gates | |
| |
| |
| |
| Efficiency of Approximating Unitary Transformations | |
| |
| |
| |
| Implementing Measurements with Quantum Circuits | |
| |
| |
| |
| Superdense Coding and Quantum Teleportation | |
| |
| |
| |
| Superdense Coding | |
| |
| |
| |
| Quantum Teleportation | |
| |
| |
| |
| An Application of Quantum Teleportation | |
| |
| |
| |
| Introductory Quantum Algorithms | |
| |
| |
| |
| Probabilistic Versus Quantum Algorithms | |
| |
| |
| |
| Phase Kick-Back | |
| |
| |
| |
| The Deutsch Algorithm | |
| |
| |
| |
| The Deutsch-Jozsa Algorithm | |
| |
| |
| |
| Simon's Algorithm | |
| |
| |
| |
| Algorithms with Superpolynomial Speed-Up | |
| |
| |
| |
| Quantum Phase Estimation and the Quantum Fourier Transform | |
| |
| |
| |
| Error Analysis for Estimating Arbitrary Phases | |
| |
| |
| |
| Periodic States | |
| |
| |
| |
| GCD, LCM, the Extended Euclidean Algorithm | |
| |
| |
| |
| Eigenvalue Estimation | |
| |
| |
| |
| Finding-Orders | |
| |
| |
| |
| The Order-Finding Problem | |
| |
| |
| |
| Some Mathematical Preliminaries | |
| |
| |
| |
| The Eigenvalue Estimation Approach to Order Finding | |
| |
| |
| |
| Shor's Approach to Order Finding | |
| |
| |
| |
| Finding Discrete Logarithms | |
| |
| |
| |
| Hidden Subgroups | |
| |
| |
| |
| More on Quantum Fourier Transforms | |
| |
| |
| |
| Algorithm for the Finite Abelian Hidden Subgroup Problem | |
| |
| |
| |
| Related Algorithms and Techniques | |
| |
| |
| |
| Algorithms Based on Amplitude Amplification | |
| |
| |
| |
| Grover's Quantum Search Algorithm | |
| |
| |
| |
| Amplitude Amplification | |
| |
| |
| |
| Quantum Amplitude Estimation and Quantum Counting | |
| |
| |
| |
| Searching Without Knowing the Success Probability | |
| |
| |
| |
| Related Algorithms and Techniques | |
| |
| |
| |
| Quantum Computational Complexity Theory and Lower Bounds | |
| |
| |
| |
| Computational Complexity | |
| |
| |
| |
| Language Recognition Problems and Complexity Classes | |
| |
| |
| |
| The Black-Box Model | |
| |
| |
| |
| State Distinguishability | |
| |
| |
| |
| Lower Bounds for Searching in the Black-Box Model: Hybrid Method | |
| |
| |
| |
| General Black-Box Lower Bounds | |
| |
| |
| |
| Polynomial Method | |
| |
| |
| |
| Applications to Lower Bounds | |
| |
| |
| |
| Examples of Polynomial Method Lower Bounds | |
| |
| |
| |
| Block Sensitivity | |
| |
| |
| |
| Examples of Block Sensitivity Lower Bounds | |
| |
| |
| |
| Adversary Methods | |
| |
| |
| |
| Examples of Adversary Lower Bounds | |
| |
| |
| |
| Generalizations | |
| |
| |
| |
| Quantum Error Correction | |
| |
| |
| |
| Classical Error Correction | |
| |
| |
| |
| The Error Model | |
| |
| |
| |
| Encoding | |
| |
| |
| |
| Error Recovery | |
| |
| |
| |
| The Classical Three-Bit Code | |
| |
| |
| |
| Fault Tolerance | |
| |
| |
| |
| Quantum Error Correction | |
| |
| |
| |
| Error Models for Quantum Computing | |
| |
| |
| |
| Encoding | |
| |
| |
| |
| Error Recovery | |
| |
| |
| |
| Three- and Nine-Qubit Quantum Codes | |
| |
| |
| |
| The Three-Qubit Code for Bit-Flip Errors | |
| |
| |
| |
| The Three-Qubit Code for Phase-Flip Errors | |
| |
| |
| |
| Quantum Error Correction Without Decoding | |
| |
| |
| |
| The Nine-Qubit Shor Code | |
| |
| |
| |
| Fault-Tolerant Quantum Computation | |
| |
| |
| |
| Concatenation of Codes and the Threshold Theorem | |
| |
| |
| |
| |
| |
| |
| Tools for Analysing Probabilistic Algorithms | |
| |
| |
| |
| Solving the Discrete Logarithm Problem When the Order of a Is Composite | |
| |
| |
| |
| How Many Random Samples Are Needed to Generate a Group? | |
| |
| |
| |
| Finding r Given k/r for Random k | |
| |
| |
| |
| Adversary Method Lemma | |
| |
| |
| |
| Black-Boxes for Group Computations | |
| |
| |
| |
| Computing Schmidt Decompositions | |
| |
| |
| |
| General Measurements | |
| |
| |
| |
| Optimal Distinguishing of Two States | |
| |
| |
| |
| A Simple Procedure | |
| |
| |
| |
| Optimality of This Simple Procedure | |
| |
| |
| Bibliography | |
| |
| |
| Index | |