Quantum computing: a gentle introduction

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

Note continued: 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.