Chem/CS/Phys191: Qubits, Quantum Mechanics and Computers

Lecture Tue & Thu 3:30 - 5:00pm (320 Soda Hall)
Section 101 W 2-3pm (6 Evans)
Section 102 M 3-4pm (87 Evans)


Prof. Umesh Vazirani
Office hours: Monday 1-2 in 671 Soda

Teaching Assistant

Hanhan Li
Office hours: Monday 11-12pm @ 397 Leconte




Homework is due Monday at 5 pm in the drop box labeled cs191, in 283 Soda Hall.

Lecture notes

Topic Notes
18/28 Chapters 1 and 2: "Qubits and Quantum Measurement" and "Entanglement". [pdf]
29/14 Chapters 3 and 4: Observables" and "Continuous Quantum States". [pdf]
39/21 Notes on "Mixtures and Density Matrices" [pdf]
49/21 Slides on Quantum Cryptography. [pdf]
59/28 Notes on "Tensor Products" [pdf]
610/10 Notes on "Reversible Computation" [pdf]
710/10 Notes on "Quantum Algorithms" [pdf]
710/10 Notes on "Simon's Algorithm" [pdf]
810/15 Notes on "Quantum Fourier Transform & Factoring" [pdf]
810/15 Notes on "Quantum Search and Quantum Zeno Effect" [pdf]
810/15 Notes on "Spin and the Bloch Sphere - I" [pdf]
810/15 Notes on "Spin Resonance" [pdf]
911/22 Notes on "Quantum Error Correction" [pdf]

Project List and Guidelines

The project is worth 30% of the grade. You should work in teams of 2-3. We encourage cross-disciplinary teams, since ideally a project should address both CS and Physics aspects of the question being studied. At the end of the semester each team will submit a short project report (ideally 2-3 pages), as well as give a 15-20 minute oral presentation.

Here are a few suggestions of broad topics for projects. We will add to this list, and you should feel free to suggest any topic that you are interested in. When you are ready, please email me (vazirani@cs) the composition of your team, the topic, and a brief description.

quant-ph refers to the Los Alamos archives: link

1. Adiabatic Quantum Computation (AQC)
AQC, though formally equivalent to circuit model QC, is quite different in its formulation. What are the advantages, and disadvantages of AQC compared to the circuit model? What are some promissing physical systems in which to implement AQC? The original paper by Farhi, Goldstone, Gutmann and Sipser provides a good starting point, and a web search will reveal a lot of follow up work.

2. Physical Implementations of QC
In class we discussed a number of physical implementations. What are the advantages of each? What are the dominant decoherence processes? Pick one and do a detailed analysis - or maybe do a general survey. You can start with David DiVincenzo's famous paper and references therein.

3. Decoherence Mitigation
There are many ways to protect a quantum computer from decoherence: dynamical decoupling, decoherence free subspaces, quantum feedback control, quantum Zeno effect, and quantum error correction. Talk about one in detail or do an overview. You can start by looking at the first couple of chapters of Dave Bacon's thesis,

4. Interpretations of quantum mechanics and the measurement problem
A good starting point is the following paper:
M. Genovese. Interpretations of quantum mechanics and the measurement problem. Adv. Sci. Lett. 3, 249 - 258 (2010).

5. Simulating quantum systems
One of the lessons of quantum computation is that quantum systems are exponentially powerful, so classical computers cannot efficiently simulate general quantum systems. Nevertheless, there are beautiful results showing how to simulate certain "natural" quantum systems efficiently on a classical computer. Here is a survey paper that provides a good starting point:

6. Algorithmic cooling and quantum architectures
(see quant-ph/9804060 and "Building quantum wires: the long and short of it")

7. Quantum algorithm for solving linear equations
Kitaev's phase estimation algorithm is a beautiful building block in quantum algorithms. A recent paper uses it to speed up solutions of systems of linear equations:

Useful Links:

Recommended reading

For all topics, the first recommended reading is the lecture notes. For a second point of view, or if the notes are confusing, try the other sources listed below.

On quantum computation

Mathematical background

On quantum mechanics in general