Instructor: David A. Meyer
Room & time: AP&M 5402, MWF 9:00am-9:50am
Office hours: AP&M 7256, M 1:00pm-2:00pm, or by appointment
Quantum computing offers the promise of more effective solutions to certain problems than are known to be possible on classical computers. 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.
This course will introduce the basic ideas of quantum computing: query complexity, optimal measurements, Grover's algorithm, quantum random walks, entanglement, Bell's theorem, gate arrays, the quantum Fourier transform, computational complexity, Shor's algorithm, and hidden subgroup problems, as time permits.
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]. Other useful references include David Mermin's text, Quantum Computer Science [2] and the lecture notes of John Preskill [3] and Scott Aaronson [4]. There will be no exams, but students taking the course for a grade will be asked to present solutions to intermittently-assigned homework problems, or to summarize a relevant topic of their choice.
| 30 may-10 jun 11 |
University of Waterloo
Institute for Quantum Computing
Undergraduate School on Experimental Quantum Information Processing. Application deadline 21 feb 11. |
| 17-20 feb 11 |
Thirteenth Annual Southwest Quantum Information and Technology
Workshop in Boulder, CO. |
| 20 jan 11 |
SQuInT Workshop poster outlines at 2pm in AP&M 7218 Orest Bucicovschi on achievable concurrences; Tom Wong on nonlinear quantum search. |
| 19 jan 11 |
Paolo Zanardi
will talk at 4:00pm in Mayer Hall 4322 on "Telling quantum phases of matter apart: The fidelity approach": P. Zanardi and N. Paunković, "Ground state overlap and quantum phase transitions"; P. Zanardi, P. Giorda and M. Cozzini, "The differential information-geometry of quantum phase transitions"; L. C. Venuti and P. Zanardi, "Quantum critical scaling of the geometric tensors". |
| 18 jan 11 |
Michael Zwolak will talk at 11:00am in Mayer Hall 4322 on
"Redundant imprinting of information in non-ideal environments: Quantum Darwinism via a noisy channel": M. Zwolak, H. T. Quan and W. H. Zurek, "Quantum Darwinism in a hazy environment"; M. Zwolak, H. T. Quan and W. H. Zurek, "Redundant imprinting of information in nonideal environments: Objective reality via a noisy channel". |
| 14 jan 11 |
Sam Buss will talk at 3:00pm in AP&M 7421 on "Introduction to computational complexity": S. Arora and B. Barak, Computational Complexity: A Modern Approach. |
| 13 jan 11 |
Asif Shakeel will talk at 2:00pm in AP&M 7218 about a representation theoretic explanation of the phase-kickback trick: Shakeel, "An improved query for the hidden subgroup problem". |
| 6 jan 11 |
Daniel Minsky will talk at 2:00pm in AP&M 7218 about: Renner and Wolf, "Towards characterizing the non-locality of entangled quantum states"; Brassard, Broadbent and Tapp, "Quantum pseudo-telepathy". |
| 3 jan 11 |
course organization and overview mathematical formulation of quantum mechanics [5] |
| 5 jan 11 |
prehistory of quantum computing [6] show that NAND is universal for boolean functions find a universal set of reversible gates find a single reversible gate that is universal Deutsch's problem [7] |
| 7 jan 11 |
tensor product Deutsch's algorithm [7] improved version [8] |
| 10 jan 11 |
generalizations of Deutch's problem [7] Deutsch-Jozsa problem [9] Bernstein-Vazirani algorithm [10] |
| 12 jan 11 |
more than 2 dimensions the shift X the discrete Fourier transform F asymmetrical measurement of three coplanar vectors with mutual inner products of norm-squared 1/4 |
| 14 jan 11 |
summing two trits symmetrical measurement of three coplanar vectors with mutual inner products of norm-squared 1/4 the improved Deutsch algorithm as an interference experiment [8] |
| 17 jan 11 | no lecture: Martin Luther King, Jr. holiday |
| future |
interference POVMs and optimal measurements Grover's algorithm amplitude amplification quantum random walks quantum simulation entanglement Bell's theorem gate arrays computational complexity quantum Fourier transform Shor's algorithm hidden subgroup problems |
| [1] | M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge: Cambridge University Press 2000). |
| [2] | N. D. Mermin, Quantum Computer Science (Cambridge: Cambridge University Press 2007); draft chapters online. |
| [3] | J. Preskill, Physics/Computer Science 219 lecture notes (1997-2004). |
| [4] | S. Aaronson, PHYS771 Quantum Computing Since Democritus lecture notes (2006). |
| [5] | J. von Neumann, Mathematische Grundlagen der Quantenmechanik (Berlin: Springer-Verlag 1932); transl. by R. T. Beyer as Mathematical Foundations of Quantum Mechanics (Princeton: Princeton University Press 1955). |
| [6] | R. P. Feynman, "Simulating physics with computers", International Journal of Theoretical Physics 21 (1982) 467-488. |
| [7] | 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. |
| [8] | R. Cleve, A. Ekert, C. Macchiavello and M. Mosca, "Quantum algorithms revisited", Proceedings of the Royal Society of London A 454 (1998) 339-354. |
| [9] | D. Deutsch and R. Jozsa, "Rapid solution of problems by quantum computation", Proceedings of the Royal Society of London A 439 (1992) 553-558. |
| [10] | E. Bernstein and U. Vazirani, "Quantum complexity theory", STOC 93: Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing (New York: ACM 1993) 11-20. |
|
|
B. Dyne, "Recent developments bring quantum computers closer to implementation", World Socialist Web Site (8 January 2011). |
|
|
M. Finnegan, "Electronic field allows more precise control of qubits", TechEYE.net (4 January 2011). |