CSE622 Introduction to Quantum Computing Winter 2024

This is an introductory course about designing solutions for computation problems using the quantum computing models. It has been shown that these models allow us to solve certain problems more efficiently compared to classical platforms (like Digital circuits or Turing machines). On the other hand, there are certain scenarios where this model is siimlar or even worse than classical platforms. In this course a student will learn about the models and interesting solutions (circuits, algorithms) for some problems from the perspective of computer science. The first half of the course will introduce the postulates of quantum computing, operations and operators and basic structure of circuits and algorithms on the circuit model and the Turing machine model. We will also cover some simple but amazing solutions like quantum teleportation, super-dense coding and Deutsch-Jozsa algorithm. The second half of the course will cover important algorithmic tools like the quantum Fourier transformation, amplitude amplification and eigenvalue estimation and discuss important algorithms like Grover’s search, Shor's factoring, BB84 protocol which bring significant efficiency compared to classical algorithms. Depending upon time and interest, some recent advances will be covered. Students may have to read a recent/classical research paper and/or simulate some of their algorithms and circuits on some quantum backend (e.g., IBM quantum computer) to gain a solid understanding about the system.

Pre-requisites

All of the following are strict requirements. The course relies heavily on linear algebra and algorithms.
You are expected to be comfortable with the following prior concepts:

If you are not familiar or comfortable with these concepts, then you must do a self-study before joining the course (you are recommend to solve a few problems in those concepts from any textbook; mere reading of concepts may not provide sufficient depth); this book chapter explains the linear algebraic concepts suitable for quantum computation in one place.

Course Objectives

  1. Understand the principles of quantum computing.
  2. Understand different quantum computing models used in different applications like search, numerical algorithms, cryptography, etc.
  3. Design and/or analyse quantum algorithms and circuits.
  4. Explain and/or implement simple algorithms and circuits from research papers.

Evaluation Policy

Evaluation will be based on homeworks, closed-book proctored midsem and endsem exams, and project/survey.

Course Personnel and Office Hours

All office hours will take place on the Meet Link given on Classroom.

Debajyoti Bera - dbera@ - TBA (email me if you want meet at some other time)
Tharrmashastha - tharrmashasthav@ - TBA

Weekly Schedule

Lecture No. Date Theme Topics
1 8 Jan 2024 Single qubit system Hilbert space, ket-bra notation, Hadamard gate, Superposition
2 10 Jan 2024 Single qubit system Inner product, Linear operators, Spectral decomposition, Projective measurement, B92 protocol
3 15 Jan 2024 Single qubit system Evolution, Operator function, Rotation gates, Important single qubit gates, identification of states
4 17 Jan 2024 Multiple qubits Tensor product, Hadamard basis, CNOT gate, Bell states, Entanglement, No-cloning theorem
5 22 Jan 2024 Bell States Partial evolution, Partial measurement, Teleportation
6 24 Jan 2024 Bell States Measuring B11 in any basis, Time-invariance of B11, Remote state preparation
Building blocks Input representation in quantum circuits, Oracle/query model, Parameterized circuit model
26 Jan 2024 HW1 Due
7 29 Jan 2024 Building blocks Amplitude & Basis encoding, single-qubit gates, multi-qubit & controlled-gates, phase kickback
8 31 Jan 2024 Simple algorithms SWAP test, Hadamard test, H-U-H framework, Deutsch & Deutsch-Jozsa algorithm
9 5 Feb 2024 Simple algorithms Algorithmic frameworks: Amplitude amplification, QPE, Hamiltonian simulation
10 7 Feb 2024 Quantum ML/Dhiraj Madan Quantum variational algorithms, VQE
12 Feb 2024 NO CLASS (Friday timetable)
11 14 Feb 2024 Quantum ML/Dhiraj Madan QSVM
12 19 Feb 2024 Amplitude Amplification Review, Exact amplification, Amplification for unknown theta
13 21 Feb 2024 Amplitude Amplification Exact amplification, Minimum finding, Finding all solutions, Finding top-K
MIDSEM EXAM (syllabus: all of the above)
14 11 Mar 2024 Hamiltonian Simulation Reducing MaxCut to ground state computation, QUBO, VQE, Simulation on gate-based QPUs
15 13 Mar 2024 Hamiltonian Simulation Quantum annealing, Trotterization
16 18 Mar 2024 Hamiltonian Simulation QAOA, Error analysis of Hamiltonian simulation for unordered search
17 20 Mar 2024 QFT Review of DFT, QFT, QFT on periodic states, Reduction of factoring to order finding
25 Mar 2024 HOLI
18 27 Mar 2024 QFT Shor's quantum algorithm for order finding
19 1 Apr 2024 QFT Circuit for QFT, Watrous-Cleve optimized circuit
20 3 Apr 2024 QFT QPE, Kitaev's algorithm, QFT-based algorithm
21 8 Apr 2024 Quantum complexity Simon's algorithm, forrelation, query complexity
22 10 Apr 2024 QFT Applications of QFT: Amplitude estimation
23 15 Apr 2024 Quantum Information Theory Density matrix representation
17 Apr 2024 NO CLASS (Holiday)
24 22 Apr 2024 Quantum Information Theory Density matrix representation
25 24 Apr 2024 Advanced topics HHL algorithm (not in syllabus)
26 29 Apr 2024 Review Review

Homeworks

  1. Homework 1
  2. Homework 2
  3. Homework 3
  4. Homework 4
  5. Homework 5