Quantum Computing - Winter 2017

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):
  • 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

  • 25% - Midsem
  • 35% - Endsem
  • 25% - Homeworks (minimum dropped)
  • 10% - 2 Quizzes
  • 5% - Paper presentation/report
  • Must get 25% 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

Paper Reading

  • Gautam Gupta:
    • S. Dorn. Quantum algorithms for matching problems. Theory of
      Computing Systems, 45-3: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 quant-ph/9605034 (1996).
    • Brassard, G., Hoyer, P., Mosca, M., & Tapp, A. (2002). Quantum amplitude amplification and estimation. Contemporary Mathematics, 305, 53-74.
  • 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. 526-536). 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.

Tentative Ouline

 Lec  DateTopic Notes 
 1 03/01
 Basic of qubits and gates,beam-splitter experiment HW0: Familiarize yourself with IBM quantum experience and Microsoft LIQUi.
 2 05/01
 Linear algebraic basics of quantum computing: vector, bases, Hilbert space, multi-qubit 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,
controlled-U gates

 9 31/01
 Multicontrolled-U gates, approximating gates, Spectral theorem
NC Ch-4, KLM Ch-4
 10
02/02
Approximating quantum circuits
HW4 Due by 9th Feb anytime
 11 07/02
Oracle gates, Phase kick-back, Deutsch's algorithm

 12 09/02
Deutsch-Jozsa algorithm

 13 14/02
16/02
Simon's algorithm

 14 28/02
Bernstein-Vazirani 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 Ch-5.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 Fan-out
 24
 Paper reading/presentation

 25
 Paper reading/presentation
 26
 Paper reading/presentation


Ċ
hw1.pdf
(93k)
Debajyoti Bera,
Jan 12, 2017, 1:16 AM
Ċ
hw2.pdf
(74k)
Debajyoti Bera,
Jan 18, 2017, 4:09 AM
Ċ
hw4.pdf
(113k)
Debajyoti Bera,
Feb 2, 2017, 2:21 AM