Quantum Computing - Winter 2018

https://docs.google.com/a/iiitd.ac.in/viewer?a=v&pid=sites&srcid=aWlpdGQuYWMuaW58Y3NlNjIyLXcxOHxneDo1NTcxMDllMWFmM2UyMWUwElective for UG+PG (CSE).  Credits: 4

Pre-requisites : 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 Description

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 circuit simulator (e.g., Microsoft LIQUi simulator, IBM quantum computer) to get a better feel about the system.

Syllabus

  • Principles of quantum computing (NC Ch-1,2)
  • Quantum circuit and Turing machine models. Basic complexity classes. (NC Ch-3,4)
  • Quantum Fourier transform, Simon’s algorithm, Shor’s algorithm, period finding and discrete logarithm. (NC Ch-5)
  • Grover’s search. Lower bound proofs for search. (NC Ch-6)
  • 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

References

Video lectures by Michael Nielsen

Evaluation

  • 35% - Midsem
  • 40% - Endsem
  • 15% - Homeworks (minimum dropped)
  • 5% - 1 or 2 Quizzes
  • 5% - Paper presentation/report
  • Must get 33% in avg of midsem & end-sem to pass the course
  • Final grade may be increased by one if student shows extra-ordinary signs of improvement

Tentative Ouline

 Lec  DateTopic Notes 
 1 02/01
 Basic of qubits and gates Lec 0
Lec 1
NC Ch-1
 2 05/01
 Linear algebraic basics of quantum computing: vector, bases, Hilbert space, multi-qubit system
Lec 2
Lec 3

NC Ch-2
HW1: Due 16th before class.
 3 09/01
 Linear algebra basics: operators, evolution operators, measurement
 4 12/01
 No cloning theorem, Teleportation, Superdense coding (NC Ch-1,2)
Lec 4
 5 16/01
 Measurement & entangled pairs
Gottesman and Chuang, 99 (arXiv)
Remote state preparation by Pati (arXiv)
Lec 5
 6 23/01
 Deutsch & Deutsch-Jozsa algorithms (NC Ch-1)
Quiz-1
Lec 6
HW2: Due 30th before class.
 7 30/01
 Elitzur-Vaidman's bomb,
Recursive Fourier sampling
Lec 7
 8
02/02
 Bernstein-Vazirani, Complexity classes
Lec 8
 9
 10
06-09/02
 Simon's problem
 Partial Simon paper (Appendix-A)
Lec 9, 10
HW 3: Due 16th before class.
 11 13/02
 Grover's algorithm for search
Lec 11
 1216/02
 Amplitude amplification
BHMT[Sec 2],  BHT
   Mid-sem Exams
 
 13
 14
06/03
09/03
 Spectral theorem, quantum circuit approximation, state and operator discrimination
NC Ch-2.2.3-6, KLM A.9
USD review         HW4
Lec 13   Lec 14
 15
13/03Trace operator, Density operator, quantum gates NC2.4 NC4
 16
16/03
no class
 
 17
 18
20/03
23/03
 Multi-qubit gates, Circuit parallelization
Quantum Fan-out is powerful (Sec 3, 4.1) Lec17
Lec 18
 19 03/04Quantum Fourier transformation, Phase estimation
NC Ch-5.1, KLM 7.1 Lec 19
 2006/04Factoring and Eigenvalue estimationKLM 7.2, 7.3 Lec 20 (last year's notes)
 21 10/04Quiz Quiz-2 HW5: Due 20th April before class.
 2213/04 QKD - BB84, Bell's inequalityLec 22
 2316/04 Quantum counting, Ekert91 protocolNC6.3 Lec 23
 2417/04Quantum cryptography paper-1 paper-2Lec 24
 2620/04 Quantum cryptography Grover meets Simon paperLec 26


Ċ
Lec0.pdf
(1561k)
Debajyoti Bera,
Jan 2, 2018, 5:15 AM
Ċ
Lec1.pdf
(277k)
Debajyoti Bera,
Jan 2, 2018, 5:15 AM
Ċ
Lec11.pdf
(293k)
Debajyoti Bera,
Feb 13, 2018, 12:50 AM
Ċ
Lec2.pdf
(398k)
Debajyoti Bera,
Jan 5, 2018, 12:42 AM
Ċ
Lec24.pdf
(17033k)
Debajyoti Bera,
Apr 26, 2018, 3:22 AM
Ċ
Lec3.pdf
(227k)
Debajyoti Bera,
Jan 8, 2018, 11:49 PM
Ċ
Lec4.pdf
(204k)
Debajyoti Bera,
Jan 22, 2018, 10:24 PM
Ċ
Lec5.pdf
(70k)
Debajyoti Bera,
Jan 22, 2018, 10:25 PM
Ċ
Lec6.pdf
(149k)
Debajyoti Bera,
Jan 22, 2018, 11:47 PM
Ċ
Lec7.pdf
(446k)
Debajyoti Bera,
Jan 30, 2018, 1:20 AM
Ċ
Lec8.pdf
(208k)
Debajyoti Bera,
Feb 2, 2018, 12:52 AM
Ċ
Debajyoti Bera,
Feb 9, 2018, 1:14 AM
Ċ
hw1.pdf
(102k)
Debajyoti Bera,
Jan 9, 2018, 2:15 AM
Ċ
hw2.pdf
(121k)
Debajyoti Bera,
Jan 30, 2018, 1:01 AM
ċ
hw3.txt
(1k)
Debajyoti Bera,
Feb 9, 2018, 1:16 AM
Ċ
hw4.pdf
(117k)
Debajyoti Bera,
Mar 13, 2018, 2:18 AM
Ċ
hw5.pdf
(117k)
Debajyoti Bera,
Apr 11, 2018, 12:28 AM
Ċ
lec13.pdf
(15510k)
Debajyoti Bera,
Apr 11, 2018, 9:34 PM
Ċ
lec14.pdf
(815k)
Debajyoti Bera,
Apr 11, 2018, 9:42 PM
Ċ
lec17.pdf
(16309k)
Debajyoti Bera,
Apr 11, 2018, 9:35 PM
Ċ
lec18.pdf
(14764k)
Debajyoti Bera,
Apr 11, 2018, 9:35 PM
Ċ
lec19.pdf
(3981k)
Debajyoti Bera,
Apr 11, 2018, 9:45 PM
Ċ
Debajyoti Bera,
Apr 11, 2018, 9:47 PM
Ċ
lec20.pdf
(2588k)
Debajyoti Bera,
Apr 11, 2018, 9:45 PM
Ċ
lec22.pdf
(3470k)
Debajyoti Bera,
Apr 26, 2018, 3:24 AM
Ċ
lec23.pdf
(3300k)
Debajyoti Bera,
Apr 26, 2018, 3:24 AM
Ċ
lec24.pdf
(1887k)
Debajyoti Bera,
Apr 26, 2018, 3:24 AM
Ċ
lec26.pdf
(2724k)
Debajyoti Bera,
Apr 26, 2018, 3:24 AM
Ċ
quiz1.pdf
(82k)
Debajyoti Bera,
Jan 23, 2018, 2:09 AM
Ċ
quiz2.pdf
(108k)
Debajyoti Bera,
Apr 11, 2018, 12:28 AM