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)

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/

Evaluation

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

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

Dynamic quantum secret sharing - by Akshay Tomar5. 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