Binary classification with classical instances and quantum labels

Springer Science and Business Media LLC - Tập 3 Số 1 - 2021
Christoph Matthias1
1Department of Mathematics, Technical University of Munich, Garching, Germany

Tóm tắt

AbstractIn 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.

Từ khóa


Tài liệu tham khảo

Aaronson S (2007) The learnability of quantum states. Proc Roy Soc A Math Phys Eng Sci 463 (2088):3089–3114. https://doi.org/10.1098/rspa.2007.0113

Aaronson S (2018) Shadow tomography of quantum states. In: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing. STOC. https://doi.org/10.1145/3188745.3188802, vol 2018. Association for Computing Machinery, New York, pp 325–338

Aaronson S, Hazan EE, Chen X, Kale S, Nayak A (2018) Online learning of quantum states. In: Advances in neural information processing systems, pp 8962–8972

Angluin D, Laird P (1988) Learning from noisy examples. Mach Learn 2(4):343–370. https://doi.org/10.1023/A:1022873112823

Arunachalam S, de Wolf R (2017) Guest column: A survey of quantum learning theory. SIGACT News 48. https://doi.org/10.1145/3106700.3106710

Arunachalam S, de Wolf R (2018) Optimal quantum sample complexity of learning algorithms. J Mach Learn Res 19(71):1–36. http://jmlr.org/papers/v19/18-195.html

Arunachalam S, Chakraborty S, Lee T, Paraashar M, de Wolf R (2019a) Two new results about quantum exact learning. In: Baier C, Chatzigiannakis I, Flocchini P, Leonardi S (eds) 46th International colloquium on automata, languages, and programming (ICALP 2019), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, Leibniz International Proceedings in Informatics (LIPIcs). https://doi.org/10.4230/LIPIcs.ICALP.2019.16. http://drops.dagstuhl.de/opus/volltexte/2019/10592, vol 132, pp 16:1–16:15

Arunachalam S, Grilo AB, Sundaram A (2019b) Quantum hardness of learning shallow classical circuits. arXiv:1903.02840

Arunachalam S, Grilo AB, Yuen H (2020) Quantum statistical query learning

Aslam JA, Decatur SE (1996) On the sample complexity of noise-tolerant learning. Inf Process Lett 57(4):189–195. https://doi.org/10.1016/0020-0190(96)00006-3

Atıcı A, Servedio RA (2007) Quantum algorithms for learning andtestingjuntas. QuantumInfProcess 6(5):323–348. https://doi.org/10.1007/s11128-007-0061-6

Bartlett PL, Mendelson S (2002) Rademacherandgaussiancomplexities:Riskboundsandstructuralresults. JMachLearnRes 3(Nov):463–482. http://www.jmlr.org/papers/volume3/bartlett02a/bartlett02a.pdf

Ben-David S, Dichterman E (1998) Learningwithrestrictedfocusofattention. JComputSystSci 56(3):277–298. https://doi.org/10.1006/jcss.1998.1569

Bernstein E, Vazirani U (1993) Quantumcomplexitytheory. In: Kosaraju R (ed) Proceedingsofthetwenty-fifthannualACMsymposiumonTheoryofcomputing. https://doi.org/10.1145/167088.167097. ACM, NewYork, pp 11–20

Blumer A, Ehrenfeucht A, Haussler D, Warmuth MK (1989) Learnabilityandthevapnik-chervonenkisdimension, vol 36. https://doi.org/10.1145/76359.76371.http://dl.acm.org/ft_{g}ateway.cfm?id=76371&type=pdf

Brandão FGSL, Kastoryano MJ (2019) Finitecorrelationlengthimpliesefficientpreparationofquantumthermalstates. CommunMathPhys 365(1):1–16. https://doi.org/10.1007/s00220-018-3150-8

Bshouty NH, Jackson JC (1998) Learningdnfovertheuniformdistributionusingaquantumexampleoracle. SIAMJComput 28(3):1136–1153. https://doi.org/10.1137/S0097539795293123

Caro MC (2020) Quantumlearningbooleanlinearfunctionsw.r.t.productdistributions. QuantumInfProcess 19(6):1–41. https://doi.org/10.1007/s11128-020-02661-1

Cesa-Bianchi N, Dichterman E, Fischer P, Shamir E, Simon HU (1999) Sample-efficientstrategiesforlearninginthepresenceofnoise. JACM(JACM) 46(5):684–719. https://doi.org/10.1145/324133.324221

Cheng HC, Hsieh MH, Yeh PC (2016) Thelearnabilityofunknownquantummeasurements. QuantumInfComput 16(7-8):615–656

Chowdhury AN (2020) Low,GH, Avariationalquantumalgorithmforpreparingquantumgibbsstates, WiebeN

Chung KM, Lin HH (2018) Sampleefficientalgorithmsforlearningquantumchannelsinpacmodelandtheapproximatestatediscriminationproblem

Ciliberto C, Herbster M, Ialongo AD, Pontil M, Rocchetto A, Severini S, Wossnig L (2018) Quantummachinelearning:Aclassicalperspective. ProcRoySocAMathPhysEngSci 474(2209):20170551. https://doi.org/10.1098/rspa.2017.0551

Cross AW, Smith G, Smolin JA (2015) Quantumlearningrobustagainstnoise. PhysRevA 92 (1):97. https://doi.org/10.1103/PhysRevA.92.012327

Grilo AB, Kerenidis I, Zijlstra T (2017) Learningwitherrorsiseasywithquantumsamples.arXiv:1702.08255

Hanneke S (2016) Theoptimalsamplecomplexityofpaclearning. JMachLearnRes 17(1):1319–1333. http://dl.acm.org/ft_{g}ateway.cfm?id=2946683&type=pdf

Heinosaari T, Ziman M (2012) Themathematicallanguageofquantumtheory:Fromuncertaintytoentanglement. CambridgeUniversityPress, Cambridge. https://doi.org/10.1017/CBO9781139031103

Holevo A (1973) Statisticaldecisiontheoryforquantumsystems. JMultivarAnal 3(4):337–394. https://doi.org/10.1016/0047-259X(73)90028-6

Kanade V, Rocchetto A, Severini S (2019) Learningdnfsunderproductdistributionsviaμ-biasedquantumfouriersampling. QuantumInfComput 19(15&16):1261–1278. http://www.rintonpress.com/xxqic19/qic-19-1516/1261-1278.pdf

Laird PD (1988) Learningfromgoodandbaddata.TheKluwerinternationalseriesinengineeringandcomputersciences,knowledgerepresentation,learning andexpertsystems, vol 47. Springer, Boston. https://doi.org/10.1007/978-1-4613-1685-5

Montanaro A (2012) Thequantumquerycomplexityoflearningmultilinearpolynomials. InfProcessLett 112(11):438–442. https://doi.org/10.1016/j.ipl.2012.03.002

Natarajan N, Dhillon IS, Ravikumar P, Tewari A (2013) Learningwithnoisylabels, pp 1196–1204

Nielsen MA, Chuang IL (2009) Quantumcomputationandquantuminformation, 10th edn. CambridgeUniv.Press, Cambridge

Ristè D, daSilva MP, Ryan CA, Cross AW, Córcoles AD, Smolin JA, Gambetta JM, Chow JM, Johnson BR (2017) Demonstrationofquantumadvantageinmachinelearning. NpjQuantumInf 3 (1):16. https://doi.org/10.1038/s41534-017-0017-3

Servedio RA, Gortler SJ (2004) Equivalencesandseparationsbetweenquantumandclassicallearnability. SIAMJComput 33(5):1067–1092. https://doi.org/10.1137/S0097539704412910

Shalev-Shwartz S, Ben-David S (2014) Understandingmachinelearning:Fromtheorytoalgorithms. CambridgeUniversityPress, Cambridge. https://doi.org/10.1017/CBO9781107298019

Shannon CE (1948) Amathematicaltheoryofcommunication. BellSystTechJ 27(3):379–423. https://doi.org/10.1002/j.1538-7305.1948.tb01338.x

Valiant LG (1984) Atheoryofthelearnable. CommunACM 27(11):1134–1142. https://doi.org/10.1145/1968.1972

Vapnik VN, Chervonenkis AY (1971) Ontheuniformconvergenceofrelativefrequenciesofeventstotheirprobabilities. TheoryProbabitsAppl 16(2):264–280. https://doi.org/10.1137/1116025

Vershynin R (2018) High-dimensionalprobability:Anintroductionwithapplicationsindatascience,Cambridgeseriesinstatisticalandprobabilistic mathematicsvol47. CambridgeUniversityPress, Cambridge

Watrous J (2018) Thetheoryofquantuminformation. CambridgeUniversityPress, Cambridge. https://doi.org/10.1017/9781316848142

Wilde M (2013) Quantuminformationtheory. CambridgeUniversityPress, Cambridge. https://doi.org/10.1017/CBO9781139525343

Yuen H, Kennedy R, Lax M (1975) Optimumtestingofmultiplehypothesesinquantumdetectiontheory. IEEETransInfTheory 21(2):125–134. https://doi.org/10.1109/TIT.1975.1055351

Thông tin
Thông tin xuất bản

Springer Science and Business Media LLC

Tập 3 Số 1

Thông tin tác giả