Machine generated contents note: 1. Introduction -- I. QUANTUM BUILDING BLOCKS -- 2. Single-Qubit Quantum Systems -- 2.1. The Quantum Mechanics of Photon Polarization -- 2.1.1. A Simple Experiment -- 2.1.2. A Quantum Explanation -- 2.2. Single Quantum Bits -- 2.3. Single-Qubit Measurement -- 2.4. A Quantum Key Distribution Protocol -- 2.5. The State Space of a Single-Qubit System -- 2.5.1. Relative Phases versus Global Phases -- 2.5.2. Geometric Views of the State Space of a Single Qubit -- 2.5.3. Comments on General Quantum State Spaces -- 2.6. References -- 2.7. Exercises -- 3. Multiple-Qubit Systems -- 3.1. Quantum State Spaces -- 3.1.1. Direct Sums of Vector Spaces -- 3.1.2. Tensor Products of Vector Spaces -- 3.1.3. The State Space of an n-Qubit System -- 3.2. Entangled States -- 3.3. Basics of Multi-Qubit Measurement -- 3.4. Quantum Key Distribution Using Entangled States -- 3.5. References -- 3.6. Exercises -- 4. Measurement of Multiple-Qubit States -- 4.1. Dirac's Bra/Ket Notation for Linear Transformations
4.2. Projection Operators for Measurement -- 4.3. Hermitian Operator Formalism for Measurement -- 4.3.1. The Measurement Postulate -- 4.4. EPR Paradox and Bell's Theorem -- 4.4.1. Setup for Bell's Theorem -- 4.4.2. What Quantum Mechanics Predicts -- 4.4.3. Special Case of Bell's Theorem: What Any Local Hidden Variable Theory Predicts -- 4.4.4. Bell's Inequality -- 4.5. References -- 4.6. Exercises -- 5. Quantum State Transformations -- 5.1. Unitary Transformations -- 5.1.1. Impossible Transformations: The No-Cloning Principle -- 5.2. Some Simple Quantum Gates -- 5.2.1. The Pauli Transformations -- 5.2.2. The Hadamard Transformation -- 5.2.3. Multiple-Qubit Transformations from Single-Qubit Transformations -- 5.2.4. The Controlled-not and Other Singly Controlled Gates -- 5.3. Applications of Simple Gates -- 5.3.1. Dense Coding -- 5.3.2. Quantum Teleportation -- 5.4. Realizing Unitary Transformations as Quantum Circuits -- 5.4.1. Decomposition of Single-Qubit Transformations -- 5.4.2. Singly-Controlled Single-Qubit Transformations -- 5.4.3. Multiply-Controlled Single-Qubit Transformations
5.4.4. General Unitary Transformations -- 5.5. A Universally Approximating Set of Gates -- 5.6. The Standard Circuit Model -- 5.7. References -- 5.8. Exercises -- 6. Quantum Versions of Classical Computations -- 6.1. From Reversible Classical Computations to Quantum Computations -- 6.1.1. Reversible and Quantum Versions of Simple Classical Gates -- 6.2. Reversible Implementations of Classical Circuits -- 6.2.1. A Naive Reversible Implementation -- 6.2.2. A General Construction -- 6.3. A Language for Quantum Implementations -- 6.3.1. The Basics -- 6.3.2. Functions -- 6.4. Some Example Programs for Arithmetic Operations -- 6.4.1. Efficient Implementation of and -- 6.4.2. Efficient Implementation of Multiply-Controlled Single-Qubit Transformations -- 6.4.3. In-Place Addition -- 6.4.4. Modular Addition -- 6.4.5. Modular Multiplication -- 6.4.6. Modular Exponentiation -- 6.5. References -- 6.6. Exercises -- II. QUANTUM ALGORITHMS -- 7. Introduction to Quantum Algorithms -- 7.1. Computing with Superpositions -- 7.1.1. The Walsh-Hadamard Transformation
7.1.2. Quantum Parallelism -- 7.2. Notions of Complexity -- 7.2.1. Query Complexity -- 7.2.2. Communication Complexity -- 7.3. A Simple Quantum Algorithm -- 7.3.1. Deutsch's Problem -- 7.4. Quantum Subroutines -- 7.4.1. The Importance of Unentangling Temporary Qubits in Quantum Subroutines -- 7.4.2. Phase Change for a Subset of Basis Vectors -- 7.4.3. State-Dependent Phase Shifts -- 7.4.4. State-Dependent Single-Qubit Amplitude Shifts -- 7.5. A Few Simple Quantum Algorithms -- 7.5.1. Deutsch-Jozsa Problem -- 7.5.2. Bernstein-Vazirani Problem -- 7.5.3. Simon's Problem -- 7.5.4. Distributed Computation -- 7.6. Comments on Quantum Parallelism -- 7.7. Machine Models and Complexity Classes -- 7.7.1. Complexity Classes -- 7.7.2. Complexity: Known Results -- 7.8. Quantum Fourier Transformations -- 7.8.1. The Classical Fourier Transform -- 7.8.2. The Quantum Fourier Transform -- 7.8.3. A Quantum Circuit for Fast Fourier Transform -- 7.9. References -- 7.10. Exercises -- 8. Shor's Algorithm -- 8.1. Classical Reduction to Period-Finding
8.2. Shor's Factoring Algorithm -- 8.2.1. The Quantum Core -- 8.2.2. Classical Extraction of the Period from the Measured Value -- 8.3. Example Illustrating Shor's Algorithm -- 8.4. The Efficiency of Shor's Algorithm -- 8.5. Omitting the Internal Measurement -- 8.6. Generalizations -- 8.6.1. The Discrete Logarithm Problem -- 8.6.2. Hidden Subgroup Problems -- 8.7. References -- 8.8. Exercises -- 9. Graver's Algorithm and Generalizations -- 9.1. Graver's Algorithm -- 9.1.1. Outline -- 9.1.2. Setup -- 9.1.3. The Iteration Step -- 9.1.4. How Many Iterations? -- 9.2. Amplitude Amplification -- 9.2.1. The Geometry of Amplitude Amplification -- 9.3. Optimality of Grover's Algorithm -- 9.3.1. Reduction to Three Inequalities -- 9.3.2. Proofs of the Three Inequalities -- 9.4. Derandomization of Grover's Algorithm and Amplitude Amplification -- 9.4.1. Approach 1: Modifying Each Step -- 9.4.2. Approach 2: Modifying Only the Last Step -- 9.5. Unknown Number of Solutions -- 9.5.1. Varying the Number of Iterations -- 9.5.2. Quantum Counting
9.6. Practical Implications of Grover's Algorithm and Amplitude Amplification -- 9.7. References -- 9.8. Exercises -- III. ENTANGLED SUBSYSTEMS AND ROBUST QUANTUM COMPUTATION -- 10. Quantum Subsystems and Properties of Entangled States -- 10.1. Quantum Subsystems and Mixed States -- 10.1.1. Density Operators -- 10.1.2. Properties of Density Operators -- 10.1.3. The Geometry of Single-Qubit Mixed States -- 10.1.4. Von Neumann Entropy -- 10.2. Classifying Entangled States -- 10.2.1. Bipartite Quantum Systems -- 10.2.2. Classifying Bipartite Pure States up to LOCC Equivalence -- 10.2.3. Quantifying Entanglement in Bipartite Mixed States -- 10.2.4. Multipartite Entanglement -- 10.3. Density Operator Formalism for Measurement -- 10.3.1. Measurement of Density Operators -- 10.4. Transformations of Quantum Subsystems and Decoherence -- 10.4.1. Superoperators -- 10.4.2. Operator Sum Decomposition -- 10.4.3. A Relation Between Quantum State Transformations and Measurements -- 10.4.4. Decoherence -- 10.5. References -- 10.6. Exercises -- 11. Quantum Error Correction
11.1. Three Simple Examples of Quantum Error Correcting Codes -- 11.1.1. A Quantum Code That Corrects Single Bit-Flip Errors -- 11.1.2. A Code for Single-Qubit Phase-Flip Errors -- 11.1.3. A Code for All Single-Qubit Errors -- 11.2. Framework for Quantum Error Correcting Codes -- 11.2.1. Classical Error Correcting Codes -- 11.2.2. Quantum Error Correcting Codes -- 11.2.3. Correctable Sets of Errors for Classical Codes -- 11.2.4. Correctable Sets of Errors for Quantum Codes -- 11.2.5. Correcting Errors Using Classical Codes -- 11.2.6. Diagnosing and Correcting Errors Using Quantum Codes -- 11.2.7. Quantum Error Correction across Multiple Blocks -- 11.2.8. Computing on Encoded Quantum States -- 11.2.9. Superpositions and Mixtures of Correctable Errors Are Correctable -- 11.2.10. The Classical Independent Error Model -- 11.2.11. Quantum Independent Error Models -- 11.3. CSS Codes -- 11.3.1. Dual Classical Codes -- 11.3.2. Construction of CSS Codes from Classical Codes Satisfying a Duality Condition -- 11.3.3. The Steane Code -- 11.4. Stabilizer Codes
13.4. Alternatives to the Circuit Model of Quantum Computation -- 13.4.1. Measurement-Based Cluster State Quantum Computation -- 13.4.2. Adiabatic Quantum Computation -- 13.4.3. Holonomic Quantum Computation -- 13.4.4. Topological Quantum Computation -- 13.5. Quantum Protocols -- 13.6. Insight into Classical Computation -- 13.7. Building Quantum Computers -- 13.8. Simulating Quantum Systems -- 13.9. Where Does the Power of Quantum Computation Come From? -- 13.10. What if Quantum Mechanics Is Not Quite Correct? -- APPENDIXES -- A. Some Relations Between Quantum Mechanics and Probability Theory -- A.1. Tensor Products in Probability Theory -- A.2. Quantum Mechanics as a Generalization of Probability Theory -- A.3. References -- A.4. Exercises -- B. Solving the Abelian Hidden Subgroup Problem
B.1. Representations of Finite Abelian Groups -- B.1.1. Schur's Lemma -- B.2. Quantum Fourier Transforms for Finite Abelian Groups -- B.2.1. The Fourier Basis of an Abelian Group -- B.2.2. The Quantum Fourier Transform Over a Finite Abelian Group -- B.3. General Solution to the Finite Abelian Hidden Subgroup Problem -- B.4. Instances of the Abelian Hidden Subgroup Problem -- B.4.1. Simon's Problem -- B.4.2. Shor's Algorithm: Finding the Period of a Function -- B.5. Comments on the Non-Abelian Hidden Subgroup Problem -- B.6. References -- B.7. Exercises.
