Quantum Computing - Winter 2015

Elective for UG+PG (CSE). Theory Stream (BTech CSE).
Credits: 4

Pre-requisites: Linear Algebra, Probability, Analysis and Design of Algorithms

Post Condition (on student capability after successfully completing the course):
  • Knowledge of principles of quantum computing
  • Knowledge of different quantum models of computation
  • Knowledge of a few important quantum algorithms
  • Exposure to applications of quantum computing to different computational areas (like cryptography, communication, complexity theory, etc.)

Brief Description

This is an introductory course on quantum computing from perspective of computer science. This course will introduce the students to the
postulates of quantum computing, formalisms like density matrices, effects of measurement. It will cover the quantum Turing machine and
quantum circuit models of computation, and discuss quantum Fourier transformation, Shor’s factoring and Grover’s search algorithms in
this model. Depending upon time and interest, some recent advances will be briefly covered from topics like quantum cryptography, quantum protocols, quantum complexity classes, impossibility results, etc.

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
* [RW] http://homepages.cwi.nl/~rdewolf/qcnotes.pdf
* [DB] http://courses.cs.washington.edu/courses/cse599d/06wi/

References

Video lectures by Michael Nielsen

Evaluation

  • 25% - Midsem
  • 35% - Endsem
  • 30% - Homeworks
  • 10% - Paper presentation

Paper Reading

1. http://arxiv.org/abs/quant-ph/0006004
Fast parallel circuits for the quantum Fourier transform

2. http://arxiv.org/abs/1207.4464
An Improvement in Quantum Fourier Transform

3. http://arxiv.org/pdf/quant-ph/0201117v1.pdf
Quantum Property Testing - by Digvijay Singh

4. http://link.springer.com/article/10.1007/s11128-012-0380-0
Dynamic quantum secret sharing - by Akshay Tomar


5. http://www.cse.sc.edu/~fenner/papers/cc-and-q.pdf

6. Bounds on the Power of Constant-Depth Quantum Circuits
http://arxiv.org/pdf/quant-ph/0312209

7. http://link.springer.com/article/10.1007/s11128-008-0091-8
Perfect computational equivalence between quantum Turing machines and
finitely generated uniform quantum circuit families

Ouline

Details of lectures are available on a separate page.

(italics signifies tentative)

 Lec  DateTopic Notes 
 1  5/1 Overview - model, space, state, input, operation, output, examples http://www.iiitd.edu.in/~dbera/docs/QuantumTalkIITD.pdf
NC1
 2  7/1 Linear algebraic basics of quantum computing - vector, bases, Hilbert space, Vaidman's Bomb NC2.1
RW-Appendix-A1,A2,A7
RW1
 3  12/1 Linear algebra - operators, evolution operators, measurement
 4  14/1 Multi-qubit system, no-cloning theorem  NC2.2
 5  19/1 Measurement of multi-qubit systems, Teleportation
 NC2
 6  21/1 Superdense coding
Quantum computing models - circuit, TM, automata
 NC2, NC4
 7  28/1 Deutsch's Circuit, Quantum gates
 NC1, NC4
 8  2/2 Deutsch-Jozsa, Quantum gates
 NC1, NC4
 9  4/2 Quantum gates, Universality
 NC4
 10
 9/2 Simon's Algorithm  RW2
 11  11/2 Simon's Algorithm, Randomized algo lower bound
 RW2
 12  16/2 Bernstein-Vazirani
 RW2 DB
 13  18/2 Simon's problem randomized lower bound
 RW2 DB
   Mid-sem exam 
 14  9/3 Discrete Fourier Transform
 CLRS(chapter on FFT), RW4
 15  11/3 Quantum Fourier Transform, Phase estimation
 NC5, RW5
 16  16/3 Eigenvalue estimation  NC5, RW5
 17  18/3 Order finding  NC5, RW5
 18  23/3 Shor's factoring algorithm
 NC5, RW5, Book by Kaye, Laflamme, Mosca
 19  25/3 Factoring algorithm (wrap-up) and Grover's unordered search  NC6, RW6
 20  30/3 Quantum counting
 NC6, RW6
 21  6/4 Quantum communication
 RW11
 22  7/4 Quantum circuit complexity
 Sec 3,4 of http://arxiv.org/abs/quant-ph/9903046
 23  8/4 Paper reading - preparation
 
 24  13/4 Paper reading - I, II
 
 25  15/4 Paper reading - III  
 26  20/4 Paper reading test