A quantum active learning algorithm for sampling against adversarial attacks

Abstract

Adversarial attacks represent a serious menace for learning algorithms and may compromise the security of future autonomous systems. A theorem by Khoury and Hadfield-Menell (KH), provides sufficient conditions to guarantee the robustness of machine learning algorithms, but comes with a caveat: it is crucial to know the smallest distance among the classes of the corresponding classification problem. We propose a theoretical framework that allows us to think of active learning as sampling the most promising new points to be classified, so that the minimum distance between classes can be found and the theorem KH used. Additionally, we introduce a quantum active learning algorithm that makes use of such framework and whose complexity is polylogarithmic in the dimension of the space, $m$, and the size of the initial training data $n$, provided the use of qRAMs; and polynomial in the precision, achieving an exponential speedup over the equivalent classical algorithm in $n$ and $m$. This algorithm may be nevertheless `dequantized' reducing the advantage to polynomial.

arXiv commentContains an additional dequantization appendix E that does not appear in the published version

References in corpus (16)

• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum machine learning in feature Hilbert spaces
• Quantum Amplitude Amplification and Estimation
• Quantum principal component analysis
• An introduction to quantum machine learning
• Quantum random access memory
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Data re-uploading for a universal quantum classifier
• Quantum Generative Adversarial Networks for Learning and Loading Random Distributions
• On the relationship between continuous- and discrete-time quantum walk
• Active learning machine learns to create new quantum experiments
• Quantum speedup for active learning agents
• Quantum algorithms and the finite element method
• Bayesian Deep Learning on a Quantum Computer

Cited by in corpus (4)

• Quantum Adversarial Machine Learning
• Active Learning Approach to Optimization of Experimental Control
• Quantum Active Learning
• Active Learning in Physics: From 101, to Progress, and Perspective