CS290A|PHYS250, UCSB, 2013-01/03: "Quantum Information & Quantum Computation" (Wim van Dam)

Announcements:

  • 2013-03-18: Contact WvD if you want to know how you scored on the 6 questions of the Take-home Exam
  • 2013-03-02: A third version of Instructions, advice, and suggested references for the Final Paper has been posted below; added are references for quantum finite automata and quantum Turing machines
  • 2013-03-01: An updated version of Instructions, advice, and suggested references for the Final Paper has been posted below; by request, several references to articles on quantum random walks have been added
  • 2013-03-01: An updated version of the Take-home exam has been posted with some minor corrections.
  • 2013-02-28: Instructions, advice, and suggested references for the Final Paper has been posted below
  • 2013-02-25: Slides with material of the past 7 weeks has been posted below
  • 2013-02-21: One day late, the take-home exam has been posted below; the due date has been moved to the weekend of March 2/3.
  • 2013-02-21: Reminder: On Thursday, February 21 there will be no class.
  • 2013-02-07: On Tuesday February 12, instead of a regular class, there will be a guest lecture by Daniel Sank on building quantum computers using superconductors
  • 2013-01-23: "Notes on Quantum Computation" (pdf, 11 pages, summarizing braket notation and basics of quantum circuit computation) has been posted below; these notes will be frequently updated as the course progresses
  • 2012-11-20: Welcome to the site of CS290A|PHYS250: Quantum Information & Quantum Computation (Wim van Dam, UCSB, Winter 2013)

Professor

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

Course description

  • Introduction to quantum computing with an emphasis on the computer science part of the field
    • Topics that will be covered are: 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.
  • What to expect?

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.
  • "Quantum mechanics is actually... unbelievably simple, once you take all the physics out"

Textbook

  • No textbook is required for this course.

Final Grade

  • 50% Examination + 50% Final Project

Formalities

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

Weekly Schedule

  • Tuesday, 15:00--16:50: class in Phelps 2510
  • Thursday, 10:00--12:00: WvD's office hours in HFH2151
  • Thursday, 15:00--16:50: class in Phelps 2510

Calendar

  • Week I [01-07/13]: formalities, introduction to theoretical computer science, quantum versus classical information
  • Week II [01-14/20]: amplitudes instead of probabilities, superposition principle, measurements, simple quantum gates, braket notation, unitarity; in-class experiments
  • Week III [01-21/27]: measurement bases, quantum money, BB84 quantum cryptography, density matrix notation for mixed quantum states
  • Week IV [01-28/02-03]: tensor products, quantum circuits, circuit complexity, reversible computing, DJ algorithm, BV algorithm; WvD's office hours this week will be 11:00--13:00
  • Week V [02-04/10]: partial measurements, Simon's algorithm, public key cryptography, factoring through period finding
  • Week VI [02-11/17]: Tuesday February 12 there will be a guest lecture by Daniel Sank on building quantum computers using superconductors
    • Thursday's topics: Shor's algorithm for period finding, Shor's factoring algorithm
  • Week VII [02-18/24]: Shor's algorithm for discrete logarithms, elliptic curve cryptography; no class or office hours on Thursday 02-21
  • On Monday February 25, 09:30--10:30, there will be a KITP lecture (Full Seminar Room) "Superposition, Entanglement, and Raising Schroedinger's Cat" by 2012 Nobel laureate David Wineland
  • Week VIII [02-25/03-03]: quantum information theory, estimating unknown quantum states, transmitting quantum information, EPR pairs, Bell basis, superdense coding, teleportation; GHZ state, hidden variable theories, Bell's inequality, quantum nonlocality, quantum communication complexity, superstrong nonlocality
  • Week IX [03-04/10]: Grover's search, lower bounds through the polynomial method, limitations of quantum computation; quantum error correcting codes,
  • Week X [03-11/15]: Details of the final paper; power and limitation of quantum computation; efficient quantum circuits; the state of the field anno 2013
  • Finals week [03-16/22]: paper due

Final Paper

The Final Paper should be about a topic in the theory of quantum information and computation. It is due on Friday, March 22.