Quantum Learning Theory

Ronald de Wolf: Quantum learning theory: samples, time, queries

Quantum learning theory studies the theoretical aspects of how quantum computing can change and improve machine learning. I will introduce several mathematical models of learning, which can be instantiated to classical or quantum data: the Probably Approximately Correct (PAC) model and exact learning from membership queries. We will see to what extent quantum computers can improve the sample complexity and/or the time complexity of learning in these models. My three lecture blocks will cover:

1. The PAC model of learning theory. Learning from quantum examples. Positive results using Fourier sampling.
2. Sample complexity of quantum PAC learning. Learning from quantum membership queries.
3. Time complexity of quantum PAC learning.

Reading material:
I will mostly follow my survey paper with Srinivasan Arunachalam: https://arxiv.org/abs/1701.06806

For general background on quantum computing (especially algorithms and complexity), you could have a look at: https://arxiv.org/abs/1907.09415

Yihui Quek: information-theoretic lower bounds for learning

Science is often seen as a pursuit to expand the boundaries of what can be done: to develop new algorithms and insights; to learn faster and better. We know far less about what we can’t do. And yet, knowing the boundaries of what is possible would save us from wasting effort to further optimize our solutions beyond that point; more importantly, proving a lower bound often yields deeper insights into the nature of measurements and quantum computation itself.

After a brief tour through common techniques to design sample efficient learning algorithms (also known as upper bounds), I will delve into information-theoretic lower bounds for learning and statistical inference, including the ONE cool reduction that instantly makes a learning lower bound into an information-theoretic exercise! If time permits, we can also take a foray into computational lower bounds.

Robert Huang: quantum advantages in learning from experiments

Quantum technology has the potential to revolutionize how we acquire and process experimental data to learn about the physical world. A quantum learning agent that transduces data from a physical system to a stable quantum memory and processes that data using quantum computation could have significant advantages over classical learning agents, which measure the physical system to obtain classical data and process the data using classical computation.

This lecture presents a mathematical framework for proving that quantum agents can learn from exponentially fewer experiments than classical agents. We will look at multiple tasks with an exponential quantum advantage, such as predicting many incompatible properties in physical systems, performing quantum principal component analysis, learning approximate models of physical dynamics, and distinguishing different kinds of evolutions. For each task, we will design an efficient algorithm for the quantum agent and prove that all algorithms the classical agent could run are exponentially inefficient.

References:

A general overview and introduction to proving quantum advantages in learning from experiments: Huang, Hsin-Yuan, et al. "Quantum advantage in learning from experiments." Science 376.6598 (2022): 1182-1186. arXiv link: https://arxiv.org/abs/2112.00778

More advanced mathematical/conceptual techniques for proving quantum advantages in learning: Chen, Sitan, et al. "Exponential separations between learning with and without quantum memory." 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022. arXiv link: https://arxiv.org/abs/2111.05881

The quantum learning algorithm for predicting all 4^n Pauli observables from only O(n) samples of the unknown state \rho is given in this work: Huang, Hsin-Yuan, Richard Kueng, and John Preskill. "Information-theoretic bounds on quantum advantage in machine learning." Physical Review Letters 126.19 (2021): 190505. arXiv link: https://arxiv.org/abs/2101.02464

Ingo Roth: Quantum device characterization and tomography

Quantum device characterization is the central application of quantum learning theory in today's experiments. The precise control of complex quantum systems promises numerous technological applications including analogue simulation and digital quantum computing. The complexity of such devices renders the characterization and certification of their correct functioning a challenge. To address this challenge, numerous methods were developed in the last decade.
In this masterclass, we provide an introduction to the field of quantum device characterization and its mathematical foundations, focusing on one of the still most frequently used techniques in practice: quantum state tomography.

Laura Mancinska: Certification of large quantum systems.

In this talk I will introduce the concept of self-testing which aims to answer the fundamental question of how do we certify proper functioning of black-box quantum devices. Self-testing is the strongest form of certification and it allows a classical user to deduce the quantum state and measurements used to produce certain measurement statistics. The main goal of this area is to understand which states and measurements can be certified and how efficiently.

We will see that surprisingly it can be possible to certify arbitrarily large quantum states and measurements with just four binary-outcome measurements. I will also present a general method for certification of quantum measurements. We will see a scheme that allows us to self-test an arbitrary real projective measurement.

Tim Möbus: Dissipation-enabled bosonic Hamiltonian learning via new information-propagation bounds