Speaker: Jerry Li (Microsoft Research)
When: 1:30PM, Oct 17, 2023
Where: CSE2 371
Abstract:
How can we learn inherently quantum phenomena? Not only is this question important for verification of quantum computation, but it is arguably one of the most basic learning theoretic questions about the physical world. While there has been much theoretical attention on this question, almost all of the algorithms developed are impractical to run on existing (so called noisy intermediate scale quantum or NISQ) quantum computers. One key bottleneck to implementing these algorithms is that NISQ devices lack the large scale quantum memory required. However, in contrast to the unconstrained quantum setting, where in many cases optimal rates are known, the theory of learning on such NISQ devices was, prior to our work, much less well understood.
In this talk, we will describe a line of work on understanding the complexity of learning with limited amounts of quantum memory, and more generally, learning on NISQ devices. For many natural problems, we will demonstrate sharp characterizations for the sample complexity of learning with and without quantum memory. No prior knowledge of quantum will be necessary for the talk, nor possessed by the speaker. The first half of the talk will consist of a gentle introduction to the relevant concepts in quantum information theory.