{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T19:10:12Z","timestamp":1783451412507,"version":"3.55.0"},"reference-count":83,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T00:00:00Z","timestamp":1666828800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Scott Aaronson\u2019s Vannevar Bush Faculty Fellowship from the US Department of Defense"},{"name":"Samsung Electronics Co., Ltd., for the project \u201cThe Computational Power of Sampling on Quantum Computers\u201d"},{"name":"Institute for Quantum Information and Matter, an NSF Physics Frontiers Center","award":["PHY-1733907"],"award-info":[{"award-number":["PHY-1733907"]}]},{"name":"EU\u2019s Horizon 2020 Marie Sk\u0142odowska-Curie program","award":["891889-QuantOrder"],"award-info":[{"award-number":["891889-QuantOrder"]}]},{"name":"IBM PhD Fellowship, QISE-NET Triplet Award","award":["DMR-1747426"],"award-info":[{"award-number":["DMR-1747426"]}]},{"name":"U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Quantum Algorithms Teams program"},{"DOI":"10.13039\/100023581","name":"National Science Foundation Graduate Research Fellowship Program","doi-asserted-by":"crossref","award":["DGE-1762114"],"award-info":[{"award-number":["DGE-1762114"]}],"id":[{"id":"10.13039\/100023581","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>\n            We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang\u2019s breakthrough quantum-inspired algorithm for recommendation systems [STOC\u201919]. Motivated by quantum linear algebra algorithms and the quantum singular value transformation (SVT) framework of Gily\u00e9n et\u00a0al.\u00a0[STOC\u201919], we develop classical algorithms for SVT that run in time independent of input dimension, under suitable quantum-inspired sampling assumptions. Our results give compelling evidence that in the corresponding QRAM data structure input model, quantum SVT does not yield exponential quantum speedups. Since the quantum SVT framework generalizes essentially all known techniques for quantum linear algebra, our results, combined with sampling lemmas from previous work, suffice to generalize all prior results about dequantizing quantum machine learning algorithms. In particular, our classical SVT framework recovers and often improves the dequantization results on recommendation systems, principal component analysis, supervised clustering, support vector machines, low-rank regression, and semidefinite program solving. We also give additional dequantization results on low-rank Hamiltonian simulation and discriminant analysis. Our improvements come from identifying the key feature of the quantum-inspired input model that is at the core of all prior quantum-inspired results: \u2113\n            <jats:sup>2<\/jats:sup>\n            -norm sampling can approximate matrix products in time independent of their dimension. We reduce all our main results to this fact, making our exposition concise, self-contained, and intuitive.\n          <\/jats:p>","DOI":"10.1145\/3549524","type":"journal-article","created":{"date-parts":[[2022,8,10]],"date-time":"2022-08-10T08:20:09Z","timestamp":1660119609000},"page":"1-72","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4138-7956","authenticated-orcid":false,"given":"Nai-Hui","family":"Chia","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Texas at Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5992-5743","authenticated-orcid":false,"given":"Andr\u00e1s Pal","family":"Gily\u00e9n","sequence":"additional","affiliation":[{"name":"Alfr\u00e9d R\u00e9nyi Institute of Mathematics Hungary and Institute for Quantum Information and Matter, California Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0338-413X","authenticated-orcid":false,"given":"Tongyang","family":"Li","sequence":"additional","affiliation":[{"name":"Center on Frontiers of Computing Studies, School of Computer Science, Peking University China and Center for Theoretical Physics, Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5126-0174","authenticated-orcid":false,"given":"Han-Hsuan","family":"Lin","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Texas at Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7451-9687","authenticated-orcid":false,"given":"Ewin","family":"Tang","sequence":"additional","affiliation":[{"name":"University of Washington, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9983-5774","authenticated-orcid":false,"given":"Chunhao","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Pennsylvania State University, USA and Department of Computer Science, University of Texas at Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,10,27]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1038\/nphys3272"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-021-27922-0"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780546"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2009.12.018"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2011.07.009"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.99"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-02-14-230"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2837020"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-08-13-307"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/34.598228"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971170"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.54"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0653-8"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0793-1"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.27"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.45"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.102.052411"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.33"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/627"},{"key":"e_1_3_3_21_2","unstructured":"Nadiia Chepurko Kenneth L. Clarkson Lior Horesh Honghao Lin and David P. Woodruff. 2020. Quantum-inspired algorithms from randomized numerical linear algebra. In International Conference on Machine Learning. PMLR 3879\u20133900."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ISAAC.2020.47"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2020.23"},{"key":"e_1_3_3_24_2","unstructured":"Nai-Hui Chia Han-Hsuan Lin and Chunhao Wang. 2018. Quantum-inspired sublinear classical algorithms for solving low-rank linear systems. arXiv:1811.04852. Retrieved from https:\/\/arxiv.org\/abs\/1811.04852."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2017.0551"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3019134"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.115"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/18\/7\/073011"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220098"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2021.3084467"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442684"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509922"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.08.023"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/07070471x"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevResearch.2.033199"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.22331\/qv-2020-03-17-32"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.84.108"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02650179"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039494"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.13001\/1081-3810.1375"},{"key":"e_1_3_3_41_2","unstructured":"Andr\u00e1s Gily\u00e9n Seth Lloyd and Ewin Tang. 2018. Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension. arXiv:1811.04909. Retrieved from https:\/\/arxiv.org\/abs\/1811.04909."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316366"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.100.160501"},{"key":"e_1_3_3_44_2","unstructured":"Lov Grover and Terry Rudolph. 2002. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv:quant-ph\/0208112. Retrieved from https:\/\/arxiv.org\/abs\/quant-ph\/0208112."},{"key":"e_1_3_3_45_2","unstructured":"Casper Gyurik Chris Cade and Vedran Dunjko. 2020. Towards quantum advantage via topological data analysis. arXiv:2005.02607. Retrieved from https:\/\/arxiv.org\/abs\/2005.02607."},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"e_1_3_3_47_2","first-page":"1233","volume-title":"Advances in Neural Information Processing Systems, Vol. 24","author":"Hazan Elad","year":"2011","unstructured":"Elad Hazan, Tomer Koren, and Nati Srebro. 2011. Beating SGD: Learning SVMs in sublinear time. In Advances in Neural Information Processing Systems, Vol. 24, J. Shawe-Taylor, R. S. Zemel, P. L. Bartlett, F. Pereira, and K. Q. Weinberger (Eds.). Curran Associates, Inc., Red Hook, NY, 1233\u20131241."},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.126.190505"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2020.53"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.5555\/1368636"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492917000058"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.73.1020"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2017.49"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.101.022316"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746599"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.273.5278.1073"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms10138"},{"key":"e_1_3_3_58_2","unstructured":"Seth Lloyd Masoud Mohseni and Patrick Rebentrost. 2013. Quantum algorithms for supervised and unsupervised machine learning. arXiv:1307.0411. Retrieved from https:\/\/arxiv.org\/abs\/1307.0411."},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1038\/nphys3029"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.118.010501"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1561\/2200000035"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1137\/060665336"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.2.040203"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107359949.008"},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301389"},{"key":"e_1_3_3_66_2","volume-title":"Quantum Algorithms for Linear Algebra and Machine Learning","author":"Prakash Anupam","year":"2014","unstructured":"Anupam Prakash. 2014. Quantum Algorithms for Linear Algebra and Machine Learning. Ph.D. Dissertation. University of California at Berkeley."},{"key":"e_1_3_3_67_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2018-08-06-79"},{"key":"e_1_3_3_68_2","unstructured":"Patrick Rebentrost and Seth Lloyd. 2018. Quantum computational finance: quantum algorithm for portfolio optimization. arXiv:1811.03975. Retrieved from https:\/\/arxiv.org\/abs\/1811.03975."},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.113.130503"},{"key":"e_1_3_3_70_2","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/ab2a9e"},{"key":"e_1_3_3_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/1255443.1255449"},{"key":"e_1_3_3_72_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-02-20-234"},{"key":"e_1_3_3_73_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_3_3_74_2","first-page":"793","volume-title":"Advances in Neural Information Processing Systems, Vol. 29","author":"Song Zhao","year":"2016","unstructured":"Zhao Song, David Woodruff, and Huan Zhang. 2016. Sublinear time orthogonal tensor decomposition. In Advances in Neural Information Processing Systems, Vol. 29. Curran Associates, Inc., Red Hook, NY, 793\u2013801. http:\/\/papers.nips.cc\/paper\/6496-sublinear-time-orthogonal-tensor-decomposition.pdf."},{"key":"e_1_3_3_75_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316310"},{"key":"e_1_3_3_76_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.127.060503"},{"key":"e_1_3_3_77_2","unstructured":"Terence Tao. 2010. 254A Notes 3a: Eigenvalues and Sums of Hermitian Matrices. Retrieved from https:\/\/terrytao.wordpress.com\/2010\/01\/12\/254a-notes-3a-eigenvalues-and-sums-of-hermitian-matrices\/."},{"key":"e_1_3_3_78_2","doi-asserted-by":"publisher","DOI":"10.26421\/QIC11.9-10"},{"key":"e_1_3_3_79_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.92917"},{"key":"e_1_3_3_80_2","unstructured":"Max Welling. 2009. Fisher Linear Discriminant Analysis. Retrieved from https:\/\/www.ics.uci.edu\/welling\/teaching\/273ASpring09\/Fisher-LDA.pdf."},{"key":"e_1_3_3_81_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"},{"key":"e_1_3_3_82_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.120.050502"},{"key":"e_1_3_3_83_2","first-page":"13674","volume-title":"Advances in Neural Information Processing Systems","author":"Yamasaki Hayata","year":"2020","unstructured":"Hayata Yamasaki, Sathyawageeswar Subramanian, Sho Sonoda, and Masato Koashi. 2020. Learning with optimized random features: Exponential speedup by quantum machine learning without sparsity and low-rank assumptions. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (Eds.). Vol. 33. Curran Associates, Inc., Red Hook, NY, 13674\u201313687."},{"key":"e_1_3_3_84_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.99.052331"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3549524","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3549524","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3549524","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T16:37:30Z","timestamp":1756485450000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3549524"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,27]]},"references-count":83,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3549524"],"URL":"https:\/\/doi.org\/10.1145\/3549524","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,27]]},"assertion":[{"value":"2020-08-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}