CS290A, UCSB, 2009-04/06

created by Wim van Dam on February 12 2009

Announcements:

  • [June 10] Some excellent final papers from two years ago have been posted below to give you an indication of what you should be aiming for.
  • [June 10] WvD will have office hours on Wednesday, June 10 between 3 and 5 pm.
  • [June 3] Information regarding the final paper has been posted below.
  • [May 19] You can also email the test to vandam@cs.____.___ if you have it in digital format.
  • [May 19] You can hand in your answers to the take-home test in my mailbox, which is in the copy room at the 2nd floor of Harold Frank Hall.
  • [May 19] Some additional clarification about Question 3a: The f-box acts on a 2n dimensional space: (n dimensions for the j register) x (2 dimensions for the output qubit), while the target summary state is composed of n qubits that live in a 2^n dimensional state space. Question 3a asks you to sketch how can create the summary state using the f-box only once. You do not have to give a whole circuit, just an informal description what that circuit should be doing. Do not try to overanalyze this question, it is a pretty simple one. It is Questions 3b and 3c that you should require more thought.
  • [May 18] A second version of the test has been posted, which should clarify Question 3a.
  • [May 13] Two comments regarding the take home-test.
      • You are allowed to use your textbook, notes, or other sources of information. Discussing the questions with others is not allowed.
      • In question 3: "... how many classical f queries...", you should consider probabilistic algorithms.
  • [May 12] The Take-home test is posted below and is due Tuesday, May 19 at 5 pm.
  • [May 10] WvD is away this week and hence there will be no class or office hours on Monday May 11 and Wednesday May 13. The take-home exercises will be posted here some time on Monday.
  • [May 4] Change of plans: there will be no extra class on Tuesday May 5.
  • [April 29] Some notes on the mathematics of quantum computation and some exercises have been posted below.
  • [April 8] Slides of the material of the first six weeks has been posted below. This is only version 1, and I plan on improving and updating them regularly so please don't waste paper by printing them out.
  • [April 1] Introductory slides have been posted below.
  • [February 12, 2009] Welcome to the CS290A site of Winter 2008, a graduate course on the theory of quantum information and quantum computation.

Slides, Notes, Exercises:

  • Formalities and Introduction to the course
  • Material of Weeks 1 through 6 (v1)
  • Notes on Mathematics of Quantum Computation I
  • Test Exercises I
  • Take-Home Test I CS290 (v2) (due Tuesday May 19, 5 pm)

The Final Paper:

  • The paper is due at the end of Finals Week, Friday June 12.
  • Please submit electronically by emailing it to vandam@cs.____.___
  • The length of the paper is not very important, although shorter is always better. Around 6 pages should be enough.
  • The paper should show that you are capable of understanding the scientific literature that deals with the theory of quantum information and computation. Specifically I am looking for the following components (if approriate):
      • A comparison between the classical probabilistic setting and the quantum one.
      • A detailed calculation (in an example say) showing your mastery of the bra-ket notation and the linear algebra that comes with it.
      • Some bound that limits the power of quantum computation.
      • Appropriate use of the big-O notation.
      • Being able to resist the temptation to write mostly about material that you already knew before the course (i.e. standard physics or computer science).
  • More advice on writing academic papers can be found here.
  • Here are some excellent final papers from the 2007 course.
    • "Review: Measurement-Based Quantum Computation"
    • "Implementations using optical lattices"
    • "Quantum Algorithms in Algebraic Number Theory"

Schedule:

Week I [March 30 - April 5]: "Preliminaries"

  • Topics: quantum mechanical state vectors, normalization, interference; computational complexity theory, big O notation

Week II [April 6-12]: "Quantum Information"

  • Topics: probabilistic computation, stochastic processes; quantum bits, quantum measurements; unitary transformations

Week III [April 13-19]: "Quantum Circuits and Tricks I"

  • Topics: reversible computation, circuit complexity, classical universality of CCNOT gate, braket notation; elementary quantum gates, {H,I,X,Y,Z}, quantum money, quantum cryptography a la BB84

Week IV [April 20-26] "Quantum Circuits and Tricks II"

  • Topics: tensor product construction, partial measurements, entanglement, Bell pairs, superdense coding, teleportation

Week V [April 27 - May 3]: "Quantum Algorithms"

  • Topics: Deutsch's original quantum algorithm, phase-kickback trick, Deutsch-Jozsa algorith, Bernstein-Vazirani algorithm, Simon's algorithm, Hidden Subgroup Problem, Fourier transform

Week VI [May 4-10]: "More Quantum Algorithms"

  • Extra classes before take-home exam
  • Topics:

Week VII [May 11-17]

  • WvD away
  • Take-home exam

Week VIII [May 18-24]

Week IX [May 25-31]

Week X [June 1-7] Finals week [June 8-14]

  • Project due.

Professor:

  • Wim van Dam
    • vandam@cs.____.___
    • Harold Frank Hall, Room 2151

Description:

  • Introduction to quantum computing with an emphasis on the computer science part of the field.
    • Topics that will be covered: elementary quantum mechanics, quantum information, quantum gates and circuits, quantum circuit complexity, teleportation, quantum cryptography, Shor's quantum algorithm for factoring integers and discrete logarithms, Grover's quantum searching algorithm, lower bounds in quantum computation, quantum error correction and fault tolerant quantum computation.

Prerequisites:

  • I will not assume that you know much about quantum mechanics or theoretical computer science, but I do assume that you want to learn about both fields. You should be mathematically literate as we are going to do a lot of linear algebra over the complex numbers.

Textbook:

  • An Introduction to Quantum Computation, Phillip Kaye, Raymond Laflamme and Michele Mosca, Oxford University Press, 2008.
    • Before buying this book, you might want to print out its first chapter, which is available for free.

Final Grade:

  • 50% Examination + 50% Final Project

Formalities:

  • ID: CMPSC 290A - Special Topics: Foundations
  • translation: a special topics graduate course in Computer Science that is open to anyone that is interested and prepared enough
  • units: 4

Weekly Schedule:

  • Monday, 1-3 pm: Class in Phelps 1401
  • Wednesday, 1-3 pm: Class in Phelps 1401
  • Wednesday, 3-5 pm: Office hours in Harold Frank Hall 2151

Contacting/Questions:

  • Any time, any where, I will be happy to talk about quantum computation and things related. For the more boring topics, please use my office hours or email me for an appointment.