Latest News:
- [May 31] Two final papers from a few years ago have been posted as an example how a good one looks like.
- [May 31] The answers to the take home exam have been posted below; WvD has also emailed the individual suggestions for the topics of your final paper
- [May 23] In class, on May 24, WvD will discuss the take-home exam; also WvD will have extra office hours that day, between 10:30 and noon.
- [May 19] LaTeX file of take-home test has been posted
- [May 18] The take-home test has been posted. It is due Thursday May 26, at 3 pm.
- [April 20] Slides on "Pre-Shor Quantum Algorithms" have been posted.
- [April 20] Slides on "Transforming information" and "Quantum Circuits" have been posted.
- [April 19] A skeleton LaTeX file and some mathematical notes on quantum computing have been posted below.
- [April 5] Slides "Intro to CS290", "Theoretical Computer Science" and "Quantum Information" have been uploaded (see attachments at the bottom of this page).
Professor
- Wim van Dam
- vandam@cs.____.___
- Harold Frank Hall 2151
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?
- Have a look at the CS290A site of Spring 2009.
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
- 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 who is interested and prepared enough
- units: 4
Weekly Schedule
- Tuesday, 3:00 - 4:50 pm, Phelps 1401: lecture
- Thursday, 11:00 am - noon, 1:00 - 2:00 pm: office hours WvD
- Thursday, 3:00 - 4:50 pm, Phelps 1401: lecture
Schedule for the Quarter
- Week I: formalities, introduction to theoretical computer science, quantum versus classical information
- Week II: amplitudes instead of probabilities, superposition principle, measurements, simple quantum gates, reversible computing
- Week III: measurement bases, circuit complexity, quantum money, BB84 quantum cryptography
- Week IV: tensor products, quantum circuits, DJ algorithm, BV algorithm
- Week V: partial measurements, Simon's algorithm, public key cryptography, factoring through period finding
- Week VI: Shor's algorithm for period finding, Shor's algorithm for discrete logarithms, elliptic curve cryptography
- Week VII: EPR pairs, Bell basis, superdense coding, teleportation, GHZ state
- Week VIII: hidden variable theories, Bell's inequality, quantum nonlocality, quantum communication complexity, superstrong nonlocality; classical and quantum error correcting codes
- Wednesday May 18: announcement take-home exam
- Week IX: Q&A about the take home exam, Grover's search, lower bounds through the polynomial method
- Thursday May 26, 3 pm: take-home exam due
- Week X: Details of the final paper; power and limitation of quantum computation; efficient quantum circuits; possible experimental implementations of quantum computers; the state of the field anno 2011
- Finals week: paper due (23:59, Friday, June 10, 2011)
Final Paper
The Final Paper should be about a topic in the theory of quantum information and computation. It is due at the end of the quarter (exact date tba).
Requirements: The paper should be typeset in LaTeX and should be at most 5 pages (excluding references and appendix). Large images can be put separately after these 5 pages as well. The font should be a standard one like Computer Modern or Times; the font size should be at least 11pts. The paper should be letter-sized with margins of at least 1 inch. When running out of space, choose depth over width in your paper. Here is a skeleton file for the final paper: skeleton LaTeX file for final paper.
See here for some advice on writing academic papers and here for information about LaTeX.
Here are two good examples of final papers from previous years: one on quantum algorithms for problems in number theory and another one on measurement based quantum computing.