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.

Will also be streamed live on the Galois YouTube channel: https://www.youtube.com/channel/UC1TJ20iM_dCa0pq6h0tA79w