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.);