{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:27:18Z","timestamp":1740137238270,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T00:00:00Z","timestamp":1728259200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T00:00:00Z","timestamp":1728259200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2212327"],"award-info":[{"award-number":["2212327"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"DOI":"10.1007\/s11128-024-04555-y","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T10:02:07Z","timestamp":1728295327000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fat shattering, joint measurability, and PAC learnability of POVM hypothesis classes"],"prefix":"10.1007","volume":"23","author":[{"given":"Abram","family":"Magner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arun","family":"Padakandla","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"4555_CR1","doi-asserted-by":"publisher","unstructured":"Heidari, M., Padakandla, A., Szpankowski, W.: A theoretical framework for learning from quantum data. In: 2021 IEEE international symposium on information theory (ISIT), pp 1469\u20131474 (2021). https:\/\/doi.org\/10.1109\/ISIT45174.2021.9517721","DOI":"10.1109\/ISIT45174.2021.9517721"},{"key":"4555_CR2","doi-asserted-by":"publisher","unstructured":"Heidari, M., Grama, A., Szpankowski, W.: Toward physically realizable quantum neural networks. arXiv (2022). https:\/\/doi.org\/10.48550\/ARXIV.2203.12092","DOI":"10.48550\/ARXIV.2203.12092"},{"key":"4555_CR3","doi-asserted-by":"publisher","first-page":"981","DOI":"10.22331\/q-2023-04-17-981","volume":"7","author":"Y Wu","year":"2023","unstructured":"Wu, Y., Wu, B., Wang, J., Yuan, X.: Quantum phase recognition via quantum kernel methods. Quantum 7, 981 (2023)","journal-title":"Quantum"},{"key":"4555_CR4","unstructured":"Padakandla, A., Magner, A.: Pac learning of quantum measurement classes : sample complexity bounds and universal consistency. In: Camps-Valls, G., Ruiz, F.J.R., Valera, I. (eds.) Proceedings of the 25th international conference on artificial intelligence and statistics. Proceedings of machine learning research, vol. 151, pp 11305\u201311319. PMLR, Virtual (2022). https:\/\/proceedings.mlr.press\/v151\/padakandla22a.html"},{"issue":"1","key":"4555_CR5","first-page":"2879","volume":"19","author":"S Arunachalam","year":"2018","unstructured":"Arunachalam, S., De Wolf, R.: Optimal quantum sample complexity of learning algorithms. J. Mach. Learn. Res. 19(1), 2879\u20132878 (2018)","journal-title":"J. Mach. Learn. Res."},{"key":"4555_CR6","volume-title":"Quantum Information Theory","author":"M Wilde","year":"2017","unstructured":"Wilde, M.: Quantum Information Theory. Cambridge University Press, Cambridge, UK (2017)"},{"key":"4555_CR7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019","volume-title":"Understanding machine learning - from theory to algorithms","author":"S Shalev-Shwartz","year":"2014","unstructured":"Shalev-Shwartz, S., Ben-David, S.: Understanding machine learning - from theory to algorithms. Cambridge University Press, Cambridge, UK (2014)"},{"issue":"2","key":"4555_CR8","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/3106700.3106710","volume":"48","author":"S Arunachalam","year":"2017","unstructured":"Arunachalam, S., De Wolf, R.: Guest column: a survey of quantum learning theory. SIGACT News 48(2), 41\u201367 (2017). https:\/\/doi.org\/10.1145\/3106700.3106710","journal-title":"SIGACT News"},{"key":"4555_CR9","unstructured":"Arunachalam, S., Grilo, A.B., Yuen, H.: Quantum statistical query learning. arXiv preprint arXiv:2002.08240 (2020) arXiv:2002.08240"},{"key":"4555_CR10","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-021-01232-0","author":"A Anshu","year":"2021","unstructured":"Anshu, A., Arunachalam, S., Kuwahara, T., Soleimanifar, M.: Sample-efficient learning of interacting quantum systems. Nature Physics (2021). https:\/\/doi.org\/10.1038\/s41567-021-01232-0","journal-title":"Nature Physics"},{"key":"4555_CR11","doi-asserted-by":"publisher","unstructured":"O\u2019Donnell, R., Wright, J.: Efficient quantum tomography. In: Proceedings of the forty-eighth annual ACM symposium on theory of computing. STOC \u201916, pp 899\u2013912. Association for Computing Machinery, New York, NY, USA (2016). https:\/\/doi.org\/10.1145\/2897518.2897544","DOI":"10.1145\/2897518.2897544"},{"key":"4555_CR12","doi-asserted-by":"publisher","unstructured":"O\u2019Donnell, R., Wright, J.: Efficient quantum tomography ii. In: Proceedings of the 49th annual ACM SIGACT symposium on theory of computing. STOC 2017, pp 962\u2013974. Association for Computing Machinery, New York, NY, USA (2017). https:\/\/doi.org\/10.1145\/3055399.3055454","DOI":"10.1145\/3055399.3055454"},{"key":"4555_CR13","doi-asserted-by":"publisher","unstructured":"Haah, J., Harrow, A.W., Ji, Z., Wu, X., Yu, N.: Sample-optimal tomography of quantum states. In: Proceedings of the forty-eighth annual acm symposium on theory of computing. STOC \u201916, pp 913\u2013925. Association for Computing Machinery, New York, NY, USA (2016). https:\/\/doi.org\/10.1145\/2897518.2897585","DOI":"10.1145\/2897518.2897585"},{"key":"4555_CR14","doi-asserted-by":"publisher","unstructured":"Aaronson, S.: The learnability of quantum states. In: Proceedings of The royal society a mathematical physical and engineering sciences 463 (2006). https:\/\/doi.org\/10.1098\/rspa.2007.0113","DOI":"10.1098\/rspa.2007.0113"},{"key":"4555_CR15","doi-asserted-by":"publisher","unstructured":"Rehacek, J., Paris, M.: Quantum state estimation. Lecture notes in physics. Springer, Berlin (2004). https:\/\/doi.org\/10.1007\/b98673 . https:\/\/cds.cern.ch\/record\/1391369","DOI":"10.1007\/b98673"},{"key":"4555_CR16","doi-asserted-by":"publisher","unstructured":"Waseem, M.H., Faizan-e-Ilahi, Anwar, M.S.: Quantum state tomography. In: Quantum mechanics in the single photon laboratory. 2053-2563, pp 6\u20131620. IOP Publishing, Bristol, UK (2020). https:\/\/doi.org\/10.1088\/978-0-7503-3063-3ch6","DOI":"10.1088\/978-0-7503-3063-3ch6"},{"key":"4555_CR17","doi-asserted-by":"crossref","unstructured":"Altepeter, J., James, D., Kwiat, P.: Qubit quantum state tomography. lecture notes in physics 649, 113\u2013145 (2004)","DOI":"10.1007\/978-3-540-44481-7_4"},{"key":"4555_CR18","doi-asserted-by":"publisher","unstructured":"Aaronson, S.: Shadow tomography of quantum states. In: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing. STOC 2018, pp 325\u2013338. Association for Computing Machinery, New York, NY, USA (2018). https:\/\/doi.org\/10.1145\/3188745.3188802","DOI":"10.1145\/3188745.3188802"},{"key":"4555_CR19","unstructured":"Aaronson, S., Chen, X., Hazan, E., Kale, S.: Online learning of quantum states. In: Proceedings of the 32nd international conference on neural information processing systems. NIPS\u201918, pp 8976\u20138986. Curran Associates Inc., Red Hook, NY, USA (2018)"},{"issue":"3","key":"4555_CR20","doi-asserted-by":"publisher","first-page":"1136","DOI":"10.1137\/S0097539795293123","volume":"28","author":"NH Bshouty","year":"1998","unstructured":"Bshouty, N.H., Jackson, J.C.: Learning dnf over the uniform distribution using a quantum example oracle. SIAM J. Comput. 28(3), 1136\u20131153 (1998)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"4555_CR21","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s11128-005-0001-2","volume":"4","author":"A Atici","year":"2005","unstructured":"Atici, A., Servedio, R.A.: Improved bounds on quantum learning algorithms. Quantum Inf. Process. 4(5), 355\u2013386 (2005). https:\/\/doi.org\/10.1007\/s11128-005-0001-2","journal-title":"Quantum Inf. Process."},{"key":"4555_CR22","unstructured":"Roget, M., Molfetta, G.D., Kadri, H.: Quantum perceptron revisited: computational-statistical tradeoffs. In: The 38th conference on uncertainty in artificial intelligence (2022). https:\/\/openreview.net\/forum?id=BuOcoU8jqxq"},{"issue":"1","key":"4555_CR23","doi-asserted-by":"publisher","first-page":"4919","DOI":"10.1038\/s41467-022-32550-3","volume":"13","author":"MC Caro","year":"2022","unstructured":"Caro, M.C., Huang, H.-Y., Cerezo, M., Sharma, K., Sornborger, A., Cincio, L., Coles, P.J.: Generalization in quantum machine learning from few training data. Nat. Commun. 13(1), 4919 (2022). https:\/\/doi.org\/10.1038\/s41467-022-32550-3","journal-title":"Nat. Commun."},{"key":"4555_CR24","doi-asserted-by":"crossref","unstructured":"Rosati, M.: A learning theory for quantum photonic processors and beyond (2023)","DOI":"10.22331\/q-2024-08-08-1433"},{"key":"4555_CR25","doi-asserted-by":"crossref","unstructured":"Fanizza, M., Quek, Y., Rosati, M.: Learning quantum processes without input control (2024)","DOI":"10.1103\/PRXQuantum.5.020367"},{"key":"4555_CR26","unstructured":"Caro, M., Gur, T., Rouz\u00e9, C., Stilck Fran\u00e7a, D., Subramanian, S.: Information-theoretic generalization bounds for learning from quantum data (2023)"},{"issue":"7\u20138","key":"4555_CR27","first-page":"615","volume":"16","author":"H-C Cheng","year":"2016","unstructured":"Cheng, H.-C., Hsieh, M.-H., Yeh, P.-C.: The learnability of unknown quantum measurements. Quantum Inf. Comput. 16(7\u20138), 615\u2013656 (2016)","journal-title":"Quantum Inf. Comput."},{"issue":"2\u20133","key":"4555_CR28","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/bf00993468","volume":"17","author":"MJ Kearns","year":"1994","unstructured":"Kearns, M.J., Schapire, R.E., Sellie, L.M.: Toward efficient agnostic learning. Mach. Learn. 17(2\u20133), 115\u2013141 (1994). https:\/\/doi.org\/10.1007\/bf00993468","journal-title":"Mach. Learn."},{"key":"4555_CR29","doi-asserted-by":"publisher","unstructured":"Kearns, M.J., Schapire, R.E.: Efficient distribution-free learning of probabilistic concepts. In: Proceedings of the 31st annual symposium on foundations of computer science. SFCS \u201990, pp 382\u20133911. IEEE Computer Society, USA (1990). https:\/\/doi.org\/10.1109\/FSCS.1990.89557","DOI":"10.1109\/FSCS.1990.89557"},{"key":"4555_CR30","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.100.032113","author":"J Jae","year":"2019","unstructured":"Jae, J., Baek, K., Ryu, J., Lee, J.: Necessary and sufficient condition for joint measurability. Phys. Rev. A (2019). https:\/\/doi.org\/10.1103\/physreva.100.032113","journal-title":"Phys. Rev. A"},{"key":"4555_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21852-6","volume-title":"Measures of Complexity: Festschrift for Alexey Chervonenkis","author":"V Vovk","year":"2015","unstructured":"Vovk, V., Papadopoulos, H., Gammerman, A.: Measures of Complexity: Festschrift for Alexey Chervonenkis. Springer, New York, NY (2015)"},{"key":"4555_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1162\/153244302760185225","volume":"2","author":"S Mendelson","year":"2002","unstructured":"Mendelson, S.: On the size of convex hulls of small sets. J. Mach. Learn. Res. 2, 1\u201318 (2002). https:\/\/doi.org\/10.1162\/153244302760185225","journal-title":"J. Mach. Learn. Res."},{"key":"4555_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41567-019-0648-8","volume":"15","author":"I Cong","year":"2019","unstructured":"Cong, I., Choi, S., Lukin, M.: Quantum convolutional neural networks. Nat. Phys. 15, 1\u20136 (2019). https:\/\/doi.org\/10.1038\/s41567-019-0648-8","journal-title":"Nat. Phys."},{"key":"4555_CR34","doi-asserted-by":"publisher","unstructured":"Szarek, S.J.: Metric entropy of homogeneous spaces. arXiv (1997). https:\/\/doi.org\/10.48550\/ARXIV.MATH\/9701213. https:\/\/arxiv.org\/abs\/math\/9701213","DOI":"10.48550\/ARXIV.MATH\/9701213"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-024-04555-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-024-04555-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-024-04555-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,2]],"date-time":"2024-11-02T10:14:12Z","timestamp":1730542452000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-024-04555-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":34,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2024,10]]}},"alternative-id":["4555"],"URL":"https:\/\/doi.org\/10.1007\/s11128-024-04555-y","relation":{},"ISSN":["1573-1332"],"issn-type":[{"type":"electronic","value":"1573-1332"}],"subject":[],"published":{"date-parts":[[2024,10,7]]},"assertion":[{"value":"8 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"337"}}