Instructor: David A. Meyer
Room & time: AP&M 5402, MW 9:30am-10:50am
Office hours: AP&M 7256, M 11:00am-12:00nn, Tu 12:00nn-1:00pm, or by appointment
The most famous quantum algorithm is Shor's quadratic time algorithm for factoring. This single result is primarily responsible for the immense investment of resources into building a quantum computer over the last decade.
But Shor's algorithm is only one of a family of quantum algorithms based on fast transforms (e.g., the Fourier transform). After introducing the basic ideas of quantum computing, we will study this family, as well as another which is represented by Grover's quantum search algorithm. If time permits, we will also discuss algorithms for simulation of quantum systems, topological quantum computation, or adiabatic quantum computation.
Some background in group theory, probability, quantum mechanics, cryptography, algorithms, or computational complexity will be useful, but is not required. Although there is no text for this course, Quantum Computation and Quantum Information by Michael Nielsen and Ike Chuang provides an excellent reference for the whole subject [1]. There will be no exams, but registered students will be asked to present solutions to intermittently-assigned homework problems, or to summarize a relevant topic of their choice.
| 26 feb-2 mar 07 | Institute for Pure and Applied Mathematics Short Program on Topological Quantum Computing at UCLA. |
| 16-18 feb 07 |
Ninth Annual Southwest Quantum Information and Technology
Meeting at CalTech. Registration deadlines 10-20 jan 07. |
| 13, 15 feb 07 |
D-Wave to unveil 16 qubit superconducting quantum computer at the Computer History Museum in Mountain View, CA and at Science World at the TELUS World of Science in Vancouver, BC. |
|
8 feb 07 David Meyer |
"Quantum correlated equilibria in games" AP&M 7218, 2:00pm |
|
25 jan 07 Gurudev Dutt |
"Quantum bits and quantum registers with electron and nuclear spins in diamond" NSB 3211, 12:00nn |
|
17 jan 07 Andrew Childs |
"Algorithms for quantum computers: quantum walk and quantum state estimation" Mayer Hall 4322, 4:00pm |
|
12 jan 07 Yi-Kai Liu |
"N-representability and QMA-completeness"
[quant-ph/0604166] EBU3B 4217, 2:00pm |
| 8 jan 07 |
overview of quantum computing [1, chap. 1] course organization |
| 10 jan 07 | Deutsch's algorithm [2,3] |
| 15 jan 07 | no lecture: Martin Luther King, Jr. holiday |
| 17 jan 07 | interference [3,4] |
| 22 jan 07 |
more on interference Deutsch-Jozsa algorithm [3,5] |
| 24 jan 07 |
Bernstein-Vazirani algorithm [6] Hamming distance oracles [7] |
| future |
(quantum error correcting codes) Simon's algorithm computational complexity quantum Fourier transform Shor's algorithm (other applications of the QFT) hidden subgroup problems (quantum learning algorithms) Grover's algorithm amplitude amplification (quantum random walks) (quantum simulation) (adiabatic quantum computation) (topological quantum computation) |
| [1] | M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge: Cambridge University Press 2000) [website]. |
| [2] | D. Deutsch, "Quantum theory, the Church-Turing principle and the universal quantum computer", Proceedings of the Royal Society of London A 400 (1985) 97-117. |
| [3] | R. Cleve, A. Ekert, C. Macchiavello and M. Mosca, "Quantum algorithms revisited", Proceedings of the Royal Society of London A 454 (1998) 339-354. |
| [4] | R. P. Feynman, R. B. Leighton and M. Sands, Quantum Mechanics, The Feynman Lectures on Physics, Vol. 3 (Reading, MA: Addison-Wesley 1965). |
| [5] | D. Deutsch and R. Jozsa, "Rapid solution of problems by quantum computation", Proceedings of the Royal Society of London A 439 (1992) 553-558. |
| [6] |
E. Bernstein and
U. Vazirani,
"Quantum complexity theory",
in Proceedings of the 25th ACM Symposium on Theory of Computing,
San Diego, CA, 16-18 May 1993 (New York: ACM 1993) 11-20; E. Bernstein and U. Vazirani, "Quantum complexity theory", SIAM Journal of Computing 26 (1997) 1411-1473. |
| [7] | M. Hunziker and D. A. Meyer, "Quantum algorithms for highly structured search problems", Quantum Information Processing 1 (2002) 145-154. |
|
|
M. Marquit, "Can neutrons be used in quantum computers?", PhysOrg.com (december 2006). |
|
|
A. Gefter, "At play in the multiverse", New Scientist (9 december 2006) 50-51. |