Breaking a Classical Barrier for Classifying Arbitrary Test Examples in the Quantum Model

Considering arbitrary test examples is a new approach for addressing adversarial robustness. This model was introduced by Goldwasser et al.~[2020], where 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, standard risk and number of samples, is presented. We show that this barrier can be broken in the quantum world.We consider a new model, influenced by the quantum PAC-learning model introduced by Bshouty and Jackson~[1995] and similar in spirit to Goldwaser et al.~[2020]. In this model we give an interactive protocol between the learner and the adversary (at test-time) that guarantees robustness. In this work we break the lower bound from Goldwasser et al.~[2020].From the technical perspective, our protocol is inspired by recent advances in delegation of quantum computation, e.g. Mahadev~[2018]. 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.