Abstract
The study of quantum computation has been motivated, in part, by the possibility that quantum computers can perform certain tasks dramatically faster than classical computers. Many of the known quantum-over-classical speedups, such as Shor’s algorithm for factoring integers and Grover’s search algorithm, can be framed as oracle problems or concept learning problems. In one model of concept learning, a student wishes to learn a concept from a teacher by making queries of the teacher. In the interest of efficiency, the student wishes to learn the concept by making as few queries as possible. For any such concept learning problem, there is a corresponding quantum concept learning problem. In the quantum version, the student is allowed to ask a superposition of queries – mathematically, a linear combination of queries – and the teacher answers with the corresponding superposition of the responses. After making this idea precise, we will examine several concept learning problems and their quantum analogues. We will discuss recent joint work with Daniel Copeland (UCSD), in which we show how tools from representation theory can be used to precisely analyze any quantum learning problem with sufficient symmetry.
Bio
Jamie Pommersheim has been the Katherine Piggott Professor of Mathematics at Reed College since 2004. He completed his Ph.D. at the University of Chicago under the direction of Willam Fulton. He held postdoctoral positions at the Institute for Advanced Study, MIT, and U.C. Berkeley, as well as faculty positions at New Mexico State University, Pomona College, and UCSD. Pommersheim has published research papers in several areas of math, including algebraic geometry, number theory, topology, and quantum computation.