Elective for UG+PG (CSE). Theory Stream (BTech CSE).Credits: 4Prerequisites: Linear Algebra, Probability, Analysis and Design of Algorithms Post Condition (on student capability after successfully completing the course): Understand the principles of quantum computing.
 Understand different quantum computing models used in different applications like search, numerical algorithms, cryptography, etc.
 Design and/or analyse quantum algorithms and circuits.
 Explain and/or implement simple algorithms and circuits from research papers.
Brief DescriptionThis 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, superdense coding and DeutschJozsa 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 circuit simulator (e.g., Microsoft LIQUi simulator, IBM quantum computer) to get a better feel about the system. Syllabus Principles of quantum computing (NC Ch1,2)
 Quantum circuit and Turing machine models. Basic complexity classes. (NC Ch3,4)
 Quantum Fourier transform, Simon’s algorithm, Shor’s algorithm, period finding and discrete logarithm. (NC Ch5)
 Grover’s search. Lower bound proofs for search. (NC Ch6)
 Advanced topics
Textbook
* [NC] Michael Nielsen and Isaac Chuang. Quantum Computation and Quantum Information, Cambridge * [KLM] Kaye, Laflamme and Mosca, An Introduction to Quantum Computing
ReferencesVideo lectures by Michael Nielsen
Evaluation
 25%  Midsem
 35%  Endsem
 25%  Homeworks (minimum dropped)
 10%  2 Quizzes
 5%  Paper presentation/report
 Must get 25% in avg of midsem & endsem to pass the course
 Final grade may be increased by one if student shows extraordinary signs of improvement
Paper Reading  Gautam Gupta:
 S. Dorn. Quantum algorithms for matching problems. Theory of
Computing Systems, 453:613–628, 2009.  E. D’Hondt. Quantum approaches to graph colouring. Theoretical
Computer Science, 410:302–309, 2009.  Peter Høyer, Jan Neerbek, and Yaoyun Shi: Quantum Complexities of
Ordered Searching, Sorting, and Element Distinctness
 Shanu:
 Boyer, Michel, Gilles Brassard, Peter Høyer, and Alain Tapp. "Tight bounds on quantum searching." arXiv preprint quantph/9605034 (1996).
 Brassard, G., Hoyer, P., Mosca, M., & Tapp, A. (2002). Quantum amplitude amplification and estimation. Contemporary Mathematics, 305, 5374.
 Rahul Gangopadhyay:
Cleve, R., & Watrous, J. (2000). Fast parallel circuits for the quantum Fourier transform. In Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on (pp. 526536). IEEE. Häner, T., Roetteler, M., & Svore, K. M. (2016). Factoring using 2n+ 2 qubits with Toffoli based modular multiplication. arXiv preprint arXiv:1611.07995.

Lec 
Date  Topic 
Notes 
1

03/01
 Basic of qubits and gates,beamsplitter experiment 
HW0: Familiarize yourself with IBM quantum experience and Microsoft LIQUi.

2 
05/01
 Linear algebraic basics of quantum computing: vector, bases, Hilbert space, multiqubit system

HW1 Due by 17th Jan, 10am.

3 
10/01
 Linear algebra basics: operators, evolution operators, measurement 
4 
12/01
 Entangled states


5 
17/01
 No cloning theorem, Teleportation

HW2 Due by 25th Jan, 5pm. 
6 
19/01
 Superdense coding, Teleportation as a primitive operation

Gottesman and Chuang, 99 (arXiv) 
7 
24/01
 Remote state preparation, probabilistic teleportation

HW3 Remote state preparation by Pati (arXiv) Probabilistic teleportation by Agrawal, Pati (2002)

8 
28/01
 Bloch sphere, single qubit gates, controlledU gates


9 
31/01
 MulticontrolledU gates, approximating gates, Spectral theorem

NC Ch4, KLM Ch4 
10

02/02
 Approximating quantum circuits

HW4 Due by 9th Feb anytime

11 
07/02
 Oracle gates, Phase kickback, Deutsch's algorithm


12 
09/02
 DeutschJozsa algorithm


13 
14/02 16/02
 Simon's algorithm


14 
28/02
 BernsteinVazirani problem

HW5 Due by 7th March in class

15 16

04/03
 Grover's search


16 17

07/03 09/03
 Applications of Grover's search

Quantum Query Complexity of Some Graph Problems

18 
21/03
 Quantum Fourier transformation

NC Ch5.1

18 19

23/03 28/03
 Quantum Phase Estimation


20 21

30/03 04/04
 Shor's Factoring Algorithm

HW6

22 23

06/04 11/04
 QFT applications: Draper, Hoyer Spalek

Addition on a Quantum Computer (Draper) Quantum Circuits with Unbounded Fanout

24 
 Paper reading/presentation


25 
 Paper reading/presentation 

26 
 Paper reading/presentation 


Updating...
Ċ Debajyoti Bera, Jan 12, 2017, 1:16 AM
Ċ Debajyoti Bera, Jan 18, 2017, 4:09 AM
Ċ Debajyoti Bera, Feb 2, 2017, 2:21 AM
