Instructor: David A. Meyer
Room & time: AP&M 6438, MWF 1:25-2:15 (note new place and time)
Office hours: AP&M 7256, T 1-3, F 3:15-4:15, or by appointment
Currently the most important applications of quantum information processing are to information security: Quantum key distribution has been demonstrated experimentally, and the security of cryptosystems based on the hardness of finding discrete logarithms or factoring is compromised, theoretically, by Shor's quantum algorithms.
In this seminar we will use these applications to motivate an introduction to quantum computing. In the Winter quarter, basic concepts in quantum mechanics (superposition, measurement, entanglement, ...) were introduced as we studied quantum protocols for the cryptographic task of random key distribution. This or some previous background in quantum mechanics will be necessary for the topics to be covered in the Spring quarter, but the details of quantum key distribution will not be. In the Spring quarter we will introduce relevant parts of computational complexity theory in order to study specific quantum algorithms and appreciate their advantages over classical algorithms for the same problems. Additional related topics will be determined by the students' interests and background, and may include quantum versions of game theory, secret sharing, other crptographic primitives, communication complexity, ... .
Some background in cryptography, complexity, coding, or game theory will be useful, but is not required. Although there is no text for this course, [1] provides an excellent reference for the whole subject and should be on reserve at the library. There will be no assignments or tests, but registered students will be asked to give a presentation on a relevant topic of their choice.
|
|
D. S. Burgess, "Quantum dots offer single photons", Photonics Technology News (April 2002). |
|
|
The Swedish Research Council, "Quantum information now readable", alphagalileo (8 April 2002). |
|
|
P. Ball, "Physicists play by quantum rules", Nature Science Update (3 April 2002). |
|
|
J. Jones, "Quantum computers get real", Physics World (April 2002). |
|
|
R. C. Johnson, "Researchers demo secure storage of quantum data", EE Times (2 April 2002). |
|
|
M. Anderson, "Quantum cloning nears perfection limit", New Scientist (29 March 2002). |
| 1 apr 02 |
quantum algorithm for XOR of function values |
| 3 apr 02 |
Deutsch-Jozsa [2] algorithm quantum algorithms as games Grover [3] algorithm |
| 5 apr 02 | no lecture (IU colloquium) |
| 8 apr 02 | student presentation: Aaron Straus on surface quantum codes [4] |
| 10 apr 02 | student presentation: John-Paul Fryckman on computational complexity theory [5] |
| 12 apr 02 |
Bernstein-Vazirani algorithm [6] Hamming distance algorithm[7] |
| 15 apr 02 |
Simon's algorithm [9] |
| 17 apr 02 |
Simon and Bernstein-Vazirani algorithms detect periodicity oracles as input bit strings [10] |
| 22 apr 02 |
Grover algorithm applied to case of multiple solutions [11] minimizing expected number of queries in Grover search [12] Grover algorithm is optimal [13,11,12] |
| 24 apr 02 |
determining Boolean functions of input bit strings [10] |
| 26 apr 02 | student presentation: Ben Baumer on the discrete, fast, and quantum Fourier transforms |
| 29 apr 02 | student presentation: Graham Hazel on anyonic quantum computing [15] |
| 1 may 02 |
|
| 3 may 02 | student presentation: Ben Bachelor on quantum finite state automata and quantum pushdown automata [17,18] |
| 6 may 02 | no lecture (Tufts colloquium) |
| 8 may 02 | no lecture (QCPM Workshop) |
| 10 may 02 | (special time 1-2 pm): Dan Curtis advancement talk |
| 13 may 02 |
the phase estimation problem [19] |
| 15 may 02 | student presentation: Sean Raleigh on quantum teleportation [21] and superdense coding [22] |
| 17 may 02 |
the order-finding problem [23] |
| [1] | M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge: Cambridge University Press 2000) [website]. |
| [2] | D. Deutsch and R. Jozsa, "Rapid solution of problems by quantum computation", Proceedings of the Royal Society of London A 439 (1992) 553-558. |
| [3] |
L. K. Grover,
"A fast quantum mechanical algorithm for database search",
quant-ph/9605043,
in Proceedings of 28th Annual ACM Symposium on Theory of Computing (STOC)
(New York: ACM 1996) 212-219; L. K. Grover, "Quantum mechanics helps in searching for a needle in a haystack", quant-ph/9706033, Physical Review Letters 79 (1997) 325-328; R. Jozsa, "Searching in Grover's algorithm", quant-ph/9901021. |
| [4] |
A. Yu. Kitaev,
"Fault-tolerant quantum computation by anyons",
quant-ph/9707021; M. H. Freedman and D. A. Meyer, "Projective plane and planar quantum codes", quant-ph/9810055, Foundations of Computational Mathematics 1 (2001) 325-332. |
| [5] | M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (New York: W. H. Freeman 1979) |
| [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 Press 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", UCSD preprint (2001). |
| [8] | D. A. Meyer, "Sophisticated quantum search without entanglement", quant-ph/0007070, Physical Review Letters 85 (2000) 2014-2017. |
| [9] |
D. R. Simon,
"On the power of quantum computation",
in S. Goldwasser, ed.,
Proceedings of the 35th IEEE Symposium on the Foundations of Computer Science (FOCS)
Santa Fe, NM (Los Alamitos, CA: IEEE Press 1994) 116-123; D. R. Simon, "On the power of quantum computation", SIAM Journal of Computing 26 (1997) 1474-1483. |
| [10] | R. Beals, H. Buhrman, R. Cleve, M. Mosca and R. de Wolf, "Quantum lower bounds by polynomials", quant-ph/9802049, in Proceedings of the 39th IEEE Symposium on the Foundations of Computer Science (FOCS) (Los Alamitos, CA: IEEE Press 1998) 352-361. |
| [11] | M. Boyer, G. Brassard, P. Høyer and A. Tapp, "Tight bounds on quantum searching", quant-ph/9605034, Fortschritte der Physik 46 (1998) 493-505. |
| [12] | C. Zalka, "Grover's quantum searching algorithm is optimal", quant-ph/9711070, Physical Review A 60 (1999) 2746-2751. |
| [13] | C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, "Strengths and weaknesses of quantum computing", quant-ph/9701001, SIAM Journal of Computing 26 (1997) 1510-1523. |
| [14] | N. Nisan and M. Szegedy, "On the degree of Boolean functions as real polynomials", in Proceedings of the 24th ACM Symposium on the Theory of Computing (STOC) (New York: ACM 1992) 462-467. |
| [15] | M. H. Freedman A. Yu. Kitaev, M. Larson and Z. Wang, "Topological quantum computation", quant-ph/0101025, |
| [16] | M. Minsky and S. Papert, Perceptrons: An Introduction to Computational Geometry (Cambridge, MA: MIT Press 1969). |
| [17] | C. Moore and J. P. Crutchfield, "Quantum automata and quantum grammars", quant-ph/9707031, Theoretical Computer Science 237 (2000) 275-306. |
| [18] | A. Ambainis and R. Freivalds, "1-way quantum finite automata: strengths, weaknesses and generalizations", quant-ph/9802062, in Proceedings of the 39th IEEE Symposium on the Foundations of Computer Science (FOCS) (Los Alamitos, CA: IEEE Press 1998) 332-341. |
| [19] | A. Yu. Kitaev, "Quantum measurements and the abelian stabilizer problem", quant-ph/9511026. |
| [20] | R. Cleve, A. K. Ekert, C. Macchiavello and M. Mosca "Quantum algorithms revisited", quant-ph/9708016, Proceedings of the Royal Society of London A 454 (1998) 339-354. |
| [21] | C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres and W. K. Wootters, "Teleporting an unknown quantum state via dual classical and EPR channels", Physical Review Letters 70 (1993) 1895-1899. |
| [22] | C. H. Bennett and S. J. Wiesner, "Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states", Physical Review Letters 69 (1992) 2881-2884. |
| [23] |
P. W. Shor,
"Algorithms for quantum computation: discrete logarithms and factoring",
in Proceedings of the 35th Annual Symposium on Foundations of Computer Science
(Los Alamitos, CA: IEEE Press 1994); P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer", quant-ph/9508027, SIAM Journal of Computing 26 (1997) 1484-1509. |