{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:27:24Z","timestamp":1740137244263,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2022,7,26]],"date-time":"2022-07-26T00:00:00Z","timestamp":1658793600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,7,26]],"date-time":"2022-07-26T00:00:00Z","timestamp":1658793600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA8750-16-2-0004"],"award-info":[{"award-number":["FA8750-16-2-0004"]}],"id":[{"id":"10.13039\/100000185","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-022-03607-5","type":"journal-article","created":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T11:51:56Z","timestamp":1659095516000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Quantum learning of concentrated Boolean functions"],"prefix":"10.1007","volume":"21","author":[{"given":"Krishna","family":"Palem","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5395-3401","authenticated-orcid":false,"given":"Duc Hung","family":"Pham","sequence":"additional","affiliation":[]},{"given":"M. V. Panduranga","family":"Rao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,26]]},"reference":[{"key":"3607_CR1","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1038\/nphys3272","volume":"11","author":"S Aaronson","year":"2015","unstructured":"Aaronson, S.: Read the fine print. Nat. Phys. 11, 291\u2013293 (2015). https:\/\/doi.org\/10.1038\/nphys3272","journal-title":"Nat. Phys."},{"key":"3607_CR2","doi-asserted-by":"crossref","unstructured":"Adcock, M., Cleve, R.: A quantum Goldreich-Levin theorem with cryptographic applications. In: Alt, H., Ferreira, A. (eds.) STACS 2002, pp. 323\u2013334. Springer, Berlin Heidelberg (2002)","DOI":"10.1007\/3-540-45841-7_26"},{"issue":"5","key":"3607_CR3","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/j.ipl.2005.01.016","volume":"97","author":"M Adcock","year":"2006","unstructured":"Adcock, M., Cleve, R., Iwama, K., Putra, R., Yamashita, S.: Quantum lower bounds for the Goldreich-Levin problem. Inf. Process. Lett. 97(5), 208\u2013211 (2006)","journal-title":"Inf. Process. Lett."},{"key":"3607_CR4","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/11766247_37","volume-title":"Advances in artificial intelligence","author":"E A\u00efmeur","year":"2006","unstructured":"A\u00efmeur, E., Brassard, G., Gambs, S.: Machine learning in a quantum world. In: Lamontagne, L., Marchand, M. (eds.) Advances in artificial intelligence, pp. 431\u2013442. Springer, Berlin (2006)"},{"issue":"2","key":"3607_CR5","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s10994-012-5316-5","volume":"90","author":"E A\u00efmeur","year":"2013","unstructured":"A\u00efmeur, E., Brassard, G., Gambs, S.: Quantum speed-up for unsupervised learning. Mach. Learn. 90(2), 261\u2013287 (2013). https:\/\/doi.org\/10.1007\/s10994-012-5316-5","journal-title":"Mach. Learn."},{"issue":"4","key":"3607_CR6","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/BF00116828","volume":"2","author":"D Angluin","year":"1987","unstructured":"Angluin, D.: Queries and concept learning. Mach. Learn. 2(4), 319\u2013342 (1987). https:\/\/doi.org\/10.1007\/BF00116828","journal-title":"Mach. Learn."},{"key":"3607_CR7","unstructured":"Arunachalam, S., Chakraborty, S., Lee, T., Wolf, R.: Two new results about quantum exact learning. In: ICALP (2019)"},{"issue":"2","key":"3607_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":"3607_CR9","unstructured":"Arunachalam, S., de\u00a0Wolf, R.: Optimal quantum sample complexity of learning algorithms. J. Mach. Learn. Res. 19, 71:1\u201371:36 (2018). http:\/\/jmlr.org\/papers\/v19\/18-195.html"},{"key":"3607_CR10","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s11128-005-0001-2","volume":"4","author":"A Atici","year":"2004","unstructured":"Atici, A., Servedio, R.: Improved bounds on quantum learning algorithms. Quant. Inf. Process. 4, 355\u2013386 (2004). https:\/\/doi.org\/10.1007\/s11128-005-0001-2","journal-title":"Quant. Inf. Process."},{"key":"3607_CR11","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s11128-007-0061-6","volume":"6","author":"A At\u0131c\u0131","year":"2007","unstructured":"At\u0131c\u0131, A., Servedio, R.: Quantum algorithms for learning and testing juntas. Quant. Inf. Process. 6, 323\u2013348 (2007). https:\/\/doi.org\/10.1007\/s11128-007-0061-6","journal-title":"Quant. Inf. Process."},{"issue":"7671","key":"3607_CR12","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1038\/nature23474","volume":"549","author":"J Biamonte","year":"2017","unstructured":"Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., Lloyd, S.: Quantum machine learning. Nature 549(7671), 195\u2013202 (2017). https:\/\/doi.org\/10.1038\/nature23474","journal-title":"Nature"},{"issue":"4","key":"3607_CR13","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.: Learnability and the vapnik-chervonenkis dimension. J. ACM 36(4), 929\u2013965 (1989). https:\/\/doi.org\/10.1145\/76359.76371","journal-title":"J. ACM"},{"key":"3607_CR14","doi-asserted-by":"publisher","first-page":"1136","DOI":"10.1137\/S0097539795293123","volume":"28","author":"N Bshouty","year":"1999","unstructured":"Bshouty, N., Jackson, J.: Learning DNF over the uniform distribution using a quantum example oracle. SIAM J. Comput. 28, 1136\u20131153 (1999). https:\/\/doi.org\/10.1137\/S0097539795293123","journal-title":"SIAM J. Comput."},{"key":"3607_CR15","doi-asserted-by":"publisher","unstructured":"Bshouty, N.H., Cleve, R., Gavald\u00e0, R., Kannan, S., Tamon, C.: Oracles and queries that are sufficient for exact learning. J. Comput. Syst. Sci. 52(3), 421\u2013433 (1996). https:\/\/doi.org\/10.1006\/jcss.1996.0032 . https:\/\/www.sciencedirect.com\/science\/article\/pii\/S002200009690032X","DOI":"10.1006\/jcss.1996.0032"},{"issue":"3","key":"3607_CR16","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). https:\/\/doi.org\/10.1137\/S0097539795293123","journal-title":"SIAM J. Comput."},{"key":"3607_CR17","unstructured":"Chia, N.H., Lin, H.H., Wang, C.: Quantum-inspired sublinear classical algorithms for solving low-rank linear systems (2018)"},{"issue":"13","key":"3607_CR18","doi-asserted-by":"publisher","first-page":"130501","DOI":"10.1103\/physrevlett.117.130501","volume":"117","author":"V Dunjko","year":"2016","unstructured":"Dunjko, V., Taylor, J.M., Briegel, H.J.: Quantum-enhanced machine learning. Phys. Rev. Lett. 117(13), 130501 (2016). https:\/\/doi.org\/10.1103\/physrevlett.117.130501","journal-title":"Phys. Rev. Lett."},{"key":"3607_CR19","unstructured":"Gily\u00e9n, A., Lloyd, S., Tang, E.: Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension. ArXiv arXiv:1811.04909 (2018)"},{"key":"3607_CR20","doi-asserted-by":"publisher","unstructured":"Goldreich, O., Levin, L.: A hard-core predicate for all one-way functions. pp. 25\u201332 (1989). https:\/\/doi.org\/10.1145\/73007.73010","DOI":"10.1145\/73007.73010"},{"key":"3607_CR21","doi-asserted-by":"publisher","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC \u201996, p. 212-219. Association for Computing Machinery, New York, NY, USA (1996). https:\/\/doi.org\/10.1145\/237814.237866","DOI":"10.1145\/237814.237866"},{"issue":"15","key":"3607_CR22","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502","volume":"103","author":"AW Harrow","year":"2009","unstructured":"Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103(15), 150502 (2009)","journal-title":"Phys. Rev. Lett."},{"key":"3607_CR23","doi-asserted-by":"crossref","unstructured":"Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Nearly optimal sparse Fourier transform (2012)","DOI":"10.1145\/2213977.2214029"},{"key":"3607_CR24","doi-asserted-by":"crossref","unstructured":"Haviv, I., Regev, O.: The list-decoding size of Fourier-sparse Boolean functions (2015)","DOI":"10.1145\/2898439"},{"key":"3607_CR25","unstructured":"Indyk, P., Kapralov, M.: Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time (2014)"},{"issue":"6","key":"3607_CR26","doi-asserted-by":"publisher","first-page":"1331","DOI":"10.1137\/0222080","volume":"22","author":"E Kushilevitz","year":"1993","unstructured":"Kushilevitz, E., Mansour, Y.: Learning decision trees using the Fourier spectrum. SIAM J. Comput. 22(6), 1331\u20131348 (1993). https:\/\/doi.org\/10.1137\/0222080","journal-title":"SIAM J. Comput."},{"issue":"9","key":"3607_CR27","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1038\/nphys3029","volume":"10","author":"S Lloyd","year":"2014","unstructured":"Lloyd, S., Mohseni, M., Rebentrost, P.: Quantum principal component analysis. Nat. Phys. 10(9), 631\u2013633 (2014). https:\/\/doi.org\/10.1038\/nphys3029","journal-title":"Nat. Phys."},{"key":"3607_CR28","doi-asserted-by":"crossref","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information: 10th Anniversary Edition, 10th edn. Cambridge University Press, USA (2011)","DOI":"10.1017\/CBO9780511976667"},{"key":"3607_CR29","unstructured":"O\u2019Donnell, R.: Analysis of Boolean Functions. Cambridge University Press, USA (2014)"},{"issue":"13","key":"3607_CR30","doi-asserted-by":"publisher","first-page":"130503","DOI":"10.1103\/physrevlett.113.130503","volume":"113","author":"P Rebentrost","year":"2014","unstructured":"Rebentrost, P., Mohseni, M., Lloyd, S.: Quantum support vector machine for big data classification. Phys. Rev. Lett. 113(13), 130503 (2014). https:\/\/doi.org\/10.1103\/physrevlett.113.130503","journal-title":"Phys. Rev. Lett."},{"key":"3607_CR31","unstructured":"Roh, Y., Heo, G., Whang, S.E.: A survey on data collection for machine learning: a big data \u2013 ai integration perspective (2019)"},{"key":"3607_CR32","doi-asserted-by":"crossref","unstructured":"Shalev-Shwartz, S., Ben-David, S.: Understanding machine learning: From theory to algorithms. Cambridge University Press (2014)","DOI":"10.1017\/CBO9781107298019"},{"issue":"5","key":"3607_CR33","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"PW Shor","year":"1997","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484\u20131509 (1997). https:\/\/doi.org\/10.1137\/S0097539795293172","journal-title":"SIAM J. Comput."},{"key":"3607_CR34","unstructured":"Tang, E.: Quantum-inspired classical algorithms for principal component analysis and supervised clustering (2018)"},{"key":"3607_CR35","doi-asserted-by":"publisher","unstructured":"Tang, E.: A quantum-inspired classical algorithm for recommendation systems. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, p. 217-228. Association for Computing Machinery, New York, NY, USA (2019). https:\/\/doi.org\/10.1145\/3313276.3316310","DOI":"10.1145\/3313276.3316310"},{"key":"3607_CR36","doi-asserted-by":"publisher","unstructured":"Valiant, L.G.: A theory of the learnable. In: Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, STOC \u201984, p. 436-445. Association for Computing Machinery, New York, NY, USA (1984). https:\/\/doi.org\/10.1145\/800057.808710","DOI":"10.1145\/800057.808710"},{"key":"3607_CR37","unstructured":"Whalen, J., Wang, Y.: Hottest job in china\u2019s hinterlands: Teaching ai to tell a truck from a turtle. Washingtonpost (2019). https:\/\/www.washingtonpost.com\/business\/2019\/09\/26\/hottest-job-chinas-hinterlands-teaching-ai-tell-truck-turtle\/"},{"key":"3607_CR38","doi-asserted-by":"crossref","unstructured":"Wiebe, N., Kapoor, A., Svore, K.: Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning (2014)","DOI":"10.26421\/QIC15.3-4-7"},{"key":"3607_CR39","unstructured":"Wiebe, N., Kapoor, A., Svore, K.M.: Quantum deep learning (2015)"},{"key":"3607_CR40","unstructured":"Wiebe, N., Kapoor, A., Svore, K.M.: Quantum perceptron models (2016)"},{"key":"3607_CR41","doi-asserted-by":"publisher","unstructured":"Zhang, C.: An improved lower bound on query complexity for quantum pac learning. Inf. Process. Lett. 111(1), 40\u201345 (2010) https:\/\/doi.org\/10.1016\/j.ipl.2010.10.007. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0020019010003133","DOI":"10.1016\/j.ipl.2010.10.007"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-022-03607-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-022-03607-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-022-03607-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,6]],"date-time":"2022-08-06T20:15:17Z","timestamp":1659816917000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-022-03607-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,26]]},"references-count":41,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2022,7]]}},"alternative-id":["3607"],"URL":"https:\/\/doi.org\/10.1007\/s11128-022-03607-5","relation":{},"ISSN":["1573-1332"],"issn-type":[{"type":"electronic","value":"1573-1332"}],"subject":[],"published":{"date-parts":[[2022,7,26]]},"assertion":[{"value":"12 August 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 July 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"256"}}