Prequisites: Familiarity with basic Linear algebra and Probability

Course Objective:

The course aims to serve as an introduction to the quantum computational model with the goal of understanding basic quantum algorithms and analyzing them. The course also addresses limitations of quantum algorithms and introduces the necessary tools and techniques to prove the same.

Course Content:

Brief review of linear algebra and probability preliminaries. (1 lecture)

Basic notions: Qubits, Dirac’s notation, operations on qubits, unitary operators and matrix representations. Single qubit gates - Hadamard, Rotation, NOT and Phase gates. Multi-qubit gates – CNOT, Toffoli. SWAP test. (3 lectures)

Quantum circuits, Church-Turing hypothesis and extensions, Universality of quantum circuits (1 lecture)

No cloning theorem, Relation to probabilistic computation, Bell pair, EPR paradox (5 lectures)

Quantum Oracles, Quantum algorithms for promise problems: Deutsch-Jozsa, Bernstein-Vazirani and Simon (4 lectures)

Phase estimation, Eigenvalue estimation and Quantum Fourier Transforms. (6 lectures)

Searching in an unstructured database: Grover search – geometric and diffusion views. Quantum walks. Optimality of Grover search. (4 lectures)

Shor’s algorithm for factoring. Order finding, Period finding, Reductions. (7 lectures)

Quantum algorithms for hidden subgroup, element distinctness, collision detection and triangle counting problems. (4 lectures)

Lower bounds. Adversary method, polynomial method, quantum query complexity (3 lectures)

Quantum Complexity Theory. Complexity class BQP and its connections to classical computation. (2 lectures)

Advanced topics in quantum computation (if time permits) like Noisy intermediate scale quantum models, quantum error correction and quantum proofs for classical theorems (2 lectures)

Learning Outcomes:

  1. Being able to analyze simple quantum algorithms and argue optimality.
  2. Familiarity with 1-qubit / 2-qubit gate operators and ability to design simple quantum circuits.
  3. Ability to read and understand recent results as well as research papers on quantum algorithms

Remark: This course has less than 20% overlap with PH5606 Quantum Information and Computation offered by the Physics department, IIT Palakkad. Due to this, students who have already done PH5606 may be allowed to credit this course.

Text Books

  1. Quantum Computation and Quantum Information by Michael A. Nielsen and Isaac L. Chuang (ISBN-13:978-1107002173)
  2. An Introduction to Quantum Computing by Phillip Kaye, Raymond Laflamme and Michele Mosca (ISBN-13:9780198570493)
  3. Quantum Algorithms via Linear Algebra: A Primer by Richard J. Lipton and Kenneth W. Regan (ISBN: 978-0262028394)

References

  1. Quantum Computing since Democritus by Scott Aaronson (ISBN:9780511979309)
  2. Quantum Computing Notes by Ronald de Wolf
  3. Quantum Proofs for Classical Theorems by Andrew Drucker and Ronald de Wolf

Past Offerings

Course Metadata

Item Details
Course Title Quantum Computing
Course Code CS5638
Course Credits 3-0-0-3
Course Category PME
Proposing Faculty Srimanta Bhattacharya and Krishnamoorthy Dinesh
Approved on Senate of IIT Palakkad
Course status New