Binary Classification with Classical Instances and Quantum Labels

Abstract

In classical statistical learning theory, one of the most well studied problems is that of binary classification. The information-theoretic sample complexity of this task is tightly characterized by the Vapnik-Chervonenkis (VC) dimension. A quantum analog of this task, with training data given as a quantum state has also been intensely studied and is now known to have the same sample complexity as its classical counterpart. We propose a novel quantum version of the classical binary classification task by considering maps with classical input and quantum output and corresponding classical-quantum training data. We discuss learning strategies for the agnostic and for the realizable case and study their performance to obtain sample complexity upper bounds. Moreover, we provide sample complexity lower bounds which show that our upper bounds are essentially tight for pure output states. In particular, we see that the sample complexity is the same as in the classical binary classification task w.r.t. its dependence on accuracy, confidence and the VC-dimension.

arXiv comment17 pages (main body) + 23 pages (references and appendix); improved presentation including illustrative examples

References in corpus (11)

• Quantum machine learning: a classical perspective
• Demonstration of quantum advantage in machine learning
• Quantum learning robust to noise
• The Optimal Sample Complexity of PAC Learning
• A Variational Quantum Algorithm for Preparing Quantum Gibbs States
• Quantum Algorithms for Learning and Testing Juntas
• Learning with Errors is easy with quantum samples
• Optimal Quantum Sample Complexity of Learning Algorithms
• Quantum statistical query learning
• The Learnability of Quantum States
• Quantum Learning Boolean Linear Functions w.r.t. Product Distributions

Cited by in corpus (5)

• Information-theoretic bounds on quantum advantage in machine learning
• Out-of-distribution generalization for learning quantum dynamics
• Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix
• Postselection-free learning of measurement-induced quantum dynamics
• Clifford Circuits can be Properly PAC Learned if and only if $\text{RP}=\text{NP}$