CS294-2

Quantum Computation

Fall 2004


Instructor Umesh Vazirani
Office: 671 Soda, 642-0572
Lectures: TuTh 10:30-12 (405 Soda)
Office Hours: M 1-2 (671 Soda)

Quantum computation is an exciting area that at the intersection of computer science, mathematics and physics. It touches on fundamental questions in computer science as well as quantum physics. This course will provide a comprehensive introduction to this area including:

1. An introduction to quantum physics from a quantum information viewpoint.

2. Quantum algorithms for factoring, discrete log and search.

3. Limits on the power of quantum computers.

3. Quantum error-correcting codes and fault-tolerant quantum computation.

4. Quantum information and cryptography.

5. Survey of proposals for implementation of quantum computers.

Prior coursework in quantum mechanics is not essential. This interdisciplinary subject draws on techniques from theoretical computer science, mathematics, and quantum physics. Students with a strong background in any one of these areas are welcome to attend.


Announcements

A list of papers for projects is now available at project-list

There will be no lecture on Tuesday 9/21 and Thursday 9/23. Please use the opportunity to digest the concepts already introduced and to work on the new assignment. I will announce makeup lectures later in the semester.


Homework

  • Homework 1 [ps pdf] due Tuesday 9/14.
  • Homework 2 [ps pdf] due Tuesday 9/28.
  • Homework 3 [ps pdf] due Tuesday 10/26.

    Lecture notes



    Topic Notes (modified)
    1 8/31 Intro, Qubits, Measurements, Bell Inequalities. [pdf,ps] (9/5)
    2 9/2 Two qubit states, Unitary Evolution, Quantum gates, Superdense coding [ps] (9/13)
    3 9/7 Hilbert Spaces, Tensor Products, No Cloning Theorem, Teleportation (preliminary version) [ps] (9/8)
    4 9/9 Universal Gate Sets, Solovay-Kitaev theorem, BQP, Reversible Computation. [pdf,ps] (9/20)
    5 9/14 Reversible computation, BPP in BQP, accuracy. [pdf,ps] (10/5)
    6 9/16 BQP in PSPACE, #P, Deutsch-Jozsa, Bernstein-Vazirani. [scan1, [scan2, scan3, [scan4] (9/24)
    7 9/28 Simon's Algorithm [pdf,ps] (10/2)
    8 9/30 Quantum Fourier Transform [pdf,ps] (10/15)
    9 10/5 Shor's Factoring Algorithm [pdf,ps] (10/15)
    10 10/7 NP-complete problems - quantum lower bounds + Grover's algorithm. [pdf,ps] (10/7)
    11 10/12 Grover contd. + Quantum zeno effect + Vaidman Bomb. [pdf,ps] (10/15)
    12 10/14 Hidden Subgroup Problem + discrete log. [pdf,ps] (10/17)
    13&14 10/19 and 10/21 Quantum Walks, Hitting Time, Element Distinctness [pdf,ps] (10/30)
    15 10/26 Hamiltonians, Schrodinger's Equation, Uncertainty Relations. [pdf,ps] (11/7)
    16 10/28 Dirac Equation, Entropic Uncertainty Relation. [pdf,ps] (11/12)

    17-19 11/2, 11/4, 11/9 Quantum simulation, Quantum NP. [pdf,ps] (11/15)

    20
    11/16 Density Matrices, trace norm, von Neumann entropy.  [pdf,ps] (11/20)


    21
    11/18 and 11/23 Quantum Error-correcting codes.   [pdf,ps] (11/20)



    Useful Links:



    Recommended reading


    On quantum computation

    Mathematical background

    On quantum mechanics in general