Updated April 21, 2006; Email: spp@iitkgp.ac.in spp@cse.iitkgp.ernet.in

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: Arijit Ghosh (03CS3007, Credit), Debapriya Chatterjee (03CS1017, Credit), Angik Sarkar (03EE1003, Credit), Anupam Prakash (Credit), Susmit Kumar Jha (02CS1037, Credit), Arka Majumdar (03EC1024, Credit), Rushin Shah (03CS3012), Rahul Gokhale (05CS6008, Credit), Hrishikesh Bhattacharya (02CS1010, Credit), Himanshu Sharma (03PH2014, Audit), Subhankar Mitra (02CS3016, Credit), Amit R. Goyal (02CS3012, Credit).

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

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.

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

Lectures on Jan 09, 2006

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

Introduction to computations, deterministic, non-deterministic, randomized and quantum; notions of space complexity, the class PSPACE and informal account of BQP, BPP and P; basic operations like X, Z and H, multiparty H operations, parity, boolean inner products mod 2; the notion of lower bounds and the result of Cleve, van Dam, Nielsen and Tapp (quant-ph/9708019 v3).

Lectures on Jan 10, 2006

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

Superpositions and intereference: the two-slit experiment, detector(s) for determining path of electrons, correlation between absence of interference patterns and the ability to detect the paths of electrons, effect of wavelength of detecting photons, rate of firing of electrons.

Measurements: in X and Z bases, use of outer product projectors, introduction to spectral decomposition of observable Hermitian operators, eigenvectors and eigenvalues of such operators.

Introduction to entanglement: creation of Bell states using CNOT 2-qubit operations, argument that such states are not factorable into product states of two pure local qubit states.

Lectures on Jan 16, 2006

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

Spaces and operators, inner-product spaces, norms, distance metrics, Hilbert spaces, (dual space of ) functionals, adjoints.

Schwarz's lemma, triangle inequalities.

The 50% success algorithm for Deustch's problem, the deterministic algorithm.

Lectures on Jan 17, 2006

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

Revision of the deterministic solution to Deustch's problem; extension to boolean functions of n boolean variables and introduction of the natural promise (of balanced and constant), leading to the solution of the Deustch-Josza problem.

Solution to the Bernstein-Vazirani problem, discussion on the relationship between these problems.

Lectures on Jan 27, 2006

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

Relationship between DFT and QFT, Hadamard operation on multiple qubits as as a special case of QFT, QFT as a product of individual qubit pure states and the resulting circuits for QFT and inverse-QFT.

The relationship between a t-bit boolean register and its QFT, the natural consequence- using inverse--- QFT for estimating phase; using a black box unitary operator U, or rather, a C-U (controlled-U) circuit [along with its eigenvector state(s)], for building blocks that compute exponential powers of U; creating the QFT of the phase of the eigenvalue(s); using inverse-QFT and measuring the phase--- approximations using limited precision.

Using phase estimation for determining the period of a function--- to begin with, the function of modulo N multiplication of two registers; generating the eigenvectors and the circuit for the unitary operator, estimating phase s/r where r is the order and s ranges with equal probability from 0 through r-1; probability calculation for getting a measurement p such that p differs from d times m/r by no more than 0.5; here m>n where 2^n=N. Such a p helps fishing out r using a continued fraction algorithm.

Lectures on Jan 30, 2006

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

Bernstein-Vazirani's problem; Simon's problem; revision of order finding and the analysis of 40% success probability in order finding; discussions on black box based problems and separations therein, versus the open questions about P, BPP and BQP separations.

Lectures on Feb 06, 2006

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

Tutorials on period finding and related results.

Lectures on Feb 10, 2006

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

Cleve and Buhrman's work (PRA 1997), on one cbit separation for 3-party (promise restricted) inner product.

Lectures on Feb 13, 2006

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

Generalization to multiple parties for certain communication complexity problems.

Lectures on Feb 24, 2006

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

Operators for Grover search and the search algorithm.

Lectures on March 03, 2006

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

Tutorial on communication complexity problems and on generalized Grover's search with multiple successes; introduction to Bell inequality violation.

Lectures on March 10, 2006

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

The 4d, two-party, non-contexually unsatisfiable set of nine equations (Kochen-Specker theorem), and the entanglement assisted contexuality game (quant-ph/0407221 and 0602064). The probablistics protocol with 3/4 success probability, its quantum entanglement assited counterpart with [cos(Pi/8)]^2>3/4 probability of success.

Class on March 17, 2006

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

Discussion on the entanglement-assisted non-locality game using the nine equations and 18 variables; Introduction to the Buhrman, Cleve, Wigderson (STOC 98) result of using communication protocols in Grover search, the case of set disjointness in particular; set equality classical protocols, with shared randomnes;

Lectures on March 20, 2006

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

Communication complexity problems and reductions: entanglement assisted as well as those based on Yao's qubit communication models; lower bounds for parity, upper bounds for boolean functions with alternating quantifiers, lower bound for two-party inner product from a non-trivial consequence of Holevo's theorem.

Lectures on March 24, 2006

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

Revision on the use of quantum parallelism in qubit exchange protocols and the Hadamard steps that lead to transfer of n cbits of information from one party to another.

Using the information theoretic quantity, Holevo's Chi, to show that any qubit protocol between Alice and Bob must cost at least n qubits overall and at least n/2 qubits fron Alice to Bob, provided n cbits of information is conveyed from Alice to Bob.

Use of Shannon and von Newmann entropies, (mutual information due to) mixed states being used to encode information in quantum states (and being retrieved by measuremnts at the other end); meaning and some special cases of Holevo's result.

Statement and use of subadditivity and Araki-Lieb inequalities; study of how each qubit communicated from Alice to Bob, would be accounted for by at most 2 units in mutual information, so at least n/2 qubits would be communicated for n cbit communication.

Tutorial on March 27, 2006

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

Shannon and von Newmann entropies and elements of quantum information theory; discussion on the proof of Holevo's result and use of density matrices and POVM measurements;

Shannon entropies

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

For a random source of symbols from a certain discrete distribution, we know that (as small as) expected H(X) bits of information can be used for coding information coming out of X. If p(x) is the probablity of x in X, then this (Shannon Entropy) H(X) or H(p(x)) is the sum over all x of [p(x) log (1/p(x))]. Once we have two such generators X and Y on the same set of symbols, we can define H(X,Y) as the sum over all pairs (x,y) of [p(x,y) log 1/p(x,y)] where p(x,y) is the probability that x comes out of X and y out of Y. If X and Y are independent (that is, p(x,y)=p(x)p(y)), then H(X,Y)=H(X)+H(Y), else H(X,Y) is less than the sum of H(X) and H(Y). Naturally, joint entropy is less than sum of entropies if the processes are dependent.

We may view the joint entropy H(X,Y) of X and Y as the sum of the entropy H(Y) of Y and the additional entropy H(X|Y) of X given Y. This defines H(X|Y), called the conditional entropy of X given Y, as a function of joint entropy and original entropies, as H(X|Y)=H(X,Y)-H(Y).

Furthermore, we may subtract the conditional entropy H(X|Y) of X given Y from H(X), to get the common information between X and Y, that is, H(X)-H(X|Y)=H(Y)-H(Y|X), ususally denoted as H(X:Y) or I(X:Y). We may now view H(X:Y) as H(X)-H(X|Y)=H(X)-[H(X,Y)-H(Y)]=H(X)+H(Y)-H(X,Y).

Quantum entropies (von Newmann entropies)

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

Quantum or von Newmann entropies are generalizations of Shannon entropies where the symbols conveyed by the random source of information are (not necessarily mutually orthogonal or even pure) quantum states. So, a distribution {p_x, x} in the classical case would be generalized here to a distribution {p_x, rho_x} where rho-x is the density operator for the mixed quantum state rho_x carrying the symbol with probability p_x. Even if all rho_x were pure states, they could be mutually non-orthogonal. Note that H(p_x) cbits of information can be extracted if the rho_x are mutually orthogonal pure states.

Exercises (QIT 1) : Submission by April 5, 2006

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

(1) Show that S(rho), the quantum entropy for a pure quantum state rho of one or more qubits can be zero, even if it is an entangled state.

(2) Show that tracing out one qubit q_B from a Bell state rho_{AB}, would leave the other qubit q_A in a state rho_A such that S(rho_A) is positive although S(rho_{AB}) is zero.

(3) Define S(X,Y) and S(X|Y) along lines similar to those for H(X,Y) and H(X|Y).

(4) Define I(X:Y), the mutual quantum information as S(X)+S(Y)-S(X,Y). What is I(X,Y) for Bell states (X,Y)? In the light of super-dense coding, would you expect a lower bound for I(X:Y)?

(5) Show that conditional quantum entropies can be negative, unlike conditional Shannon entropies.

(6) Use Schmidt decomposition to show that for bipartite quantum systems AB, in a pure state, S(A)=S(B).

(7) Establish the result of Schmidt decomposition of bipartite states.

(8) Show that S(rho) can never be negative for any density operator.

Lecture/Tutorial on March 31, 2006

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

Density matrices and von Newmann entropies for mixed, pure and entangled states, and of states left after tracing out a subsystem; identities and inequalities connecting various entropies; further discussions on techniques using information theory to establish communication complexity lower bounds, for qubit as well as cbit complexity.

Tutorial April 07, 2006

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

Use of non-decreasing von Newmann mutual information in the process of encoding a Shannon source with quantum states and decoding using POVM.

Use of functional notation S(r)= - tr (r log r) for density matrices r, in derivations.

Exercises (QIT 2) : Submission by April 5, 2006.

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

(1) Do the exercises 11.5, 11.6 and 11.7, and also study all the results in chapter 11 of [N & C].

(2) Show that H(X|Y) is the sum over (x,y) of p(x,y) log p(x|y) with sign negated. Why is this never negative unlike S(X|Y)?

(3) Show that Shannon and von Newmann entropies can never exceed log d where d is the dimension of the space.

(4) Suppose we do a unitary operation U over a multi-qubit states denoted by density operator rho. Would the von Newmann entropy change? Why?

(5) How would projective measurements change quantum entropy of a density operator? Why?

-----------------------------------------------------------------

Lectures on April 10, 2006

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

Detailed entropy calculations in the proof of Holevo's bound; Non-orthogonality of states and cloning; Ekert's and B92 QKD protocols;

-----------------------------------------------------------------

Lectures on April 14, 2006, 5 pm, CSE s/w Lab.

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

Introduction to secret sharing, of classical and quantum states (see Buzek, Hillery and Berthiume "Quantum secret sharing", and the paper "How to share a quantum secret" by Gottesman et al.);