2020/06/30 by Matthias C. Caro, C. Matthias
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Arithmetic #Artificial intelligence #Binary classification #Binary number #Computability, Logic, AI Algorithms #Computer science #Dimension (graph theory) #Machine Learning and Algorithms #Mathematical analysis #Mathematics #Pattern recognition (psychology) #Physics #Pure mathematics #Quantum #Quantum Computing Algorithms and Architecture #Quantum algorithm #Quantum complexity theory #Quantum mechanics #Quantum state #Sample (material) #Sample complexity #Sample size determination #Statistical physics #Statistics #Task (project management) #Theoretical computer science #Upper and lower bounds #VC dimension #cs.LG #quant-ph
paper · pdf · doi:10.1007/s42484-021-00043-z
published as Quantum Mach. Intell. 3, 18 (2021) · 17 pages (main body) + 23 pages (references and appendix); improved presentation including illustrative examples
openalex created_date 2020/06/19 · arxiv created 2021/04/18 · openalex publication_date 2021/05/05 · arxiv updated 2021/05/10 · openalex updated_date 2026/08/05
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.