Updated April 19, 2004, 11:30 pm.
Those in second and third year must meet their respective faculty advisors to register for this course only as an additional elective creditor.
For 10th semester Dual degree (CSE) and 8th semester B. Techs (CSE), this is an elective in the regular elective list in slot C.
For UGs from other departments and dual degree students, this course can be a breadth elective.
Students registered: M Tech (CSE)- 2 (Devendra Desai and Rakesh Tripathi), MS (School of Information Technology)- 1 (Piu Mitra), Ph D scholars CSE- 1 (Sima Das), EE 4th year B Tech- 1 (Sagnik Pal), ECE 2nd year dual degree B Tech- 1 (Arko Nasipuri), CSE Dual degree 4th year- 1 (Jitendra Chauhan), Civil Engg. B Tech -1 (Mahesh Agarwal- Roll No. 02CE1008), CSE 2nd year B Tech- 3 (Chandrashu, Kapil Modi, Hrishikesh Bhattacharya), CSE B Tech 2nd year dual degree- 2 (Ravi Agrawal, Mithun Dhali), final year dual degree M Tech CSE- 1 (Gathala Sudha Anil Kumar).
Total: 14 students.
Syllabus:
-----------------
Mathematical foundations; quantum mechanical principles; quantum entanglement; reversible computation, qubits, quantum gates and registers; universal gates for quantum computing; 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 comunication; 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.
----------------------------------------
Click here for links on this topic
-----------------------------------------
-----------------------------------------
Assignment #1, CS60014 Spring 2004
Dated Jan 24, 2004 submission by Feb 09, 2004.
----------------------------------------------
[ 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, CS60014 Spring 2004
Dated Jan 30, 2004 submission by Feb 09, 2004.
----------------------------------------------
(I) Develop the unitary matrices for CNOT, Toffoli and Fredkin quantum gates.
(II) Show that Toffoli and Fredkin gates are each universal gates for classical reversible computation.
(III) Exercises 2.26 through 2.33 [N & C].
(IV) Reading exercise Box 2.3 [N & C].
(V) Show that M Hermitiam implies that the expectation of the observable M is < psi | M | psi> and that < psi | M^2 | psi > = || < M | psi > | M | psi > > ||.
(VI) Suppose we measure observables A and B in two different setups on two different occassions, for many identical states | psi >. Will the uncertainty relation (inequality) hold? Why? Suppose identical quantum states are being measured either in the observable A or in the observable B where the objects (say electrons) possesing the quantum states arrive one at a time in a year. Will the uncertainty inequality hold? Why?
-----------------------------------------------------------
-----------------------------------------------------------
Lectures on Jan 7, 2004
-----------------------
The two-slit experiment: the cases of (i) single slit patterns, (ii) two slit interference patterns, (iii) one perfect detector detecting an electron near its slit and the electron reaching the destination (iv) one imperfect detector detecting electrons reaching the destination and (v) either detector detecting the electron; explanation using probability amplitudes and the wave nature of these amplitudes (See Feynman's Vol III, Lectures on Physics, 1965 and Gruska).
Questions:
-------------------------------------------------
(i) How does the separation between the slits matter in this experiment?
(ii) Does the intensity, duration of experiment and the rate of electrions matter? How and Why?
---------------------------------------------------
The Stern-Gerlach experiment: the splitting of beams into two beams (in the Z direction), further splitting in an orthogonal X direction and then splitting again in the original direction Z direction. The notion of measurements in two bases. The notion of a qubit (See Nielsen and Chuang.)
Lecture on Jan 12, 2004
------------------------
The basic notions of quantum mechanics, the notion of a qubit versus that of a classical bit; inner-product spaces and Hilbert spaces; the notion of a quantum state, the first postulate of quantum mechanics and elementary transformations on a simple pure quantum state; Pauli matrices; the interpretation of the Hadamard operation and the Z operation, measurements of the transformed state in another basis.
Lecture on Jan 13, 2004
-----------------------
Eigenvalues and eigenvectors of transformations; more on pauli matrices X, Y and Z; Hermitian and unitary operators; unitary operations on quantum states; the spectral decomposition of Hermitian matrices, the real eigenvalues, the orthonormal basis of the eigenvectors; the evolution of quantum states and the second postulate of quantum mechanics; the fourth postulate for representing the state of a system in terms of its subsystems as tensor products, the definitions and elementary properties of tensors;
Lectures on Jan 14, 2004
------------------------
The third postulate of quantum mechanics, projective measurements and observables, measurements in computational basis; the expectation of an observable for a quantum state; mapping from microscopic quantum behaviour to macroscopic experimental statistics, the uncertainly principle of Heisenberg; introduction to quantum entanglement, the CNOT (controlled-not) operations, generation of the pure maximally entangled Bell state, the impossibility of its representation as the tensor product of two single-qubit states;
Lecture on Jan 19
----------------
The proof of the uncertainty principle, the notion of commutators and anti-commutators, properties for a pair of non-commutating observables (Hermitian operators), the use of Cauchy-Schwartz inequality for lower bounding the product of standard deviations for a pair of non-commutating observables, the interpretation of this statistical result for experiments;
Lecture on Jan 20
----------------
Revision of linear operators on Hilbert spaces, inner product identities, properties of eigenvalues and eigenvectors for Hermitian operators;
Preliminary glimpses of quantum parallelism: the computation of the (!0,f(0)>+ !1,f(1)>) state for a one input bit boolean function; the notion of a quantum circuit for computing a (classical boolean) function so that the superposition of states with the function's values on multiple input patterns is developed in the quantum state, using the Hadamard operation to begin with;
The quantum circuit with only one quantum (controlled-f) gate (realizable as a unitary operator U_f) for the parity problem for a one variable boolean function f:{0,1}--> {0,1}; the use of the Hadamard operations in this circuit and the measurement to get the predicate f(0)=f(1) (or f(0) not equal to f(1)).
--------------------------------
*******************************
READING and STUDY execise.
********************************
---------------------------------
Suppose you are given a classical (irreversible) boolean circuit for the function f. You can convert that into a reversible boolean circuit with extra bits in the output which we may call garbage bits. This circuit can be made with classical universal Fredkin gates (for instance); so, we may also use quantum Fredkin gates for this purpose. Show that the garbage bits can be "neutralized" reversibly because they were reversibly computed ! Show also that the f(x) computed for any quantum superposition component x can CNOT a 0 or a y, bitwise (qubitwise), giving y XOR f(x), thereby realizing the controlled-f superimposing functionality. This is how we get the U_f quantum circuit. See [N & C], section 3.2.5.
--------------------------------
Lectures on Jan 21
----------------
Further discussion on the Deustch problem (of exactly solving the parity problem for a single input bit boolean function); The use of the Hadamard operator on 1-, 2- and n-qubit states; the two qubit gate CNOT, the U_CN unitary 4 x 4 matrix; the Toffoli and Fredkin gate and their applications as a classical universal gates; the unitary 8x8 matrices for these gates; the reversibility of these operations;
Lecture on Jan 27
--------------------
The Deustch-Josza problem and its exact solution- demonstrating the use of the Hadamard operation before and after the U_f quantum circuit for deciding the promised character of f(x1,...,xn) as one of a constant and a balanced function;
Motivation for discussion on Bell's inequality and its development (classical) for the thought experiment, establishing an upper bound of 2 for the classical expectation E(QR)+E(QS)+E(RT)-E(QT);
Lectures on Jan 28
---------------------------
Establishing the violation of Bell's inequality in the quantum mechanical setting where Alice [Bob] uses observable A [B] as either X or Z [(-Z-X)/sqrt(2) or (Z-X)/sqrt(2)], calculating the expectations of the observable for tensor product A X B for the entangled singlet state, showing a value of 2*sqrt(2) for the sum of the expectations violating Bell's inequality.
The no-cloning theorem- the impossibility of copying an unknown quantum state exactly, discussions on two proofs from Gruska's text;
Lecture on Feb 3
---------------
Revision of the Duestch and Deustch-Jozsa algorithms; the Bernstein-Vazirani problem and its (exact) quantum solution showing computing time separation with respect to classical computation; introduction to Simon's problem;
Lectures on Feb 5
---------------
General version of Simon's problem (the hidden subgroup problem); quantum (but probabilistic) solution to the original problem of Simon; the quality of naive deterministic and randomized solutions; allusion to the expoential-polynomial separation between classical and quantum approaches via Yao's result.
Revision of simple unary and two-qubit gates and their unitary matrices.
Introduction to density matrices- ensemble of pure states, the effect of a unitary operator on the density matrix; the expectation of an observable M for a single pure quantum state as trace(MR) where R is the density matrix of the pure state;
--------------------------
Topics covered during Feb 9-13 (Invited lectures of Sudhir Kumar Singh)
---------------------------
The Bloch sphere interpretation of quantum states and consequent interpretations of transformations;
Teleportation of an unknown quantum state using (i) entanglement (Einstein-Rosen-Podolsky pairs or EPR pairs), (ii) local operations and (iii) classical communication;
Monday 09/02/2004
1. QUANTUM ENTANGLEMENT
i) As a consequence of quantum superposition in multi-particle scenario
ii) Definition and physical interpretation
iii) Bell States, Bell Basis and measurement in Bell Basis
2. UNDERSTANDING THE QUANTUM MEASUREMENT PROCESS
i) Quantum superposition to classical probability distribution
ii) Unitary equivalence of measurements in different ortho-normal bases
3. QUANTUM MECHANICAL MODEL OF COMPUTATION
A. i) Representation
ii) Operations on the information
iii) Extracting the result
B. Why normal operators?
4. ENTANGLEMENT ASSISTED COMMUNICATION
i) Super-dense coding
ii) Quantum Teleportation: Introduction (Details: Reading Exercise)
Wednesday 11/02/2004
1. QUANTUM MECHANICAL MODEL OF COMPUTATION: A DISCRETE MODEL
i) Ideas from the Hilbert Space of Linear Operators on a Hilbert Space
ii) Ideas from classical probabilistic model of computation (Also a thinking exercise)
2. ENTANGLEMENT ASSISTED COMMUNICATION
i) Quantum teleportation: two unitarily equivalent circuits (detail Calculations: Working Exercise)
ii) Lower bound on the classical communication complexity of teleportation
iii) Teleportation with GHZ (tripartite entangled) state (Working Exercise)
iv) Selective Teleportation (of two qubits) and its impossibility using a GHZ state (Research)
3. UNDERSTANDING THE QUANTUM MEASUREMENT PROCESS
i) An overview of Ghose-Samal idea of unitary interpretation of measurement (details: Reading Exercise)
4. MIXED STATES AND DENSITY OPERATOR FORMALISM
i) Pure states and mixed states
ii) Why mixed states? Physical interpretation and examples
iii) Ensemble, density matrices and its properties. Why density matrices?
iv) Reformulation of postulates of quantum mechanics through density operators
v) Ensemble realization of mixed states: Unitary freedom (also a reading Exercise)
Saturday 14/02/2004
1. MIXED STATES AND DENSITY OPERATOR FORMALISM
i) Set of density matrices is convex.
ii) Criterion for being pure or mixed state
iii) Bloch Sphere representation of one qubit density operators
iv) Partial trace and reduced density operators
v) Why partial trace?
vi) LU, LO, LOCC and reduced density operators
vii) Change of trace during a quantum operation
-----------------------------------------------------------------
TO BE COVERED
-----------------------------------------------------------------
2. MIXED STATE ENTANGLEMENT: INTRODUCTION AND MOTIVATION
3. ENTANGLEMENT ASSISTED COMMUNICATION
i) Entanglement swapping
ii) Quantum key distribution (Basic idea)
4. QUANTIFYING ENTANGLEMENT: Introductory View
i) Schmidt decomposition
ii) Purification
iii) Entanglement concentration and dilution iv) PPT condition for separability
---------------------------------------------------------------------
--------------------------------------
Assignment # 3
---------
(1) Show that the measurement in any orthonormal basis can be unitarily converted to the measurement in any other orthonormal basis. In particular draw the circuit to convert the Bell basis measurement into the computational basis measurement.
(2) Show that the eight possible GHZ states form an orthonormal basis for the state space of a 3-qubit system. How do we convert the measurement in this basis to that in the computational basis? How is it related to the circuit used to create the proposed GHZ state?
(3) How does the measurement statistics change when the individual qubits of a Bell state are measured in diagonal basis, rather than in computational basis? What happens in the case of the GHZ state?
(4) Show how superdense coding can be done using GHZ states. How much compression can therefore be achieved in this case?
(5) Analyze the two circuits for teleportation, showing how the teleportation of an unknown qubit is realized. Suppose the first party (the sender) does the measurement(s) but the second party (the receiver) is not aware of the results of the measurement. In what (mixed) state is the qubit of the second party? What about the state of the first party?
[Discussion: Work out complete details of the working of the two circuits (i) doing the Hadamard and computational basis measurements and (ii) doing a direct Bell basis measurement.]
(6) Generalize teleportation using GHZ states. Suppose the GHZ state is shared between three parties A, B and C, then show how A can teleport an unknown qubit to C. How many classical bits do you need to communicate?
[Discussion: Start with a qubit a|0>+b|1> in A to be teleported. Another qubit in A is in GHZ state with one qubit each of B and C. Teleport the first qubit in A to C in a manner similar to the standard teleportation circuit/technique as we do with EPR pairs. Observe that B needs to do something in this teleportation ! ]
(7) Is it possible to teleport one of the qubits of a Bell state?
(8) Show that a mixed state can also be teleported using the circuits in Question 5.
(9) Suppose we perform a measurement in Z basis on a qubit and forget the result. In what state is the qubit? What if the measurement was done in the X basis?
[Discussion: Do you get a mixed state?.]
(10) 1/2 {|0><0|+|0><1|+|1><0|+|1><1|} is the density matrix representation of a state represented in computational basis {|0>,|1>}. Find whether this is a mixed state. If so, in what basis is it pure? What about the density operator 1/2 {|0><0|+|1><1|} ?
[Discussion: Check using the density operator trace characterization of pure and mixed states.]
(11) Find the reduced density operator of the first qubit in the following states (a) the four Bell states (b) the GHZ state (c) in the state represented by the density matrix 1/2{|00><00|+ |11><11|} (d) in the maximal mixture of the four Bell states.
(12) Show that the reduced density operator does not change under local operations.
(13) Show that the set of Hermitian operators on a Hilbert space form a Hilbert space. What is the scalar field here? What happens in the case of unitary operators?
(14) Analyze the ensemble realization of two commuting density operators.
------------------------------------------
Lecture on Feb 16
---------------
Quantum circuits: study of unitary transformations and 2X2 matrices.
----------------------
----------------------
Assignment #4, CS60014, Submission date Feb 17
------------------
(1) Show that H=(X+Z)/sqrt(2) and S=T^2.
(2) Ex. 4.2, [N & C].
(3) Ex. 4.3, [N & C].
(4) Ex. 4.4, [N & C].
(5) Ex. 4.5, [N & C].
(6) Ex. 4.7 and 4.8, [N & C].
(7) Study exercise, Theorem 4.1 [N & C].
(8) Ex. 4.9, [N & C].
(9) Study exercise, Corollary 4.2 [N & C].
(10) Ex. 4.18 [N & C].
(11) Ex 4.20 [N & C].
You may find Sakurai's text useful.
--------------------------
-------------------------
Lectures on Feb 18
-----------------------
Tutorial on problems related to unitary transformations for one qubit and for controlled unitary transformations on the second qubit from the first qubit with respect to Assignment #4.
Discussions on problems related to Bell basis measurements, density operators and commutation with respect to Assignment #3.
=======================================================
Sample excercises Feb 21, 2004
==============================
(1) Show that the singlet state (|01>-|10>)/sqrt(2) has a density matrix representation r such that trace(r^2)=1.
(2) Show with an example that two distinct one-qubit states may have the same density matrix representation.
(3) Show that the unitary operator V=(1-i) (I+iX)/2 is such that V^2=X. Show that using only CNOT gates and V and V* (adjoint V) circuits, we may realize the quantum Toffoli gate.
(4) Given a GHZ state, show how an EPR pair can be constructed.
(5) Explain (with illustrated examples) the significance of Schimdt decomposition in the context of local measurements on two-qubit states.
=======================================================
=======================================================
Lecture on March 1.
------------------
Revision of spectral decompositions for Hermitian operators; measurements in Bell basis for teleportation, the density matrix and mixed state resulting due to measurements therein; representations of one-qubit unitary operators U for C-U circuits using only CNOT gates and one-qubit unitary operators.
==============================
Assignment #5, March 1. Submissions by March 10, 2004
==============================
(1) Show that any Hermitian operator can be represented as a diagonal mztrix in an orthogonal basis of its eigenvectors.
(2) Show c.S (where c is any unit vector in 3d and S is the vector (X,Y,Z) of the Pauli matrices) can be written as V(x.S)V+ where V is a unitary operator, V+ is its adjoint and x is (1,0,0).
(3) Using (2) show that any unitray operator U for one qubit can be written as WX(W+)VX(V+)E, where W and V are unitary operators on one qubit and E is for phase correction. Thereby argue that a C-U circuit is possible for any one-qubit unitary operator using two CNOT gates and several one-qubit unitary operators.
(4) Ex. 4.22 and 4.23 [N & C].
(5) Ex. 4.24 through 4.27 [N & C].
(6) Ex. 4.32 through 4.35 [N & C].
(7) Ex. 4.36 [N & C].
========================================
=======================================================
Lectures on March 3.
------------------
The rotation operators R_y and R_z and their use in realizing an arbitrary one-qubit controlled gate, using only one-qubit unitary operators and CNOT gates; the unitary operator (1/(sqrt(2))) (I+iX) and its relationship with R_x, R_y and R_z;
Quantum circuits for addition of two n-qubit numbers: the use of the CARRY and SUM circuits with reversed carry RCARRY;
Initial discussion on universality of two-qubit gates: breaking up one NXN unitary operator into a sequences of 2X2 unitary operators and then realizing each such operator using only CNOT and one-qubit unitary operators;
=======================================================
Lecture on March 8
------------------
Sketches of (i) realization of a general unitary matrix as the product of several two-level unitary matrices (O(N^2) such matrices for an N X N unitary matrix) (ii) realization of a two-level unitary matrix using only single-qubit unitary operators and CNOT gates.
-------------------------------------------
++++++++++++++++++++++++++++++++++
Reading exercises and homework
++++++++++++++++++++++++++++++++++
(1) Work out the details in the proof of universality of two-level unitary operators and their realization using CNOT gates.
(2) Work out the proofs of polar, spectral and Schmidt decompositions.
================================================
=======================================================
Lecture on March 9
------------------
The use of measurements in X and Y directions by agents sharing a GHZ (maximally entangled) state: (i) the study of correlations Charlie can salvage given the directions of measurements of Alice and Bob, (ii) a protocol where all three randomly choose X or Y directions to measure and finally Charlie (Bob) discard a set of measurements if no correlation can be salvaged in that measurement and (iii) rewriting the GHZ and other entangled states so that results or correlations in X and Y mesurements of Alice, Bob and Charlie may be deciphered.
=======================================================
Lectures on March 10
------------------
Suppose Bob grabs Charlie's qubit and does some mesurement with the hope that his eavesdropping (after Alice has made an X or Y measurement) will go undetected by Alice and Charlie- resulting in Charlie following a protocol to determine only correlations between measurements results of Alice and Bob (not the exact measurements though); whereas Bob also gets to know the measurement results of Alice and Charlie with some probability of eavesdropping success (not getting detected).
We compute the probability (1/4) that Bob actually gets detected of eavesdropping.
Converting a local GHZ state (between three local qubits) into an EPR pair (between two of the three qubits) using local quantum operations;
Converting a GHZ state with two qubits in location A and one qubit in location B into an EPR pair between A and B.
Converting a GHZ state state between three non-local sites in to an EPR pair between two of the three sites.
Converting two EPR pairs between two distinct pairs of three sites into one GHZ state between the three sites.
Using a GHZ state between three sites A, B and C to teleport an unknown quantum state from A to C. ============================================================
=======================================================
Lectures on March 15 and 16
------------------
The RSA scheme and its use of private key d derived from the public key c and two large primes p and q (using group G_{(p-1)(q-1)}) to decode the coded message a^c (mod pq) as a^{cd} (mod pq); the equality of the order of the message a and the coded message b; how to use the order of b to decode b into a using d' (by doing a^{cd'} (mod pq)), where d' is in G_r and r is the order of a (or b); restating such order finding as period finding for f(x)= b^x (mod N); how to find (classically) the period from many multiples of the period where multiples are such that f(x)=f(x+s) (recall Simon' problem !!!); how using a single U_f (controlled-f) and doing a measurement on the output register may not help so we do a QFT (Quantum Fourier Transform) and measurement on the input register to resolve the period r;
=======================================================
Lectures on March 17
------------------
Shor's period finding trace for n=15, a=7 where a^r=1 mod n; the analysis of the case when the period r divides m=2^l (l qubits input register); characterizing the case when the observed value p =d*m/r depending on whether gcd(d,r)=1, giving the period r; the general case where r may not divide m; the continued fractional approximations; analysis of the probability of getting observed p within a good approximation of multiples of m/r;
=======================================================
Lecture on March 22
------------------
How period estimation can help in factoring the product of two primes; the complete factoring algorithm; the use of three number theoretic facts (i) about factoring when a (a is mutually prime with pq) has an even order and a^(r/2)<>-1 mod (pq) [READING EXERCISE: Work out the conditions on a and the probabilities for the conditions that you get factors p or q of pq using r] (ii) about convergents of the continued fraction of known ratio p/m being very close to unknown ration d/r where gcd(d,r) being 1 gives period r [READING EXERCISE: Check the theory about continued fractions] (iii) the probability that a random d has this gcd property [Check the corresponding results]. These introduce respectively factors 1/2, 2/5 and 1/4*(log log pq) to a lower bound on the probability that the period is discovered by Shor's algorithm.
=======================================================
Lectures on March 23 and 24
------------------
Grover's search algorithm; the proof of quadratic speedup over classical search; the use of Grover's search to query on a non-key attribute, black box function f(x) and U_f realization;
============================================================
=======================================================
Sessions on March 29, 30 and 31
------------------
Problem solving sessions and revision-- entanglement, density matrices, mixed states.
Assignment 6, March 31, 2004 submission.
=============================================================
(i) Design quantum circuits for QFT.
(ii) Design quantum circuits for realizing Grover's search.
(iii) Analyse alternatives and costs of possible circuits in (i) and (ii).
=============================================================
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
=======================================================
Lecture on April 5
----------------------------------
The result on the partial trace of density operator T in Hilbert space Hn X Hm, wrt any observable An X Im (In X A) giving T1(T2) density operators in either subspace Hn (Hm) against observable A in Hn(Hm) by tracing out space Hm(Hn); the use of operators such as the outer product of |x_k> and |x_l> and the outer product of |x> with itself in (respectively) salvaging elements of T1 and in showing the uniqueness of T1.
=======================================================
Lectures on April 7
----------------------------------
Revision of the result on partial trace and its uniqueness, connections of this result with Schmidt decomposition;
The notion of compression possible on average in communicating n-bit strings from a {(1-p,0),(p,1)} binary alphabet probability distribution, the compression ratio of H(p)= -(1-p)log (1-p) - p log p;
Generalization to a probability distribution of alphabet X={(x,p(x)| x in X and Sigma p(x)=1}, where compression ratio possible is no more than H(X)= Sigma p(x) log (1/p(x));
The notion of H(X) generalized to joint probability distributions giving H(X,Y) and conditional probabilties giving H(X|Y) and H(Y|X); the relationships between these measures;
+++++++++++++++++++++++++++++++++++++++++++++++++++++
Remaining lectures in April 2004
------------------
The notion of relative Shannon entropy; the notion of mutual information H(X:Y) and its relationship with H(X), H(Y), H(X|Y), H(Y|X) and H(X,Y);
introduction to von Newmann entropy for a density matrix represented quantum mized state rho, S(rho); the notion of relative von Newmann entropy; properties of Shannon and von Newmann entropy;
+++++++++++++++++++++++++++
Could not discuss
----------------------
Proofs of BPP being a subset of BQP and BQP being a subset of P^{#P}.
Universal QTMs.
Elements of quantum cryptography.
=======================================================