Math 410-01/510-01: Introduction to Quantum Computing, Fall 2012

[ Blackboard link | Course description | Homework List ]

Instructor: Chi-Kwong Li

Course description: An introduction of the mathematics background of quantum computing will be given based on
the first 12 chapters of the following required textbook.

M. Nakahara and T. Ohmi, Quantum computing: From Linear Algebra to Physical Realizations,
CRC Press, Taylor and Francis Group, New York, 2008.
http://www.amazon.com/Quantum-Computing-Algebra-Physical-Realizations/dp/0750309830

Additional references:

M. Hirvensalo, Quantum Computing, (2nd edition), Springer, New York, 2004.
G. Johnson, A Shortcut Through Time: The Path to the Quantum Computer, Alfred A. Knopf, New york, 2003.
P. Kaye, R. Laflamme and M. Mosca, An introduction to quantum computing, Oxford University Press, Oxford, 2007.
A. Yu Kitaev, A. H. Shen, and M. N. Vyalyi, Classical and Quantum Computation (Graduate Studies in Mathematics), AMS, Rhode Island, 2002.
D. McMahon, Quantum Computing Explained, Wiley and Sons, 2008, New York.
M.A. Nielsen and I.L. Chuang, Quantum computation and quantum information, Cambridge University Press, Cambridge, 2000.
A. O. Pittenger, An introduction to quantum computing algorithms, Birkhauser, Boston 1999.

The course may lead to undergraduate research opportunities in the summer sponsored by the NSF CSUMS grant at William and Mary:
http://web.wm.edu/mathematics/CSUMS.php?&=&svr=www

Homework will be assigned every lecture and due the following Thursday.
Homework sessions will be conducted on Wednesday.

Challenging problems will be assigned from time to time;
extra-credits will be given to successful (or partially successful) attempts.

Math 510-01 students are required to write term papers.

Assessment

            
     Quizzes (20 min. each) on Sept. 13, 27, Oct. 25, Nov. 8, 29.
    
     Exams:  Mid-term Oct. 11 1:20 hrs (9:30-11:00 a.m.)
             Final Dec. 17 3 hrs (9:00-noon)
    
     Grades (for homework, quizzes, exams, final grade, etc.):

     %: 0 - 60 - 65 - 70 - 75 - 80 - 83 - 87 - 90 - 93 - 100
          F     D   C-   C    C+   B-   B    B+   A-   A
     
     Assessment: Homework Quizzes Mid-term Final Term paper
    
     Math 410 20% 20% 25% 35%
     Math 510 20% 20% 20% 30% 10%
   
               (Extra credit problems may add another 5%)

Homework List:

Homework 1. Due: Sept. 6, 2:00 p.m.
Ex. 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7.
Homework 2. Due: Sept. 13, 2:00 p.m.
Ex. 1.9, 1.11 - 1.17, 1.21-1.22. Optional (extra credit): 1.19, 1.20.
Homework 3. Due: Sept. 20, 5:00 p.m.
Ex. 2.1 (1)-(4). (40 points.) [Do (5) for extra credit if you know that differential operator.]
Ex. 2.2 2.5, 2.6, (10 points each).
Additional problem. (10 points) Suppose {|e_1>, |e_2>, |e_3>} is the standard basis for C^3,
{|f_1>, |f_2>} is the standard bais for C^2. Find the Schmidt decomposition of |x> for
|x> = |e_1 f_1> + 2 |e_1 f_2> + 3 |e_2 f_1 > + 4 |e_2 f_2 > + i|e_3 f_1 >.
[cf. Example 2.3]
Homework 4. Due: Sept. 28, noon.
Ex. 2.7, 2.8, 2.9, 2.10; 3.1, 3.2, 3.3.
Homework 5. Due: Oct. 5, noon.
Ex. 3.4., 3.5, 3,6, 4.3 (2), 4.4-4.9.
Homework 6. Due: Oct.18, noon.
Ex. 4.10, 4.11, 4.13, 4.14 [Read the Gray code description in p. 85.] 4.16. 4.17.
Homework 7. Due: Oct. 29, noon.
Ex. 5.1 5.2.
Homework 8. Due. Nov. 5, noon.
Ex. 6.1 (Hint: [\tilde f(0), \dots, \tilde f(N-1)]^t = K [f(0), \dots, f(N-1)]^t where v^t is the transpose of v.)
Ex. 6.2
Ex. 6.3 (You may focus on n = 4, and p = 2, 4, 8.)
(You get etra credit if you give details for the general case with clear explanation, not just repeating the derviation at the end of the book.)
Ex. 6.4. (Hint: Note that U = U_1 ... U_k is symmetric, then U^t = U = U_k^t ... U_1^t.)
Make up projects for Exam 1. You may earn up to 20 points for your exam and quizzes by trying the following projects. They might also lead to funded research opportunities in the winter break, spring 2013, or summer 2013.
(a) (10 points) Write a computer program in (Matlab, Maple, C++, Java) so that for any 4-by-4 unitary U, the program wil return two level matrices described in Quiz 3 U_1, ...., U_6 so that U = U_1 ... U_6.
Xiaoyan will you on Nov. 8, a general scheme to decompose any d-by-d unitary into d(d-1)/2 two level P-unitary matrices. You will earn 10 more points if you can do the general progam.
(b) (10 points) Write a complete proof, typed in Tex, explaining why K = (w^{-ij})$ is unitary.
(c) (10 points or more) Suggest, design, new methods to
(c.i) decompose unitary gate into simple quantum gates such as I \otimes U for 2-by-2 U,
(c.ii) new Quantum Integral Transform to do the grouping and regrouping of register qubits more efficiently to carry out the quantum algorithms we have discussed, especially, the period finding algorithm.
(d) Write an essay explaining the work of the 2012 physics Nobel prize on quantum states.
Homework 9, Due. Nov. 13, noon.
Exercise 7.1 - 7.4.
Homework 10, Due. Nov. 20, noon.
Exercise 8.1-8.4.

Homework 11, Due Nov. 29, noon.
1) Suppose N = 21, determine the number of m in {1, ...., N-1} such that m^P = 1 (mod N) such that P is even and m^{P/2} + 1 is not a multiple of N.
2) Consider a 2-by-2 density matrix A, B = E_{11} in M_3, and U = (u_{ij}) is 6x6 unitary. Show that Tr_1(U(A\otimes B)U^*) = F_1AF_1* + F_2AF_2* such that
[F_1
F_2]
is formed by the first and fourth column of U, and F_1^*F_1 + F_2^* F_2 = I_2$.
Exercise 9.1.

Homework 12, Due. Dec. 5, noon.
Ex. 9.2, 10.1, 10.2, 10.3.