Quantum Computing: Lecture Notes

1 Quantum Computing
1.1 Introduction
1.2 Quantum mechanics
1.2.1 Superposition
1.2.2 Measurement
1.2.3 Unitary evolution
1.3 Qubits and quantum memory
1.4 Elementary gates
1.5 Example: quantum teleportation
2 The Circuit Model and the Deutsch-Jozsa Algorithm
2.1 Quantum computation
2.1.1 Classical circuits
2.1.2 Quantum circuits
2.2 Universality of various sets of elementary gates
2.3 Quantum parallelism
2.4 The early algorithms
2.4.1 Deutsch-Jozsa
2.4.2 Bernstein-Vazirani
3 Simon's Algorithm
3.1 The problem
3.2 The quantum algorithm
3.3 Classical algorithms for Simon's problem
3.3.1 Upper bound
3.3.2 Lower bound
4 The Fourier Transform
4.1 The classical discrete Fourier transform
4.2 The Fast Fourier Transform
4.3 Application: multiplying two polynomials
4.4 The quantum Fourier transform
4.5 An efficient quantum circuit
4.6 Application: phase estimation
5 Shor's Factoring Algorithm
5.1 Factoring
5.2 Reduction from factoring to period-finding
5.3 Shor's period-finding algorithm
5.4 Continued fractions
6 Hidden Subgroup Problem
6.1 Hidden Subgroup Problem
6.1.1 Group theory reminder
6.1.2 Definition and some instances of the HSP
6.2 An efficient quantum algorithm if G is Abelian
6.2.1 Representation theory and the quantum Fourier transform
6.2.2 A general algorithm for Abelian HSP
6.3 General non-Abelian HSP
6.3.1 The symmetric group and the graph isomorphism problem
6.3.2 Non-Abelian QFT on coset states
6.3.3 Query-efficient algorithm
7 Grover's Search Algorithm
7.1 The problem
7.2 Grover's algorithm
7.3 Amplitude amplification
7.4 Application: satisfiability
8 Quantum Walk Algorithms
8.1 Classical random walks
8.2 Quantum walks
8.3 Applications
8.3.1 Grover search
8.3.2 Collision problem
8.3.3 Finding a triangle in a graph
9 Hamiltonian Simulation
9.1 Hamiltonians
9.2 Method 1: Lie-Suzuki-Trotter methods
9.3 Method 2: Linear combination of unitaries (LCU)
9.3.1 Hamiltonian simulation via LCU
9.4 Method 3: Transforming block-encoded matrices
9.4.1 Hamiltonian simulation via transforming block-encoded matrices
10 The HHL Algorithm
10.1 The linear-system problem
10.2 The basic HHL algorithm for linear systems
10.3 Improving the efficiency of the HHL algorithm
11 Quantum Query Lower Bounds
11.1 Introduction
11.2 The polynomial method
11.3 The quantum adversary method
12 Quantum Algorithms from the Generalized Adversary Bound
12.1 The generalized adversary bound
12.2 The dual of the generalized adversary bound
12.3 ADV is an upper bound on quantum query complexity
12.4 Applications
12.5 Perfect composition and AND-OR trees
13 Quantum Complexity Theory
13.1 Most functions need exponentially many gates
13.2 Classical and quantum complexity classes
13.3 Classically simulating quantum computers in polynomial space
14 QMA and the Local Hamiltonian Problem
14.1 Quantum Merlin-Arthur (QMA)
14.2 The local Hamiltonian problem
14.3 Local Hamiltonian is QMA-complete
14.3.1 Completeness and soundness
14.3.2 Reducing the locality
14.4 Other interesting problems in QMA
14.5 Quantum interactive proofs
15 Quantum Encodings, with a Non-Quantum Application
15.1 Mixed states and general measurements
15.2 Quantum encodings and their limits
15.3 Lower bounds on locally decodable codes
16 Quantum Communication Complexity
16.1 Classical communication complexity
16.2 The quantum question
16.3 Example 1: Distributed Deutsch-Jozsa
16.4 Example 2: The Intersection problem
16.5 Example 3: The vector-in-subspace problem
16.6 Example 4: Quantum fingerprinting
17 Entanglement and Non-Locality
17.1 Quantum non-locality
17.2 CHSH: Clauser-Horne-Shimony-Holt
17.3 Magic square game
17.4 A non-local version of distributed Deutsch-Jozsa
18 Quantum Cryptography
18.1 Saving cryptography from Shor
18.2 Quantum key distribution
18.3 Reduced density matrices and the Schmidt decomposition
18.4 The impossibility of perfect bit commitment
18.5 More quantum cryptography
19 Quantum Machine Learning
19.1 Introduction
19.2 Supervised learning from quantum data
19.2.1 The PAC model of learning
19.2.2 Learning from quantum examples under the uniform distribution
19.2.3 Learning from quantum examples under all distributions
19.2.4 Learning quantum states from classical data
19.3 Unsupervised learning from quantum data
19.4 Optimization
19.4.1 Variational quantum algorithms
19.4.2 Some provable quantum speed-ups for optimization
20 Error-Correction and Fault-Tolerance
20.1 Introduction
20.2 Classical error-correction
20.3 Quantum errors
20.4 Quantum error-correcting codes
20.5 Fault-tolerant quantum computation
20.6 Concatenated codes and the threshold theorem
A Some Useful Linear Algebra
A.1 Vector spaces
A.2 Matrices
A.3 Inner product
A.4 Unitary matrices
A.5 Diagonalization and singular values
A.6 Tensor products
A.7 Trace
A.8 Rank
A.9 The Pauli matrices
A.10 Dirac notation
B Some other Useful Math and CS
B.1 Some notation, equalities and inequalities
B.2 Algorithms and probabilities
C Hints for Exercises