Date,Time,Venue: 9pm IST, 8th Dec 2021. The talk will be held online
PAC Learning on a Quantum Computer : A New ERM Algorithm and Sample Complexity Bounds
Arun Padakandla
University of Tennessee, Knoxville, USA.
08-12-21

---

Abstract

In this talk, I will address a quantum analogue of the fundamental classical PAC learning problem. In contrast to a conventional computer, data is encoded on a quantum computer by modifying specific attributes of sub-atomic particles. For example, the axis of spin of an electron or the plane of polarization of a photon can be modified to encode data. The behaviour of these particles is governed by the unique laws of quantum mechanics. In particular, extracting or learning from data encoded on sub-atomic particles is via quantum measurements. We are thus led to a problem of PAC learning Quantum Measurement Classes. I will present a new Quantum Empirical Risk minimization algorithm that respects quantum non-commutativity. Analyzing its complexity, I present upper bounds on the sample complexity of learning measurement classes. In the latter part of my talk, I will provide an overview of some of my findings in classical information theory.