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