{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,4]],"date-time":"2025-04-04T00:37:42Z","timestamp":1743727062329,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T00:00:00Z","timestamp":1627776000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T00:00:00Z","timestamp":1627776000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003696","name":"Electronics and Telecommunications Research Institute","doi-asserted-by":"publisher","award":["2018- 104","2018-104"],"award-info":[{"award-number":["2018- 104","2018-104"]}],"id":[{"id":"10.13039\/501100003696","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["2019R1A2C2005504","2019R1A2C2005504"],"award-info":[{"award-number":["2019R1A2C2005504","2019R1A2C2005504"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["2019R1A2C2005504","NRF-2019M3E4A1079666"],"award-info":[{"award-number":["2019R1A2C2005504","NRF-2019M3E4A1079666"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF-2019M3E4A1079666","NRF-2019M3E4A1079666"],"award-info":[{"award-number":["NRF-2019M3E4A1079666","NRF-2019M3E4A1079666"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NCN grants","award":["2015\/19\/B\/ST2\/01999","2017\/26\/E\/ST2\/01008"],"award-info":[{"award-number":["2015\/19\/B\/ST2\/01999","2017\/26\/E\/ST2\/01008"]}]},{"name":"FNP grant","award":["First Team\/2016-1\/5"],"award-info":[{"award-number":["First Team\/2016-1\/5"]}]},{"name":"KIAS Advanced Research Program","award":["CG014604"],"award-info":[{"award-number":["CG014604"]}]},{"name":"KIAS Individual Grant","award":["CG061003"],"award-info":[{"award-number":["CG061003"]}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["2021M3E4A1038213"],"award-info":[{"award-number":["2021M3E4A1038213"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003621","name":"Ministry of Science, ICT and Future Planning","doi-asserted-by":"publisher","award":["2020-0-00890"],"award-info":[{"award-number":["2020-0-00890"]}],"id":[{"id":"10.13039\/501100003621","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2021,8]]},"DOI":"10.1007\/s11128-021-03217-7","type":"journal-article","created":{"date-parts":[[2021,8,23]],"date-time":"2021-08-23T07:12:04Z","timestamp":1629702724000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Tangible reduction in learning sample complexity with large classical samples and small quantum system"],"prefix":"10.1007","volume":"20","author":[{"given":"Wooyeong","family":"Song","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1873-3945","authenticated-orcid":false,"given":"Marcin","family":"Wie\u015bniak","sequence":"additional","affiliation":[]},{"given":"Nana","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Marcin","family":"Paw\u0142owski","sequence":"additional","affiliation":[]},{"given":"Jinhyoung","family":"Lee","sequence":"additional","affiliation":[]},{"given":"Jaewan","family":"Kim","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9263-9394","authenticated-orcid":false,"given":"Jeongho","family":"Bang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,8,23]]},"reference":[{"issue":"2","key":"3217_CR1","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1137\/S0036144598347011","volume":"41","author":"PW Shor","year":"1999","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 302\u2013332 (1999)","journal-title":"SIAM Rev."},{"key":"3217_CR2","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1103\/PhysRevLett.79.325","volume":"79","author":"LK Grover","year":"1997","unstructured":"Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79, 325 (1997)","journal-title":"Phys. Rev. Lett."},{"key":"3217_CR3","doi-asserted-by":"publisher","first-page":"150502","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, 150502 (2009)","journal-title":"Phys. Rev. Lett."},{"key":"3217_CR4","doi-asserted-by":"publisher","first-page":"160501","DOI":"10.1103\/PhysRevLett.100.160501","volume":"100","author":"V Giovannetti","year":"2008","unstructured":"Giovannetti, V., Lloyd, S., Maccone, L.: Quantum random access memory. Phys. Rev. Lett. 100, 160501 (2008)","journal-title":"Phys. Rev. Lett."},{"key":"3217_CR5","doi-asserted-by":"publisher","first-page":"052310","DOI":"10.1103\/PhysRevA.78.052310","volume":"78","author":"V Giovannetti","year":"2008","unstructured":"Giovannetti, V., Lloyd, S., Maccone, L.: Architectures for a quantum random access memory. Phys. Rev. A 78, 052310 (2008)","journal-title":"Phys. Rev. A"},{"key":"3217_CR6","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1038\/nphys3272","volume":"11","author":"S Aaronson","year":"2015","unstructured":"Aaronson, S.: Read the find print. Nat. Phys. 11, 291 (2015)","journal-title":"Nat. Phys."},{"key":"3217_CR7","doi-asserted-by":"crossref","unstructured":"Arunachalam, S., Gheorghiu, V., Jochym-O\u2018Connor, T., Mosca, M., Srinivasan, P.V.: On the robustness of bucket brigade quantum RAM. New J. Phys. 17, 123010 (2015)","DOI":"10.1088\/1367-2630\/17\/12\/123010"},{"key":"3217_CR8","doi-asserted-by":"publisher","first-page":"20170551","DOI":"10.1098\/rspa.2017.0551","volume":"474","author":"C Ciliberto","year":"2018","unstructured":"Ciliberto, C., Herbster, M., Ialongo, A.D., Pontil, M., Rocchetto, A., Severini, S., Wossnig, L.: Quantum machine learning: a classical perspective. Proc. R. Soc. A 474, 20170551 (2018)","journal-title":"Proc. R. Soc. A"},{"key":"3217_CR9","doi-asserted-by":"publisher","first-page":"79","DOI":"10.22331\/q-2018-08-06-79","volume":"2","author":"J Preskill","year":"2018","unstructured":"Preskill, J.: Quantum Computing in the NISQ era and beyond. Quantum 2, 79 (2018)","journal-title":"Quantum"},{"key":"3217_CR10","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1038\/s41586-019-1666-5","volume":"574","author":"F Arute","year":"2019","unstructured":"Arute, F., et al.: Quantum supremacy using a programmable superconducting processor. Nature 574, 505 (2019)","journal-title":"Nature"},{"key":"3217_CR11","doi-asserted-by":"crossref","unstructured":"Peruzzo, A., McClean, J.R., Shadbolt, P., Yung, M.H., Zhou, X.Q., Love, P.J., Aspuru-Guzik, A., O\u2018brien, J.L.: A variational eigenvalue solver on a photonic quantum processor. Nat. Commun. 5, 4213 (2014)","DOI":"10.1038\/ncomms5213"},{"key":"3217_CR12","doi-asserted-by":"publisher","first-page":"023023","DOI":"10.1088\/1367-2630\/18\/2\/023023","volume":"18","author":"JR McClean","year":"2016","unstructured":"McClean, J.R., Romerom, J., Babbush, R., Aspuru-Guzik, A.: The theory of variational hybrid quantum-classical algorithms. New J. Phys. 18, 023023 (2016)","journal-title":"New J. Phys."},{"key":"3217_CR13","doi-asserted-by":"publisher","first-page":"014001","DOI":"10.1088\/2058-9565\/aada1f","volume":"4","author":"A Khoshaman","year":"2018","unstructured":"Khoshaman, A., Vinci, W., Denis, B., Andriyash, E., Amin, M.H.: Quantum variational autoencoder. Quant. Sci. Technol. 4, 014001 (2018)","journal-title":"Quant. Sci. Technol."},{"key":"3217_CR14","doi-asserted-by":"crossref","unstructured":"Zhu, D., et al.: Training of quantum circuits on a hybrid quantum computer. Sci. Adv. 5(10),(2019)","DOI":"10.1126\/sciadv.aaw9918"},{"key":"3217_CR15","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1038\/s41586-019-0980-2","volume":"567","author":"V Havl\u00ed\u010dek","year":"2019","unstructured":"Havl\u00ed\u010dek, V., C\u00f3rcoles, A.D., Temme, K., Harrow, A.W., Kandala, A., Chow, J.M., Gambetta, J.M.: Supervised learning with quantum-enhanced feature spaces. Nature 567, 209 (2019)","journal-title":"Nature"},{"key":"3217_CR16","doi-asserted-by":"publisher","first-page":"103014","DOI":"10.1088\/1367-2630\/16\/10\/103014","volume":"16","author":"S Yoo","year":"2014","unstructured":"Yoo, S., Bang, J., Lee, C., Lee, J.: A quantum speedup in machine learning: finding a N-bit Boolean function for a classification. New J. Phys. 16, 103014 (2014)","journal-title":"New J. Phys."},{"key":"3217_CR17","doi-asserted-by":"publisher","first-page":"012313","DOI":"10.1103\/PhysRevA.99.012313","volume":"99","author":"JS Lee","year":"2019","unstructured":"Lee, J.S., Bang, J., Hong, S., Lee, C., Seol, K.H., Lee, J., Lee, K.G.: Experimental demonstration of quantum learning speedup with classical input data. Phys. Rev. A 99, 012313 (2019)","journal-title":"Phys. Rev. A"},{"key":"3217_CR18","doi-asserted-by":"publisher","first-page":"012326","DOI":"10.1103\/PhysRevA.99.012326","volume":"99","author":"J Bang","year":"2019","unstructured":"Bang, J., Dutta, A., Lee, S.W., Kim, J.: Optimal usage of quantum random access memory in quantum machine learning. Phys. Rev. A 99, 012326 (2019)","journal-title":"Phys. Rev. A"},{"key":"3217_CR19","doi-asserted-by":"publisher","first-page":"250501","DOI":"10.1103\/PhysRevLett.121.250501","volume":"121","author":"V Dunjko","year":"2018","unstructured":"Dunjko, V., Ge, Y., Cirac, J.I.: Computational speedups using small quantum devices. Phys. Rev. Lett. 121, 250501 (2018)","journal-title":"Phys. Rev. Lett."},{"key":"3217_CR20","unstructured":"Harrow, A.W.: Small quantum computers and large classical data sets. Preprint arXiv:2004.00026 (2020)"},{"key":"3217_CR21","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/s00224-006-1313-z","volume":"40","author":"H Buhrman","year":"2007","unstructured":"Buhrman, H., Newman, I., Rohrig, H., de Wolf, R.: Robust polynomials and quantum algorithms. Theory Comput. Syst. 40, 379 (2007)","journal-title":"Theory Comput. Syst."},{"key":"3217_CR22","doi-asserted-by":"publisher","first-page":"012327","DOI":"10.1103\/PhysRevA.92.012327","volume":"92","author":"AW Cross","year":"2015","unstructured":"Cross, A.W., Smith, G., Smolin, J.A.: Quantum learning robust against noise. Phys. Rev. A 92, 012327 (2015)","journal-title":"Phys. Rev. A"},{"key":"3217_CR23","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"LG Valiant","year":"1984","unstructured":"Valiant, L.G.: A theory of the learnable. Commun. ACM 27, 1134 (1984)","journal-title":"Commun. ACM"},{"key":"3217_CR24","unstructured":"Langley, P.: Elements of Machine Learning. Morgan Kaufmann (1995)"},{"key":"3217_CR25","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Iwama, K., Kawachi, A., Masuda, H., Putra, R.H., Yamashita, S.: Quantum identification of Boolean oracles. In: Annual Symposium on Theoretical Aspects of Computer Science, Springer, pp. 105\u2013116 (2004)","DOI":"10.1007\/978-3-540-24749-4_10"},{"key":"3217_CR26","unstructured":"Childs, A.M., Kothari, R., Ozols, M., Roetteler, M.: Easy and hard functions for the Boolean hidden shift problem. In: 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013) (Dagstuhl, Germany: Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik) vol.\u00a022 of Leibniz International Proceedings in Informatics (LIPIcs) pp. 50\u201379 (2013)"},{"key":"3217_CR27","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. ACM SIGACT News 48, 41 (2017)","journal-title":"ACM SIGACT News"},{"key":"3217_CR28","doi-asserted-by":"publisher","first-page":"2317","DOI":"10.1109\/TCAD.2006.871622","volume":"25","author":"P Gupta","year":"2006","unstructured":"Gupta, P., Agrawal, A., Jha, N.K.: An algorithm for synthesis of reversible logic circuits. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 25, 2317 (2006)","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"issue":"4","key":"3217_CR29","first-page":"319","volume":"2","author":"D Angluin","year":"1988","unstructured":"Angluin, D., Laird, P.: Queries and concept learning. Mach. Learn. 2(4), 319 (1988)","journal-title":"Mach. Learn."},{"issue":"1","key":"3217_CR30","first-page":"7","volume":"14","author":"D Angluin","year":"1994","unstructured":"Angluin, D., Slonim, D.K.: Randomly fallible teachers: learning monotone DNF with an incomplete membership oracle. Mach. Learn. 14(1), 7 (1994)","journal-title":"Mach. Learn."},{"key":"3217_CR31","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, 1136 (1998)","journal-title":"SIAM J. Comput."},{"key":"3217_CR32","doi-asserted-by":"crossref","unstructured":"Toffoli, T.: Reversible computing. International Colloquium on Automata, Languages, and Programming. Springer, pp. 632\u2013644 (1980)","DOI":"10.1007\/3-540-10003-2_104"},{"key":"3217_CR33","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1080\/00207210412331272643","volume":"91","author":"A Younes","year":"2004","unstructured":"Younes, A., Miller, J.F.: Representation of Boolean quantum circuits as Reed-Muller expansions. Int. J. Electron. 91, 431 (2004)","journal-title":"Int. J. Electron."},{"key":"3217_CR34","unstructured":"Van\u00a0Dam, W.: Quantum oracle interrogation: Getting all information for almost half the price. In: Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280) IEEE pp. 362\u2013367 (1998)"},{"key":"3217_CR35","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1038\/nature18648","volume":"536","author":"S Debnath","year":"2016","unstructured":"Debnath, S., Linke, N.M., Figgatt, C., Landsman, K.A., Wright, K., Monroe, C.: Demonstration of a small programmable quantum computer with atomic qubits. Nature 536, 63 (2016)","journal-title":"Nature"},{"key":"3217_CR36","doi-asserted-by":"publisher","first-page":"062114","DOI":"10.1103\/PhysRevA.95.062114","volume":"95","author":"H Eleuch","year":"2017","unstructured":"Eleuch, H., Hilke, M., MacKenzie, R.: Probing Anderson localization using the dynamics of a qubit. Phys. Rev. A 95, 062114 (2017)","journal-title":"Phys. Rev. A"},{"key":"3217_CR37","first-page":"1319","volume":"17","author":"S Hanneke","year":"2016","unstructured":"Hanneke, S.: The optimal sample complexity of PAC learning. J. Mach. Learn. Res. 17, 1319 (2016)","journal-title":"J. Mach. Learn. Res."}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03217-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-021-03217-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03217-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,3]],"date-time":"2021-09-03T18:50:37Z","timestamp":1630695037000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-021-03217-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8]]},"references-count":37,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["3217"],"URL":"https:\/\/doi.org\/10.1007\/s11128-021-03217-7","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"type":"print","value":"1570-0755"},{"type":"electronic","value":"1573-1332"}],"subject":[],"published":{"date-parts":[[2021,8]]},"assertion":[{"value":"1 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 August 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"275"}}