{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T00:30:20Z","timestamp":1769733020842,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,11,6]],"date-time":"2020-11-06T00:00:00Z","timestamp":1604620800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,6]],"date-time":"2020-11-06T00:00:00Z","timestamp":1604620800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008848","name":"Elitenetzwerk Bayern","doi-asserted-by":"publisher","award":["TopMath"],"award-info":[{"award-number":["TopMath"]}],"id":[{"id":"10.13039\/501100008848","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DGE1656518"],"award-info":[{"award-number":["DGE1656518"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001655","name":"Deutscher Akademischer Austauschdienst","doi-asserted-by":"publisher","award":["7381410"],"award-info":[{"award-number":["7381410"]}],"id":[{"id":"10.13039\/501100001655","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004350","name":"Studienstiftung des Deutschen Volkes","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004350","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005713","name":"Technische Universit\u00e4t M\u00fcnchen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005713","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Mach. Intell."],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We characterize the expressive power of quantum circuits with the pseudo-dimension, a measure of complexity for probabilistic concept classes. We prove pseudo-dimension bounds on the output probability distributions of quantum circuits; the upper bounds are polynomial in circuit depth and number of gates. Using these bounds, we exhibit a class of circuit output states out of which at least one has exponential gate complexity of state preparation, and moreover demonstrate that quantum circuits of known polynomial size and depth are PAC-learnable.<\/jats:p>","DOI":"10.1007\/s42484-020-00027-5","type":"journal-article","created":{"date-parts":[[2020,11,6]],"date-time":"2020-11-06T14:02:41Z","timestamp":1604671361000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":33,"title":["Pseudo-dimension of quantum circuits"],"prefix":"10.1007","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9009-2372","authenticated-orcid":false,"given":"Matthias C.","family":"Caro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2117-9922","authenticated-orcid":false,"given":"Ishaun","family":"Datta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,6]]},"reference":[{"issue":"2088","key":"27_CR1","doi-asserted-by":"publisher","first-page":"3089","DOI":"10.1098\/rspa.2007.0113","volume":"463","author":"S Aaronson","year":"2007","unstructured":"Aaronson S (2007) The learnability of quantum states. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 463(2088):3089\u20133114. https:\/\/doi.org\/10.1098\/rspa.2007.0113","journal-title":"Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences"},{"key":"27_CR2","first-page":"109","volume":"23","author":"S Aaronson","year":"2016","unstructured":"Aaronson S (2016) The complexity of quantum states and transformations: From quantum money to black holes. Electronic Colloquium on Computational Complexity (ECCC) 23:109","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"Aaronson S (2018) Shadow tomography of quantum states. http:\/\/dl.acm.org\/ft_gateway.cfm?id=3188802&type=pdf","DOI":"10.1145\/3188745.3188802"},{"key":"27_CR4","unstructured":"Aaronson S, Chen X, Hazan E, Kale S (2018) Online learning of quantum states. http:\/\/dl.acm.org\/ft_gateway.cfm?id=3327572&type=pdf"},{"issue":"4","key":"27_CR5","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1145\/263867.263927","volume":"44","author":"N Alon","year":"1997","unstructured":"Alon N, Ben-David S, Cesa-Bianchi N, Haussler D (1997) Scale-sensitive dimensions, uniform convergence, and learnability. J ACM 44(4):615\u2013631. https:\/\/doi.org\/10.1145\/263867.263927","journal-title":"J ACM"},{"issue":"3","key":"27_CR6","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1017\/S0963548300004247","volume":"9","author":"M Anthony","year":"2000","unstructured":"Anthony M, Bartlett PL (2000) Function learning from interpolation. Comb Probab Comput 9(3):213\u2013225. https:\/\/doi.org\/10.1017\/S0963548300004247","journal-title":"Comb Probab Comput"},{"key":"27_CR7","doi-asserted-by":"crossref","unstructured":"Arunachalam S, de Wolf R (2017) Guest column: A survey of quantum learning theory. SIGACT News 48 , https:\/\/pure.uva.nl\/ws\/files\/25255496\/p41_arunachalam.pdf","DOI":"10.1145\/3106700.3106710"},{"issue":"2","key":"27_CR8","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1006\/jcss.1997.1557","volume":"56","author":"PL Bartlett","year":"1998","unstructured":"Bartlett PL, Long PM (1998) Prediction, learning, uniform convergence, and scale-sensitive dimensions. J Comput Sys Sci 56(2):174\u2013190. https:\/\/doi.org\/10.1006\/jcss.1997.1557","journal-title":"J Comput Sys Sci"},{"issue":"Nov","key":"27_CR9","first-page":"463","volume":"3","author":"PL Bartlett","year":"2002","unstructured":"Bartlett PL, Mendelson S (2002) Rademacher and gaussian complexities: Risk bounds and structural results. J Mach Learn Res 3(Nov):463\u2013482. http:\/\/www.jmlr.org\/papers\/volume3\/bartlett02a\/bartlett02a.pdf","journal-title":"J Mach Learn Res"},{"issue":"4","key":"27_CR10","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A Blumer","year":"1989","unstructured":"Blumer A, Ehrenfeucht A, Haussler D, Warmuth M K (1989) Learnability and the vapnik-chervonenkis dimension. J ACM 36(4):929\u2013965. https:\/\/doi.org\/10.1145\/76359.76371","journal-title":"J ACM"},{"issue":"7-8","key":"27_CR11","doi-asserted-by":"crossref","first-page":"615","DOI":"10.26421\/QIC16.7-8-4","volume":"16","author":"HC Cheng","year":"2016","unstructured":"Cheng HC, Hsieh MH, Yeh PC (2016) The learnability of unknown quantum measurements. Quantum Information & Computation 16(7-8):615\u2013656","journal-title":"Quantum Information & Computation"},{"key":"27_CR12","unstructured":"Chung KM, Lin HH (2018) Sample efficient algorithms for learning quantum channels in pac model and the approximate state discrimination problem. arXiv:1810.10938"},{"issue":"2-3","key":"27_CR13","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/BF00993408","volume":"18","author":"PW Goldberg","year":"1995","unstructured":"Goldberg PW, Jerrum MR (1995) Bounding the vapnik-chervonenkis dimension of concept classes parameterized by real numbers. Mach Learn 18(2-3):131\u2013148. https:\/\/doi.org\/10.1007\/BF00993408","journal-title":"Mach Learn"},{"key":"27_CR14","unstructured":"Hanneke S (2016) The optimal sample complexity of pac learning. J Mach Learn Res 17(1):1319\u20131333. http:\/\/dl.acm.org\/ft_gateway.cfm?id=2946683&type=pdf"},{"key":"27_CR15","volume-title":"The mathematical language of quantum theory: From uncertainty to entanglement","author":"T Heinosaari","year":"2013","unstructured":"Heinosaari T, Ziman M (2013) The mathematical language of quantum theory: From uncertainty to entanglement. Cambridge University Press, Cambridge"},{"issue":"1","key":"27_CR16","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1006\/jcss.1997.1477","volume":"54","author":"M Karpinski","year":"1997","unstructured":"Karpinski M, Macintyre A (1997) Polynomial bounds for vc dimension of sigmoidal and general pfaffian neural networks. J Comput Sys Sci 54(1):169\u2013176. https:\/\/doi.org\/10.1006\/jcss.1997.1477","journal-title":"J Comput Sys Sci"},{"key":"27_CR17","unstructured":"Kiani BT, Lloyd S, Maity R (2020) Learning unitaries by gradient descent. arXiv:2001.11897"},{"key":"27_CR18","doi-asserted-by":"publisher","unstructured":"Koiran P (1996) VC dimension in circuit complexity. In: Cai J Y, Homer S (eds) Proceedings, Eleventh annual ieee conference on computational complexity. https:\/\/doi.org\/10.1109\/CCC.1996.507671. IEEE Computer Society Press, Los Alamitos, pp 81\u201385","DOI":"10.1109\/CCC.1996.507671"},{"key":"27_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976667","volume-title":"Quantum computation and quantum information","author":"MA Nielsen","year":"2010","unstructured":"Nielsen MA, Chuang IL (2010) Quantum computation and quantum information. Cambridge University Press, Cambridge and New York"},{"key":"27_CR20","volume-title":"Convergence of stochastic processes. Springer Series in Statistics","author":"D Pollard","year":"1984","unstructured":"Pollard D (1984) Convergence of stochastic processes. Springer Series in Statistics. Springer, New York"},{"key":"27_CR21","unstructured":"Rocchetto A (2017) Stabiliser states are efficiently pac-learnable. Quantum Information and Computation, 18"},{"key":"27_CR22","doi-asserted-by":"publisher","unstructured":"Rocchetto A, Aaronson S, Severini S, Carvacho G, Poderini D, Agresti I, Bentivegna M, Sciarrino F (2019) Experimental learning of quantum states. Science Advances 5(3), https:\/\/doi.org\/10.1126\/sciadv.aau1946","DOI":"10.1126\/sciadv.aau1946"},{"issue":"5","key":"27_CR23","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1038\/s41567-018-0048-5","volume":"14","author":"G Torlai","year":"2018","unstructured":"Torlai G, Mazzola G, Carrasquilla J, Troyer M, Melko R, Carleo G (2018) Neural-network quantum state tomography. Nat Phy 14(5):447\u2013450 . https:\/\/doi.org\/10.1038\/s41567-018-0048-5, https:\/\/www.nature.com\/articles\/s41567-018-0048-5.pdf","journal-title":"Nat Phy"},{"issue":"11","key":"27_CR24","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"LG Valiant","year":"1984","unstructured":"Valiant LG (1984) A theory of the learnable. Commun ACM 27(11):1134\u20131142. https:\/\/doi.org\/10.1145\/1968.1972","journal-title":"Commun ACM"},{"issue":"2","key":"27_CR25","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"VN Vapnik","year":"1971","unstructured":"Vapnik VN, Chervonenkis AY (1971) On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications 16(2):264\u2013280. https:\/\/doi.org\/10.1137\/1116025","journal-title":"Theory of Probability & Its Applications"},{"issue":"1","key":"27_CR26","doi-asserted-by":"publisher","first-page":"167","DOI":"10.2307\/1994937","volume":"133","author":"HE Warren","year":"1968","unstructured":"Warren HE (1968) Lower bounds for approximation by nonlinear manifolds. Trans Am Math Soc 133(1):167. https:\/\/doi.org\/10.2307\/1994937","journal-title":"Trans Am Math Soc"}],"container-title":["Quantum Machine Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-020-00027-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s42484-020-00027-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-020-00027-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,13]],"date-time":"2021-04-13T00:51:15Z","timestamp":1618275075000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s42484-020-00027-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,6]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["27"],"URL":"https:\/\/doi.org\/10.1007\/s42484-020-00027-5","relation":{},"ISSN":["2524-4906","2524-4914"],"issn-type":[{"value":"2524-4906","type":"print"},{"value":"2524-4914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,6]]},"assertion":[{"value":"25 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"14"}}