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.

==============================================