DQC Seminar Series: Information-memory-computation tradeoffs for learning quantum states

Abstract: As the computational resources for existing quantum devices continue to grow, so too does their potential to help us analyze quantum experimental data and learn about the physical universe. In this talk, I will describe recent progress towards understanding the fundamental capabilities and limitations of near- and intermediate-term devices for such tasks. In the first part of the talk, I will provide a gentle survey on our work in this direction over the last few years, focusing on the tradeoff between statistical complexity and quantum memory for fundamental tasks like full tomography, state certification, shadow tomography, Pauli channel estimation, and purity estimation. In the second part of the talk, I will describe a new general framework for proving tradeoffs between the amount of data one has available and the computational complexity needed for quantum learning, inspired by tools from the literature on information-computation gaps for classical statistical inference. Short bio: Sitan Chen is an Assistant Professor of Computer Science at Harvard University, where he is a member of the Theory of Computation, the ML Foundations group, and the Harvard Quantum Initiative. Previously, he was an NSF math postdoc at UC Berkeley, after completing his PhD in EECS at MIT in 2021. He is broadly interested in algorithmic questions about learning from data, most recently related to the science and theory of localization-based generative modeling, and the design of quantum protocols for learning about the physical universe. His work has been recognized with an NSF CAREER award, an ICML Outstanding Paper Award, and the Harvard Dean's Competitive Fund for Promising Scholarship. --- Upcoming seminars: 02 Oct: Heather Lewandowski 16 Oct: Senrui Chen 30 Oct: TBA 20 Nov: Jeff Thompson 04 Dec: Felix Knollman