🦊 FOCS 2024 Workshop: Recent Advances in Quantum Learning
⏰ Date: October 27, 2024
How can we learn about properties of quantum systems? Given that, to the best of our knowledge, the world is fundamentally quantum, this question is arguably one of the most fundamental statistical estimation problems, and also has important ramifications for the development of large scale quantum devices. While such questions have a long history dating back to seminal work of Helstrom and Holevo, amongst others, there has been a recent flurry of progress in understanding both the statistical and computational aspects of quantum learning, including many important contributions by members of the TCS community.
The goal of this workshop is to both introduce the concepts underlying quantum learning to the wider FOCS/STOC community, as well as to survey some of the exciting recent developments and open directions in this area. While we appreciate that the word “quantum” can be daunting to some in the TCS community, many of the important open questions in this area do not require much quantum background at all. In fact, many of the techniques which have found recent success are directly inspired by techniques from classical learning theory and optimization. It is our firm belief that the topics covered in this workshop will be quite approachable for the TCS community—including those without any prior quantum background—and more importantly, that this workshop will foster new dialogues across previously disparate areas of research.
Organizers
Program: The workshop will be located in the Lasalle Room on the 15th floor of voco: Chicago Downton
Zoom link for remote participants
The program will feature tutorial-style talks on recent and exciting results in this area, and will gather open problems in the topic from and for the participants:
- 9:00-9:30: Jerry Li (Microsoft Research and University of Washington)
Quantum Learning Theory for Dummies [slides]
Abstract: This talk will serve as crash course for the basic concepts in quantum learning theory.
We will mathematically define the basic problems in quantum learning theory, and see how they arise mathematically as a natural non-commutative analog of classical statistics, as well as where they differ.
No prior knowledge of quantum will be expected for this talk.
- 9:35-10:30: Ewin Tang (Berkeley)
How to learn a Hamiltonian [slides]
Abstract: When can we efficiently learn the parameters of an unknown quantum system? This question, which we formalize as Hamiltonian learning, captures the fundamental task of the researcher who wants to understand the behavior of a complicated quantum device. I will survey what is known about this problem, including techniques, results, and open directions, with an eye towards accessibility. In particular, I'll discuss the many insights that classical TCS bring to the table, along with the new and exciting challenges which come with learning in the quantum realm.
- 11:05-12:00: Jonas Haferkamp (Harvard University)
Random unitaries from random quantum circuits [slides]
Abstract: Random quantum circuits are central to quantum information theory, with applications ranging from benchmarking quantum devices and quantum supremacy experiments to modeling black hole dynamics. Many of these applications are related to the rapid generation of quantum pseudorandomness. In this talk, I will discuss the concepts of unitary t-designs and pseudorandom unitaries, and their generation with random quantum circuits. I will also review recent advances that resulted in near-optimal constructions of quantum pseudorandomness. Finally, I will explain the implications of these results for the learnability of quantum circuits.
- 2:00-2:55: Anurag Anshu (Harvard University)
Learning theory in the “physical” corner of the Hilbert space [slides]
Abstract: In recent years, there has been a surge of research on the learnability of quantum states that emerge from physically motivated settings. Prominent examples include Gibbs states, shallow quantum circuits, and tensor network states. This talk will provide a survey of these developments, emphasizing how efficient algorithms are intrinsically linked to the fundamental structures of these quantum states. A key theme in these results is the role of locality, which necessitates the use of experiment-friendly measurements that act jointly on only a few qubits. We will also discuss the major challenges that remain, particularly in the quest for optimal algorithms.
- 3:00-3:30: Open Questions Session
[List of open problems]
- 4:05-5:00: Xun Gao (University of Colorado Boulder)
No-go theorem of hidden variable theory and quantum machine learning [slides]
Abstract: Generative models in machine learning have gained a lot of attention for their practical applications. In this tutorial, we explore how quantum correlations can enhance these models and investigate the potential quantum advantage based on the no-go theorem of hidden variable theory. Unlike other tutorials that focus on sample complexity directly, our focus is on the expressive power of the learning models. We give an example showing how quantum correlations—specifically, contextuality—can define a quantum neural network that outperforms any reasonable classical neural network in terms of the number of hidden neurons required for a language translation task. This includes a proof for artificially constructed data and numerical results for real-world data. We will also briefly mention a possible mathematical framework that could solidify this claim, and the connection between the expressive power of quantum generative models and other areas like communication complexity and non-negative matrix factorization. This direction is still in its early stages, and I hope this tutorial will inspire others to make more connections from foundational research in quantum information to practically useful problems in machine learning.
Call for Open Problems: To suggest an open problem, please fill this Google form 📋
This website template was shamessly stolen from Clément Cannnnonnne