PAC Learning on a Quantum Computer : A New ERM Algorithm and Sample Complexity Bounds

We 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 handles with post-measurement collapse and indicate upper bounds on its sample complexity. Time permitting, I will discuss the problem of quantifying the information content in the outcome of a quantum measurement.

PAC Learning on a Quantum Computer : A New ERM Algorithm and Sample Complexity Bounds

Abstract

Arun Padakandla, University of Tennessee, Knoxville