{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T23:42:12Z","timestamp":1740181332363,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T00:00:00Z","timestamp":1619395200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T00:00:00Z","timestamp":1619395200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA2386-15-1-4082"],"award-info":[{"award-number":["FA2386-15-1-4082"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001381","name":"National Research Foundation Singapore","doi-asserted-by":"publisher","award":["NRFF2013-01"],"award-info":[{"award-number":["NRFF2013-01"]}],"id":[{"id":"10.13039\/501100001381","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Mach. Intell."],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Machine learning has recently emerged as a fruitful area for finding potential quantum computational advantage. Many of the quantum-enhanced machine learning algorithms critically hinge upon the ability to efficiently produce states proportional to high-dimensional data points stored in a quantum accessible memory. Even given query access to exponentially many entries stored in a database, the construction of which is considered a one-off overhead, it has been argued that the cost of preparing such amplitude-encoded states may offset any exponential quantum advantage. Here we prove using smoothed analysis that if the data analysis algorithm is robust against small entry-wise input perturbation, state preparation can always be achieved with constant queries. This criterion is typically satisfied in realistic machine learning applications, where input data is subjective to moderate noise. Our results are equally applicable to the recent seminal progress in quantum-inspired algorithms, where specially constructed databases suffice for polylogarithmic classical algorithm in low-rank cases. The consequence of our finding is that for the purpose of practical machine learning, polylogarithmic processing time is possible under a general and flexible input model with quantum algorithms or quantum-inspired classical algorithms in the low-rank cases.<\/jats:p>","DOI":"10.1007\/s42484-021-00045-x","type":"journal-article","created":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T11:03:10Z","timestamp":1619434990000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Smooth input preparation for quantum and quantum-inspired machine learning"],"prefix":"10.1007","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9043-8289","authenticated-orcid":false,"given":"Zhikuan","family":"Zhao","sequence":"first","affiliation":[]},{"given":"Jack K.","family":"Fitzsimons","sequence":"additional","affiliation":[]},{"given":"Patrick","family":"Rebentrost","sequence":"additional","affiliation":[]},{"given":"Vedran","family":"Dunjko","sequence":"additional","affiliation":[]},{"given":"Joseph F.","family":"Fitzsimons","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,4,26]]},"reference":[{"issue":"4","key":"45_CR1","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1038\/nphys3272","volume":"11","author":"S Aaronson","year":"2015","unstructured":"Aaronson S (2015) Nat Phys 11(4):291\u2013293","journal-title":"Nat Phys"},{"key":"45_CR2","doi-asserted-by":"crossref","unstructured":"A\u00efmeur E, Brassard G, Gambs S (2006) Advances in Artificial Intelligence, Springer, pp. 431\u2013442","DOI":"10.1007\/11766247_37"},{"issue":"2","key":"45_CR3","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 (2017) ACM SIGACT News 48(2):41\u201367","journal-title":"ACM SIGACT News"},{"key":"45_CR4","unstructured":"Boyer M, Brassard G, H\u00f8yer P, Tapp A (1996) arXiv preprint quant-ph\/9605034"},{"issue":"12","key":"45_CR5","doi-asserted-by":"publisher","first-page":"7907","DOI":"10.1109\/TIT.2011.2164053","volume":"57","author":"N Cesa-Bianchi","year":"2011","unstructured":"Cesa-Bianchi N, Shalev-Shwartz S, Shamir O (2011) IEEE Trans Inf Theory 57 (12):7907\u20137931","journal-title":"IEEE Trans Inf Theory"},{"key":"45_CR6","unstructured":"Chia N-H, Lin H-H, Wang C (2018) arXiv preprint arXiv:1811.04852"},{"issue":"6","key":"45_CR7","doi-asserted-by":"publisher","first-page":"1920","DOI":"10.1137\/16M1087072","volume":"46","author":"AM Childs","year":"2017","unstructured":"Childs AM, Kothari R, Somma RD (2017) SIAM J Comput 46(6):1920\u20131950","journal-title":"SIAM J Comput"},{"key":"45_CR8","unstructured":"Dehdashti S, Moreira C, Obeid A K, Bruza P (2020) arXiv preprint arXiv:2006.02904"},{"key":"45_CR9","unstructured":"Dodge S, Karam L (2016) In: Quality of multimedia experience (QoMEX), 2016 Eighth international conference on (IEEE), pp. 1\u20136"},{"key":"45_CR10","doi-asserted-by":"crossref","unstructured":"Dunjko V, Briegel HJ (2018) RepProg Phys 81 074001","DOI":"10.1088\/1361-6633\/aab406"},{"key":"45_CR11","unstructured":"Genton MG (2001) Journal of machine learning research 2:299"},{"key":"45_CR12","unstructured":"Gily\u00e9n A, Lloyd S, Tang E (2018) arXiv preprint arXiv:1811.04909"},{"key":"45_CR13","unstructured":"Gily\u00e9n A, Su Y, Low G, Wiebe N (2018) arXiv preprint arXiv:1806.018381806.01838"},{"issue":"16","key":"45_CR14","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 (2008) Phys Rev Lett 100(16): 160501","journal-title":"Phys Rev Lett"},{"issue":"15","key":"45_CR15","doi-asserted-by":"publisher","first-page":"150502","DOI":"10.1103\/PhysRevLett.103.150502","volume":"103","author":"AW Harrow","year":"2009","unstructured":"Harrow AW, Hassidim A, Lloyd S (2009) Phys Rev Lett 103(15): 150502","journal-title":"Phys Rev Lett"},{"issue":"7747","key":"45_CR16","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 AD, Temme K, Harrow AW, Kandala A, Chow JM, Gambetta JM (2019) Nature 567(7747):209\u2013212","journal-title":"Nature"},{"key":"45_CR17","unstructured":"International Comprehensive Ocean-Atmosphere Data Set (http:\/\/icoads.noaa.gov\/)"},{"key":"45_CR18","unstructured":"Kalapanidas E, Avouris N, Craciun M, Neagu D (2003) Machine learning algorithms: a study on noise sensitivity. In Proc. 1st Balcan Conference in Informatics. pp. 356\u2013365"},{"key":"45_CR19","doi-asserted-by":"publisher","unstructured":"Kerenidis I, Prakash A (2017) Quantum Recommendation Systems. In: Papadimitriou C. H (ed) 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), vol 67. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, pp 49:1\u201349:21, DOI https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2017.49","DOI":"10.4230\/LIPIcs.ITCS.2017.49"},{"issue":"3","key":"45_CR20","doi-asserted-by":"publisher","first-page":"033159","DOI":"10.1103\/PhysRevResearch.1.033159","volume":"1","author":"JM K\u00fcbler","year":"2019","unstructured":"K\u00fcbler JM, Muandet K, Sch\u00f6lkopf B (2019) Physical Review Research 1(3):033159","journal-title":"Physical Review Research"},{"key":"45_CR21","unstructured":"Lloyd S, Mohseni M, Rebentrost P (2013) arXiv preprint arXiv:1307.04111307.0411"},{"issue":"9","key":"45_CR22","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 (2014) Nat Phys 10(9):631\u2013633","journal-title":"Nat Phys"},{"issue":"13","key":"45_CR23","doi-asserted-by":"publisher","first-page":"130503","DOI":"10.1103\/PhysRevLett.113.130503","volume":"113","author":"S Lloyd","year":"2014","unstructured":"Lloyd S, Mohseni M, Rebentrost P (2014) Phys Rev Lett 113(13): 130503","journal-title":"Phys Rev Lett"},{"issue":"4","key":"45_CR24","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s10462-010-9156-z","volume":"33","author":"DF Nettleton","year":"2010","unstructured":"Nettleton DF, Orriols-Puig A, Fornells A (2010) Artif Intell Rev 33(4):275\u2013306","journal-title":"Artif Intell Rev"},{"key":"45_CR25","unstructured":"Practical Geostatistics 2000 Data Sets (http:\/\/www.kriging.com\/datasets\/)"},{"key":"45_CR26","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 (2014) Phys Rev Let 113: 130503","journal-title":"Phys Rev Let"},{"issue":"4","key":"45_CR27","doi-asserted-by":"publisher","first-page":"040504","DOI":"10.1103\/PhysRevLett.122.040504","volume":"122","author":"M Schuld","year":"2019","unstructured":"Schuld M, Killoran N (2019) Phys Rev Let 122(4):040504","journal-title":"Phys Rev Let"},{"key":"45_CR28","doi-asserted-by":"crossref","unstructured":"Schuld M, Sinayskiy I, Petruccione F (2014) In: PRICAI 2014: Trends in artificial intelligence, Springer, pp. 208\u2013220","DOI":"10.1007\/978-3-319-13560-1_17"},{"issue":"1","key":"45_CR29","doi-asserted-by":"publisher","first-page":"012307","DOI":"10.1103\/PhysRevA.73.012307","volume":"73","author":"AN Soklakov","year":"2006","unstructured":"Soklakov AN, Schack R (2006) Phys Rev A 73(1):012307","journal-title":"Phys Rev A"},{"key":"45_CR30","unstructured":"Spielman D, Teng SH (2001) In: ACM symposium on theory of computing, pp. 296\u2013305"},{"issue":"10","key":"45_CR31","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1145\/1562764.1562785","volume":"52","author":"DA Spielman","year":"2009","unstructured":"Spielman DA, Teng S-H (2009) Commun ACM 52(10):76\u201384","journal-title":"Commun ACM"},{"key":"45_CR32","unstructured":"Tang E (2018) arXiv preprint arXiv:1807.04271"},{"key":"45_CR33","unstructured":"Tang E (2018) arXiv preprint arXiv:1811.00414"},{"key":"45_CR34","unstructured":"Tiwari P, Dehdashti S, Obeid AK, Melucci M, Bruza P (2020) arXiv preprint arXiv:2007.07887"},{"issue":"5","key":"45_CR35","doi-asserted-by":"publisher","first-page":"050502","DOI":"10.1103\/PhysRevLett.120.050502","volume":"120","author":"L Wossnig","year":"2018","unstructured":"Wossnig L, Zhao Z, Prakash A (2018) Phys Rev Let 120(5):050502","journal-title":"Phys Rev Let"},{"issue":"21","key":"45_CR36","doi-asserted-by":"publisher","first-page":"210501","DOI":"10.1103\/PhysRevLett.113.210501","volume":"113","author":"TJ Yoder","year":"2014","unstructured":"Yoder TJ, Low GH, Chuang IL (2014) Phys Rev Let 113(21):210501","journal-title":"Phys Rev Let"},{"key":"45_CR37","unstructured":"Zhao L, Zhao Z, Rebentrost P, Fitzsimons J (2019) arXiv preprint arXiv:1902.10394"},{"key":"45_CR38","doi-asserted-by":"publisher","first-page":"052331","DOI":"10.1103\/PhysRevA.99.052331","volume":"99","author":"Z Zhao","year":"2019","unstructured":"Zhao Z, Fitzsimons JK, Fitzsimons JF (2019) Phys. Rev. A 99:052331. https:\/\/doi.org\/10.1103\/PhysRevA.99.052331","journal-title":"Phys. Rev. A"},{"issue":"1","key":"45_CR39","doi-asserted-by":"publisher","first-page":"012304","DOI":"10.1103\/PhysRevA.100.012304","volume":"100","author":"Z Zhao","year":"2019","unstructured":"Zhao Z, Fitzsimons JK, Osborne MA, Roberts SJ, Fitzsimons JF (2019) Phys Rev A 100(1):012304","journal-title":"Phys Rev A"},{"key":"45_CR40","doi-asserted-by":"publisher","unstructured":"Zhao Z, Pozas-Kerstjens A, Rebentrost P, Wittek P (2019) Quantum Machine Intelligence. https:\/\/doi.org\/10.1007\/s42484-019-00004-7","DOI":"10.1007\/s42484-019-00004-7"}],"container-title":["Quantum Machine Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-021-00045-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42484-021-00045-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-021-00045-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,2]],"date-time":"2021-07-02T08:28:22Z","timestamp":1625214502000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42484-021-00045-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,26]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["45"],"URL":"https:\/\/doi.org\/10.1007\/s42484-021-00045-x","relation":{},"ISSN":["2524-4906","2524-4914"],"issn-type":[{"type":"print","value":"2524-4906"},{"type":"electronic","value":"2524-4914"}],"subject":[],"published":{"date-parts":[[2021,4,26]]},"assertion":[{"value":"4 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Dr. Fitzsimons has financial holdings in Horizon Quantum Computing Pte Ltd. Otherwise, the authors have no potential financial or non-financial conflicts of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Competing interests"}}],"article-number":"14"}}