Updated April 10, 2005
This course has no prerequisites and the necessary
background in linear algebra, algebra and quantum mechanics will
be included in this self-contained first level course.
Undergrads in their second and third year (B Tech and M Sc)
must meet their respective
faculty advisors to register for this course, possibly
treating it as
an additional elective, if not as a breadth elective.
For 10th semester Dual degree (CSE) and 8th semester B. Techs (CSE),
this is an elective in the regular elective list in slot B.
For UGs from other departments and dual degree students, this course
can be a breadth elective.
====================================================
====================
Students registered:
=======================
Anil Kumar (02CS1034), Arunim Gupta (00MA2014),
Avradip Mandal (01EC1022), Saikat Ghosh (01CS1024), Abhik Kumar Das (00EC3002),
Bharat D. Dravid (00MA2021), V. L. Subrahmanyam (01CS1012),
Arpan Chatterjee(01IE1007).
========================
TAs:
Sima Das (Ph D scholar) and Devendra Desai (M Tech II yr, 2003 batch)
-----------------
Syllabus:
Mathematical foundations; quantum mechanical principles and concepts; qubits,
quantum entanglement; reversible computation, quantum gates and registers;
universal gates for quantum computation; quantum parallelism and simple
quantum algorithms; quantum Fourier transforms and its applications, quantum
search algorithms; elements of quantum automata and quantum complexity theory;
introduction to quantum error correcting codes; entanglement
assisted communication; elements of quantum information theory and quantum
cryptography.
------------ Main texts:
(0) M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum
Information, Cambridge University Press, 2000.
(1) Jozef Gruska, Quantum Computing, McGraw Hill, 1999.
-----------
References:
(00) Lecture notes by John Preskill.
http://www.theory.caltech.edu/people/preskill/ph229/
(01) Lecture Notes by N. D. Mermin.
http://people.ccmr.cornell.edu/~mermin/qcomp/CS483.html
(02) Chris. J. Isham, Lectures on Quantum Theory: Mathematical and
Structural Foundations, Imperial College Press, 1995
(03) D. Bouwmeester, A. Ekert and A. Zeilinger, editors,
The Physics of Quantum Information, Springer, 2000
(04) H.-K. Lo, S. Popesku and T. Spiller, Editors, Introduction to
Quantum
Computation and Information, World Scientific, 1998
(05) M. D. Srinivas, Measurements and Quantum Probabilities,
Universities Press (India), 2001
(06) I. N. Herstein, Topics in Algebra, 2nd Edition,
John Wiley and Sons, 1999
(07) E. Kreyszig, Introductory Functional Analysis with Applications,
John Wiley and Sons, 1978
(08) R. Bhatia, Matrix Analysis, Springer, 1997
(09) Paul R. Halmos, Finite dimensional vector spaces, Princeton Univ.
Press.
(10) Bela Bollobas, Linear Analysis, Cambridge University Press, 1990.
(11) Los Alamos Quant_ph archive.
http://www.arxiv.org/archive/quant-ph
(12) T. H. Cormen, C. E. Leiserson and R. L. Rivest,
Introduction to Algorithms, MIT Press (1990)
(13) Mika Hirvensalo, Quantum Computing, second Edition, Springer, 2004.
(14) Arthur O. Pittenger, An introduction to quantum computing
algorithms, Birkhauser, Progress in Computer Science and Applied
Logic, 2001.
(15) Sakurai, Modern quantum physics.
(16) Approaching Quantum Computing by Marinescu and Marinescu.
----------------------------------------
Elementary Quantum Algorithms.
=========================================================================
Lectures in Jan 2005 began with the definitions and notions of Hilbert spaces
and inner products on the one hand and the two-slit experiments illustrating
periodic interference of particle waves. The presence of detectors in
the form of light photons discovering particles by colliding with them and
then being trapped in detectors was used to illustrate how the interference
patterns get disturbed on detection, as described in Feynman's third volume.
We also studied the essence of Stern-Gerlach kind of observations as mentioned
in
the Spring 2004 course page. We introduced the notions of evolution of
quantum systems, linear and unitary, and also the notion of projective
measurements. Notions of tensor products and their properties, the
four postulates of quantum mechanics, some linear algebra basics for Hilbert
spaces, particularly notions and characterizations regarding eigenvalues and
eigenvectors were dealt with.
=======================================================
Assignment 1, CS60070 Spring 2005
Dated Jan 06, 2005 submission by Jan 15, 2005.
----------------------------------------------
[ NOTE: [N & C ] means Nielsen and Chuang's text]
(I) Pauli matrices
(0) Show that X, Y and Z are unitary and Hermitian.
(ii) Ex. 2.11 [N & C]
(II) Cauchy-Schwartz inequality
Ex. Box 2.1 [N & C]
(III) Gram-Schmidt procedure
Ex. 2.8 [N & C]
(IV) Real eigenvalues.
Ex. 2.17 [N & C]
(V) Orthonormal eigenbasis
Ex 2.22 [N & C]
(VI) Show that unitary operators preserve inner products, that is,
< U|A> | U|B> >=< |A> | |B> >
(VII) Reading exercise Box 2.2 [N & C]
Spectral theorem for normal operators.
-----------------------------------------------
=========================================================================
Assignment #2 submissions by Jan 31 and late submissions by Feb 7.
=======================================================================
Assignment #3 submssions by Feb 10.
(1) Chapter 6 from Mika's book: particularly, concerning the function
in eqn 6.1, section 6.1.3 and section 6.2.
(2) Section 6.2.3 from Mika's book after (1) is done.
(3) See illustration of Grover search numerical example in Pittenger's book.
(4) Section 5.1 from Mika's book and corresponding material from Gruska's book
on Simon's problem.
(5) Application of Yao's lemma as in Gruska's book for Simon's problem.
(6) Write a consolidated term paper or report on (1) through (5) by February 10,
2005 and submit within February 10, for evaluation.
========================================================================
Assignment #4, submissions by March 10, 2005.
========================================================================
Assignment #5, submissions by March 14, 2005.
========================================================================
Assignment #6, submission by March 21, 2005.
(i) What is the usual naive method of factoring a product m=pq of two primes?
How can you speed up this process using quantum means?
(ii) How can you use Grover's search for solving the 3SAT problem? Analyse the
time complexity and probabilities of error.
========================================================================
Assignment #7, submission by March 22, 2005.
Reading excerices from [N & C]
Chapter 6, section 6.1 and Chapter 5, Theorems 5.1 and 5.2.
Problems:
(i) Exercises 6.1 through 6.6.
(ii) Exercises 5.17 through 5.19
===========================
Seminar Topics:
==============
(1) Arpan-- Quantum coin flipping.
(2) Bharat-- Quantum key distribution.
(3) Avradip-- Quantum secret sharing.
(4) Avik-- Quantum channel capacities.
(5) Saikat-- Universality of quantum gates.
(6) V. L.-- Quantum computation of transforms.
(7) Anil-- Quantum complexity classes.
(8) Arunim-- Quantum cryptography.
Seminars will be conducted in the weeks starting April 4, 2005. Before
each seminar, a complete report in latex is required to be submitted.
====================================
Lectures in March 2005 covered notions and results on
Shannon entropy, and its corresponding relative, joint, conditional
entropies as well as mutual information.
These were accompanied by problem sessions and corresponding definitions
and results for von Newmann entropy. We reintroduced mixed states
through the notion of Shannon entropy of an classical ensemble of orthogonal
pure states.
We also studied arbitrary classical ensembles of (mixed) quantum states and
the von Newmann entropies of such states, bipartite states,
and entangled states. Finally we studied Holevo's bound and its applications.
A snapshot of our studies are evident in the following exercises, as
assignments.
=================
Assignment #8, submission by March 31, 2005.
All from [N & C]
(i) Ex. 11.1, 11.2, 11.3 and 11.4.
Study Theorems 11.1 through 11.10.
(ii) Ex. 11.5, 11.6, 11.7.
(iii) Ex. 11.10, 11.11, 11.12.
(iv) Ex. 11.13, 11.14, 11.15.
==========
Assignment #9, submission by April 4, 2005.
All from [N & C]
(i) Ex. 11.16, 11.17.
Study Theorems 11.15 and 11.16 and 12.1 and Box 12.1.
(ii) Ex. 12.2
(iii) Ex. 12.3 and 12.4.
============================
Seminar by Avik Das April 4, 2005 will continue at 7:30 am April 5, 2005.
The brainstorming considered Shannon's noiseless channel capacity theorem
following the "typical sequences"
theorem and sketched the quantum analog in "typical subspace" theorem, finally
pointing towards the non-trivial generalization, Schumacher's noiseless
channel capacity theorem, to be continued in the 2nd week of April.
===============================
Seminar by Avradip on quantum secret sharing started with examples of a (2,3)
scheme using qutrits and a (3,3) scheme using qubits. He also argued the basis
for two fundamental results on the conditions restricting t wrt n in (t,n)
schemes. He will continue later in April second week after others start
speaking on different topics.
================================
Seminar by V L Subramanyam started with the basis for choosing the
Shannon entropy definition function from fundamental arguments and observing
the uniqueness of the H() function. He also related Huffman coding and used
it to show that entropies add up for independent random sources, giving
joint entropy. He will lead us through entropy and other discussions finally
in to error correcting codes, classical and quantum. The underlying theme
will be connecting classical and quantum notions, showing and observing how
classical theory has its counterparts in quantum cases as well. He will continue
later in April.
======================================================
Seminar by Bharat Dravid began with notions of disturbance arising out
of attempts to extract information from a source of two non-orthogonal states.
He also introduced the notion of collision entropy. He discussed the use of
random universal hash functions and the lower bounds on conditional
collision entropy (and conditional entropy) of the hashed shared
secret string given the knowledge of the hash function and the eavesdropper's
knowledge z about a specific instance of the protocol.
==========================================
Anil Kumar contrasted DTMs, NDTMs, probabilistic TMs and QTMs, defining
classes of languages with bounded error (like BPP) that are accepted in
polynomial time by QTMs. More to follow.
==============================================