Quantum Computing: Algorithms and Limitations Through the Query Model

ABOUT THE COURSE:Quantum Computation captured the imagination of computer scientists with the discovery of efficient quantum algorithms for factoring and fast algorithm for search. With the recent advances in quantum hardware, quantum computing has once again grabbed the limelight.This course will primarily focus on the mathematical and computer science aspect of it. After covering the motivation and basics for quantum computing, we will move to the circuit model and take lots of examples. The main part of the course will look at quantum algorithms and the advantage they offer over classical counterparts.Our focus will be to learn these algorithms and lower bounds as an extension to already known techniques in classical and randomized computation. The course will focus on giving computer science perspective to this interdisciplinary field.INTENDED AUDIENCE: Computer scientist and mathematicians who would like to understand the basics of quantum algorithmsPREREQUISITES: Linear Algebra and ProbabilityINDUSTRY SUPPORT:Quantum Technology Companies & StartupsGovernment & Research LabsSoftware consulting firms

Syllabus

Week 1: What is quantum computing? Quantum weirdness: Mach-Zehnder interferometer.
Week 2:Linear algebraic formulation of states: deterministic, randomized and quantum, qubits, composite systems
Week 3:Operations in quantum computing, basics gates and circuits, Mach-Zehnder in terms of quantum operations.
Week 4:Semidefinite matrices, projectors, measurements in quantum computing, principle of deferred measurement
Week 5:Classical and quantum circuits, Deutsch (from Mach-Zehnder) and Deutsch-Jozsa, swap circuit
Week 6:Randomized computation with examples
Week 7:Simon’s algorithm, Quantum Fourier transform, its applications: phase estimation and Shor’s algorithm
Week 8:Grover search, amplitude amplification and variants
Week 9:Random walks and discrete time quantum walks
Week 10:Query model: classical and quantum, approximate degree, optimality of Grover search
Week 11:Total functions: at most polynomial separation between deterministic and quantum query complexity
Week 12:Super-quadratic separation: cheatsheet model, partial functions, Aaronson-Ambainis conjecture and Forrelation problem (depending on time).