C191 Quantum information

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)

Instructor

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

Teaching Assistant

Hanhan Li
Email: bomb@berkeley.edu
Office hours: Monday 11-12pm @ 397 Leconte

Announcements

Project presentations will take place during two of the following three slots: Wed 12/8 between 10 am and noon, Friday 12/10 between 10 am - noon, and Friday 12/10 3 pm - 5 pm. Please email Prof. Vazirani with your slot preferences. Please include all the slots in order of preference that you would be willing to speak in.
11/20/10 Broad suggestions for term projects have been listed below. Please form groups of 2-3 if you haven't already, and formulate a topic for your project.
11/14/10 Midterm 2 will be in 306 Soda from 3:30 - 5:00 on 11/16.
It will focus mainly on material covered since the 1st midterm, especially:
Hadamard transform and quantum fourier transform.
Phase I of Simon's algorithm = Hadamard + U_f + measurement.
Period finding in quantum factoring algorithm.
Grover's algorithm.

Spin as a qubit
Bloch sphere representation of qubits (pure states and mixed states).
Pauli matrices
Exponentiating Pauli matrices for single qubit evolution
Density matrix representation in terms of Pauli matrices
Advantages and disadvantages of liquid-state NMR and solid state implementations of QC

You should focus more on general ideas, don't stress too much about doing computations. For instance, you should know what is meant by decoherence, but you won't be expected to take partial traces.
11/14/10 Review session for mid-term 2 will be held in 310 Soda at 5-6pm on Monday, Nov. 15th.
11/05/10 Update to homework 8 has been posted.
11/02/10 Homework 8 has been posted.
10/31/10 Notes on Spin Resonance posted.
10/26/10 Homework 7 has been posted as well as the notes for today's lecture on quantum spin.
10/15/10 The last question on Homework 5 has been simplified so it involves the Hadamard transform rather than the quantum fourier transform.
10/9/10 Homework 5 is due on 10/18.
10/4/10 Review session will be held on Tuesday Oct 5, 8-9pm in 60 Evans.
10/3/10 On homework 4 question 2, your answer should be a matrix. On question 3, you may assume the numbers j and k are specified as binary strings.
10/1/10 The midterm will be in 155 Donner.
9/26/10 As discussed in class on Thursday, the first midterm will be in class on Thursday, Oct 7.
9/20/10 We have a new classroom! Starting Tuesday 9/21 lecture will be in 320 Soda Hall.
9/17/10 A preliminary version of homework 3 has been posted for those who wish to get started working on it this weekend. It is due on 9/27. I will add a question or two to the homework before Monday.
9/9/10 Homework 2 has been modified to delete two questions that were based on material not yet covered in lecture, and add a new question in their place.
08/29/10 Currently only a couple of wait-listed students will be allowed to sign up for the course (we are working on changing that situation). In the meantime, if you wish to be considered, please send Prof. Vazirani an email stating your name, major, year, your level of preparation for the course (relevant coursework and grades), and your reasons for taking the course.
08/31/10 Homework 1 has been posted. It is due at the beginning of class on Tuesday 9/7, because Monday is a holiday.

Mid-term

Problems and solutions [pdf]
Grade distribution [pdf]

Problems [pdf]
Solutions [pdf]
Grade distribution for regular problems (out of 60)[pdf]

Homework

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

Homework 1 [pdf] due Tuesday 9/7. solution [pdf]

Homework 2 [pdf] due Monday 9/13. solution [pdf]

Homework 3 [pdf] due Monday 9/27. solution [pdf]

Homework 4 [pdf] due Monday 10/4. solution [pdf]

Homework 5 [pdf] due Monday 10/18. solution [pdf]

Homework 6 [pdf] due Monday 10/25. solution [pdf]

Homework 7 [pdf] due Monday 11/1. solution [pdf]

Homework 8 [pdf] due Monday 11/8. solution [pdf]

Lecture notes

		Topic	Notes
1	8/28	Chapters 1 and 2: "Qubits and Quantum Measurement" and "Entanglement".	[pdf]
2	9/14	Chapters 3 and 4: Observables" and "Continuous Quantum States".	[pdf]
3	9/21	Notes on "Mixtures and Density Matrices"	[pdf]
4	9/21	Slides on Quantum Cryptography.	[pdf]
5	9/28	Notes on "Tensor Products"	[pdf]
6	10/10	Notes on "Reversible Computation"	[pdf]
7	10/10	Notes on "Quantum Algorithms"	[pdf]
7	10/10	Notes on "Simon's Algorithm"	[pdf]
8	10/15	Notes on "Quantum Fourier Transform & Factoring"	[pdf]
8	10/15	Notes on "Quantum Search and Quantum Zeno Effect"	[pdf]
8	10/15	Notes on "Spin and the Bloch Sphere - I"	[pdf]
8	10/15	Notes on "Spin Resonance"	[pdf]
9	11/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.
http://arxiv.org/abs/quant-ph/0001106

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.
http://arxiv.org/abs/quant-ph/0002077

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,
http://arxiv.org/abs/quant-ph/0305025

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:
http://arxiv.org/abs/quant-ph/0603163

6. Algorithmic cooling and quantum architectures
(see quant-ph/9804060 and http://www.cs.berkeley.edu/~kubitron/papers/ "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:
http://arxiv.org/abs/0811.3171

Useful Links:

Los Alamos archive of papers and preprints on Quantum Mechanics and Quantum Computation: link
John Preskill's Quantum Computation course at Caltech: link
Umesh Vazirani's Quantum Computation course at UC Berkeley: link
Daniel Lidar's page of teaching links for Quantum Mechanics and Quantum Computation: link