Quantum Computation Seminar (Fall quarter 2002):
QUANTUM LEARNING

Room & time: AP&M 7218, Tuesdays 11:30-12:30

Description

Improvements of quantum over classical algorithms have only been proved in the oracle context, that is, with respect to their query complexity. Query, or sample, complexity is particularly relevant for machine learning. This suggests the possibility that quantum computers might be superior to classical computers for certain computational learning tasks. The goal of the seminar this quarter is to explore this possibility.

Since concept learning can be understood as a search problem in a large hypothesis space, we will begin by discussing quantum search algorithms: Grover's, Bernstein-Vazirani's, etc. After some discussion of relevant parts of classical machine learning, we will try to understand how to formalize quantum learning, reading papers of Bshouty, Jackson, Gortler and Servedio. Depending on the interests of the participants we may also discuss other topics, such as recent proposals for "quantum neural nets" and pattern recognition.

David Meyer and Jamie Pommersheim will give several of the initial lectures, but we are hoping for active participation by others as well. This is intended as a working seminar, so while some knowledge about quantum computing [1], or computational complexity [2], or machine learning [3] will be useful, no-one is expected to have a background in all of these subjects, only an interest in learning about them.

Upcoming conferences

7-9 feb 03
Santa Fe, NM
Fifth Annual SQuInT Workshop
This will be a good, low-pressure forum for students to present their work and meet other quantum computing researchers in the American Southwest.
10-13 feb 03
San Diego, CA
SIAM Conference on Computational Science and Engineering
There will be a Minisymposium on "Quantum networks for computation and control", closely related to the topic of this seminar.

Schedule (incremental)

1 oct 02
David Meyer
Introductory lecture [pdf (revised 1 nov 01; missing figure)]
motivations for seminar
paucity of quantum algorithms
proposals for "quantum neural nets"
introduction to learning problems
concept learning
learning from membership queries [4]
an example learning problem
classical solutions
a quantum solution
8 oct 02
David Meyer
Grover's algorithm exemplifies quantum learning from membership queries [pdf]
basics of quantum algorithms
amplitudes and probabilities
unitary evolution
Grover's algorithm [5]
as iteration of pairs of reflections
15 oct 02
David Meyer
Single query quantum learning [pdf (missing figures)]
22 oct 02
David Meyer
Quantum learning beyond concepts
29 oct 02
Markus Hunziker
Query complexity of quantum algorithms for structured search problems
5 nov 02
David Meyer
Lower bounds on classical sample complexity
12 nov 02
No seminar
19 nov 02
David Meyer
Classical perceptrons
26 nov 02
David Meyer
Quantum perceptrons?
3 dec 02
No seminar
10 dec 02
Jamie Pommersheim
Lower bounds on quantum sample complexity

Bibliography

[1] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge: Cambridge University Press 2000) [website].
[2] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (New York: W. H. Freeman 1979)
[3] For the computer science perspective see, e. g., T. M. Mitchell, Machine Learning (San Francisco: McGraw-Hill 1997) [website];
for a recent mathematical perspective see F. Cucker and S. Smale, "On the mathematical foundations of learning", Bulletin of the AMS 39 (2002) 1-49.
[4] D. Angluin, "Queries and concept learning", Machine Learning 2 (1988) 319-342.
[5] 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.

Likely topics

Last modified: 02 dec 02.