Breaking a Classical Barrier for Classifying Arbitrary Test Examples in the Quantum Model
Grzegorz Gluch, Khashayar Barooti, Rüdiger Urbanke
Abstract
A new model for adversarial robustness was introduced by Goldwasser et al. in [GKKM20]. In this model the authors present a selective and transductive learning algorithm which guarantees a low test error and low rejection rate wrt to the original distribution. Moreover, a lower bound in terms of the VC-dimension, the standard risk and the number of samples is derived. We show that this lower bound can be broken in the quantum world. We consider a new model, influenced by the quantum PAC-learning model introduced by [BJ95], and similar in spirit to the one in [GKKM20]. In this model we give an interactive protocol between the learner and the adversary (at test-time) that guarantees robustness. This protocol, when applied, breaks the lower bound from [GKKM20]. From the technical perspective, our protocol is inspired by recent advances in delegation of quantum computation, e.g. [Mah18]. But in order to be applicable to our task, we extend the delegation protocol to enable a new feature, e.g. by extending delegation of decision problems, i.e. BQP, to sampling problems with adversarially chosen inputs.
BibTeX
@InProceedings{pmlr-v206-gluch23a,
title = {Breaking a Classical Barrier for Classifying Arbitrary Test Examples in the Quantum Model},
author = {Gluch, Grzegorz and Barooti, Khashayar and Urbanke, R\"udiger},
booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics},
pages = {11457--11488},
year = {2023},
editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem},
volume = {206},
series = {Proceedings of Machine Learning Research},
month = {25--27 Apr},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v206/gluch23a/gluch23a.pdf},
url = {https://proceedings.mlr.press/v206/gluch23a.html},
abstract = {A new model for adversarial robustness was introduced by Goldwasser et al. in [GKKM20]. In this model the authors present a selective and transductive learning algorithm which guarantees a low test error and low rejection rate wrt to the original distribution. Moreover, a lower bound in terms of the VC-dimension, the standard risk and the number of samples is derived. We show that this lower bound can be broken in the quantum world. We consider a new model, influenced by the quantum PAC-learning model introduced by [BJ95], and similar in spirit to the one in [GKKM20]. In this model we give an interactive protocol between the learner and the adversary (at test-time) that guarantees robustness. This protocol, when applied, breaks the lower bound from [GKKM20]. From the technical perspective, our protocol is inspired by recent advances in delegation of quantum computation, e.g. [Mah18]. But in order to be applicable to our task, we extend the delegation protocol to enable a new feature, e.g. by extending delegation of decision problems, i.e. BQP, to sampling problems with adversarially chosen inputs.}
}