Introduction to Quantum Computing and Quantum Algorithms

This course will cover the basic formalism of quantum states and quantum measurements, and introduce the circuit model of quantum computation. Basic results such as the Solovay-Kitaev theorem, no-cloning theorem, quantum entanglement and Bell's inequality will be discussed followed by the quantum Fourier transform (QFT) and quantum phase estimation (QPE), and cover some of its important applications such as the celebrated Shor's algorithm for integer factorization (other applications will be mentioned but not discussed in detail), Grover's algorithm for quantum search is covered next, and lower bounds for query complexity in this context; some basic concepts of quantum error correction and quantum entropy, distance between quantum states, subadditivity and strong subadditivity of von Neumann quantum entropy will also be covered. Time permitting, we will discuss some advanced algorithms such as the HHL algorithm for matrix inversion, VQE (variational quantum eigensolver) and the QAOA algorithm for optimization. Requires programming in Python, where the goal will be to familiarize the students to available software for quantum algorithm development, existing libraries, and also run some simple programs on a real quantum computer. Prerequisites: Linear algebra at the level of CME 200 / MATH 104, basic knowledge of group theory, and programming in Python. Additionally, some knowledge of real analysis will be helpful.