Quantum Computing Course Outline
Module 1: Introduction to Quantum Computing
- What is Quantum Computing?
- Quantum Mechanics
- Qubits and Quantum Memory
- Elementary Gates
Module 2: Overview of Circuit Model and Deutsch-Jozsa
- Classical Circuits
- Quantum Circuits
- Universality of Various Sets of Elementary Gates
- Quantum Parallelism
- Early Algorithms
Module 3: Simon’s Algorithm and Fourier Transform
- Simon’s Algorithm
- Problem
- Quantum Algorithm
- Classical Algorithms for Simon’s Problem
Module 4: Fast Fourier Transform
- Classical Discrete Fourier Transform
- Fast Fourier Transform
- Application: Multiplying Two Polynomials
- Quantum Fourier Transform
Module 5: Shor’s Factoring Algorithm
- Factoring
- Shor's Period-Finding Algorithm
- Continued Fractions
Module 6: Hidden Subgroup Problem
- Group Theory Reminder
- A General Algorithm for Abelian HSP
- Non-Abelian QFT on Coset States
Module 7: Grover’s Search and Quantum Walk Algorithm
- Grover’s Algorithm
- Amplitude Amplification
- Quantum Walk
- Applications
Module 8: Hamiltonian Simulation and HHL Algorithm
- Hamiltonians
- Methods of Hamiltonian Simulation
Module 9: Introduction to HHL Algorithm
- What is HHL Algorithm?
- Linear System Problem
- HHL Algorithm for Linear Systems
- Improving HHL Algorithm Complexity
Module 10: Quantum Query Lower Bounds
- Introduction
- Polynomial Method
- Quantum Adversary Method
Module 11: Quantum Complexity Theory
- Introduction to Quantum Complexity Theory
- Classical and Quantum Complexity Classes
- Classically Simulating Quantum Computers in Polynomial Space
Module 12: Quantum Encodings with a Non-Quantum Application
- Mixed States and General Measurements
- Quantum Encodings and Their Limits
- Lower Bounds on Locally Decodable Codes
Module 13: Quantum Communication Complexity
- Classical Communication Complexity
- Quantum Question
Module 14: Entanglement and Non-Locality
- Quantum Non-Locality
- CHSH: Clauser-Horne-Shimony-Holt
- Magic Square Game
Module 15: Introduction to Quantum Cryptography
- Quantum Key Distribution
- Reduced Density Matrices and the Schmidt Decomposition
- Impossibility of Perfect Bit Commitment
Module 16: Error-Correction and Fault-Tolerance
- Introduction
- Classical Error-Correction
- Quantum Errors
- Quantum Error-Correcting Codes
- Fault-Tolerant Quantum Computation
- Concatenated Codes and the Threshold Theorem