PAC Learning of Quantum Measurement Classes : Sample Complexity Bounds and Universal Consistency

Arun Padakandla, Abram Magner
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:11305-11319, 2022.

Abstract

We formulate a quantum analogue of the fundamental classical PAC learning problem. As on a quantum computer, we model data to be encoded by modifying specific attributes - spin axis of an electron, plane of polarization of a photon - of sub-atomic particles. Any interaction, including reading off, extracting or learning from such data is via quantum measurements, thus leading us to a problem of PAC learning Quantum Measurement Classes. We propose and analyze the sample complexity of a new ERM algorithm that respects quantum non-commutativity. Our study entails that we define the VC dimension of Positive Operator Valued Measure(ments) (POVMs) concept classes. Our sample complexity bounds involve optimizing over partitions of jointly measurable classes. Finally, we identify universally consistent sequences of POVM classes. Technical components of this work include computations involving tensor products, trace and uniform convergence bounds.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-padakandla22a, title = { PAC Learning of Quantum Measurement Classes : Sample Complexity Bounds and Universal Consistency }, author = {Padakandla, Arun and Magner, Abram}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {11305--11319}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/padakandla22a/padakandla22a.pdf}, url = {https://proceedings.mlr.press/v151/padakandla22a.html}, abstract = { We formulate a quantum analogue of the fundamental classical PAC learning problem. As on a quantum computer, we model data to be encoded by modifying specific attributes - spin axis of an electron, plane of polarization of a photon - of sub-atomic particles. Any interaction, including reading off, extracting or learning from such data is via quantum measurements, thus leading us to a problem of PAC learning Quantum Measurement Classes. We propose and analyze the sample complexity of a new ERM algorithm that respects quantum non-commutativity. Our study entails that we define the VC dimension of Positive Operator Valued Measure(ments) (POVMs) concept classes. Our sample complexity bounds involve optimizing over partitions of jointly measurable classes. Finally, we identify universally consistent sequences of POVM classes. Technical components of this work include computations involving tensor products, trace and uniform convergence bounds. } }
Endnote
%0 Conference Paper %T PAC Learning of Quantum Measurement Classes : Sample Complexity Bounds and Universal Consistency %A Arun Padakandla %A Abram Magner %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-padakandla22a %I PMLR %P 11305--11319 %U https://proceedings.mlr.press/v151/padakandla22a.html %V 151 %X We formulate a quantum analogue of the fundamental classical PAC learning problem. As on a quantum computer, we model data to be encoded by modifying specific attributes - spin axis of an electron, plane of polarization of a photon - of sub-atomic particles. Any interaction, including reading off, extracting or learning from such data is via quantum measurements, thus leading us to a problem of PAC learning Quantum Measurement Classes. We propose and analyze the sample complexity of a new ERM algorithm that respects quantum non-commutativity. Our study entails that we define the VC dimension of Positive Operator Valued Measure(ments) (POVMs) concept classes. Our sample complexity bounds involve optimizing over partitions of jointly measurable classes. Finally, we identify universally consistent sequences of POVM classes. Technical components of this work include computations involving tensor products, trace and uniform convergence bounds.
APA
Padakandla, A. & Magner, A.. (2022). PAC Learning of Quantum Measurement Classes : Sample Complexity Bounds and Universal Consistency . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:11305-11319 Available from https://proceedings.mlr.press/v151/padakandla22a.html.

Related Material