{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T02:44:59Z","timestamp":1781837099904,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000005","name":"U.S. Department of Defense","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000005","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMR-1747426, PHY-1733907, DGE-1762114"],"award-info":[{"award-number":["DMR-1747426, PHY-1733907, DGE-1762114"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384314","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"387-400","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":50,"title":["Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing Quantum machine learning"],"prefix":"10.1145","author":[{"given":"Nai-Hui","family":"Chia","sequence":"first","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andr\u00e1s","family":"Gily\u00e9n","sequence":"additional","affiliation":[{"name":"California Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tongyang","family":"Li","sequence":"additional","affiliation":[{"name":"University of Maryland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Han-Hsuan","family":"Lin","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ewin","family":"Tang","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chunhao","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Scott Aaronson. 2015. Read the fine print. Nature Physics 11 4 ( 2015 ) 291.  Scott Aaronson. 2015. Read the fine print. Nature Physics 11 4 ( 2015 ) 291.","DOI":"10.1038\/nphys3272"},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP). 99 : 1-99 : 15","author":"van Apeldoorn Joran","year":"2019","unstructured":"Joran van Apeldoorn and Andr\u00e1s Gily\u00e9n . 2019 . Improvements in quantum SDPsolving with applications . In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP). 99 : 1-99 : 15 . arXiv: 1804.05058 Joran van Apeldoorn and Andr\u00e1s Gily\u00e9n. 2019. Improvements in quantum SDPsolving with applications. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP). 99 : 1-99 : 15. arXiv: 1804.05058"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837020"},{"key":"e_1_3_2_1_4_1","volume-title":"Bhaskar Roy Bardhan, and Seth Lloyd","author":"Arrazola Juan Miguel","year":"2019","unstructured":"Juan Miguel Arrazola , Alain Delgado , Bhaskar Roy Bardhan, and Seth Lloyd . 2019 . Quantum-inspired algorithms in practice. arXiv: 1905.10415 Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan, and Seth Lloyd. 2019. Quantum-inspired algorithms in practice. arXiv: 1905.10415"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP). 27 : 1-27 : 14","author":"Brand\u00e3o Fernando G. S. L.","year":"2019","unstructured":"Fernando G. S. L. Brand\u00e3o , Amir Kalev , Tongyang Li , Cedric Yen-Yu Lin , Krysta M. Svore , and Xiaodi Wu . 2019 . Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning . In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP). 27 : 1-27 : 14 . arXiv: 1710. 02581 Fernando G. S. L. Brand\u00e3o, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. 2019. Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP). 27 : 1-27 : 14. arXiv: 1710. 02581"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP). 33 : 1-33 : 14","author":"Chakraborty Shantanav","year":"2019","unstructured":"Shantanav Chakraborty , Andr\u00e1s Gily\u00e9n , and Stacey Jefery . 2019 . The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation . In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP). 33 : 1-33 : 14 . arXiv: 1804.01973 Shantanav Chakraborty, Andr\u00e1s Gily\u00e9n, and Stacey Jefery. 2019. The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP). 33 : 1-33 : 14. arXiv: 1804.01973"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/627"},{"key":"e_1_3_2_1_8_1","volume-title":"Quantuminspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches. ( 2019 ). arXiv","author":"Chia Nai-Hui","year":"1901","unstructured":"Nai-Hui Chia , Tongyang Li , Han-Hsuan Lin , and Chunhao Wang . 2019. Quantuminspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches. ( 2019 ). arXiv : 1901 .03254 Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang. 2019. Quantuminspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches. ( 2019 ). arXiv: 1901.03254"},{"key":"e_1_3_2_1_9_1","volume-title":"Quantum-inspired sublinear classical algorithms for solving low-rank linear systems. ( 2018 ). arXiv","author":"Chia Nai-Hui","year":"1811","unstructured":"Nai-Hui Chia , Han-Hsuan Lin , and Chunhao Wang . 2018. Quantum-inspired sublinear classical algorithms for solving low-rank linear systems. ( 2018 ). arXiv : 1811 .04852 Nai-Hui Chia, Han-Hsuan Lin, and Chunhao Wang. 2018. Quantum-inspired sublinear classical algorithms for solving low-rank linear systems. ( 2018 ). arXiv: 1811.04852"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2017.0551"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/18\/7\/073011"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220098"},{"key":"e_1_3_2_1_13_1","volume-title":"Quantum-Inspired Support Vector Machine. arXiv","author":"Ding Chen","year":"1906","unstructured":"Chen Ding , Tian-Yi Bao , and He-Liang Huang . 2019. Quantum-Inspired Support Vector Machine. arXiv : 1906 .08902 Chen Ding, Tian-Yi Bao, and He-Liang Huang. 2019. Quantum-Inspired Support Vector Machine. arXiv: 1906.08902"},{"key":"e_1_3_2_1_14_1","volume-title":"Mahoney","author":"Drineas Petros","year":"2006","unstructured":"Petros Drineas , Ravi Kannan , and Michael W . Mahoney . 2006 . Fast Monte Carlo algorithms for matrices I : Approximating matrix multiplication. SIAM J. Comput . 36, 1 ( 2006 ), 132-157. Petros Drineas, Ravi Kannan, and Michael W. Mahoney. 2006. Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication. SIAM J. Comput. 36, 1 ( 2006 ), 132-157."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509922"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.08.023"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/07070471X"},{"key":"e_1_3_2_1_18_1","volume-title":"A quantuminspired algorithm for general minimum conical hull problems. arXiv","author":"Du Yuxuan","year":"1907","unstructured":"Yuxuan Du , Min-Hsiu Hsieh , Tongliang Liu , and Dacheng Tao . 2019. A quantuminspired algorithm for general minimum conical hull problems. arXiv : 1907 .06814 Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, and Dacheng Tao. 2019. A quantuminspired algorithm for general minimum conical hull problems. arXiv: 1907.06814"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Vedran Dunjko and Peter Wittek. 2020. A non-review of Quantum Machine Learning: trends and explorations. Quantum Views 4 (March 2020 ) 32.  Vedran Dunjko and Peter Wittek. 2020. A non-review of Quantum Machine Learning: trends and explorations. Quantum Views 4 (March 2020 ) 32.","DOI":"10.22331\/qv-2020-03-17-32"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039494"},{"key":"e_1_3_2_1_21_1","volume-title":"Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension. ( 2018 ). arXiv","author":"Gily\u00e9n Andr\u00e1s","year":"1811","unstructured":"Andr\u00e1s Gily\u00e9n , Seth Lloyd , and Ewin Tang . 2018. Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension. ( 2018 ). arXiv : 1811 .04909 Andr\u00e1s Gily\u00e9n, Seth Lloyd, and Ewin Tang. 2018. Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension. ( 2018 ). arXiv: 1811.04909"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316366"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.100.160501"},{"key":"e_1_3_2_1_24_1","unstructured":"Lov Grover and Terry Rudolph. 2002. Creating superpositions that correspond to eficiently integrable probability distributions. ( 2002 ). arXiv: quant-ph\/0208112  Lov Grover and Terry Rudolph. 2002. Creating superpositions that correspond to eficiently integrable probability distributions. ( 2002 ). arXiv: quant-ph\/0208112"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"e_1_3_2_1_26_1","unstructured":"Elad Hazan Tomer Koren and Nati Srebro. 2011. Beating SGD : Learning SVMs in sublinear time. In Advances in Neural Information Processing Systems 24 J. ShaweTaylor R. S. Zemel P. L. Bartlett F. Pereira and K. Q. Weinberger (Eds.). 1233-1241.  Elad Hazan Tomer Koren and Nati Srebro. 2011. Beating SGD : Learning SVMs in sublinear time. In Advances in Neural Information Processing Systems 24 J. ShaweTaylor R. S. Zemel P. L. Bartlett F. Pereira and K. Q. Weinberger (Eds.). 1233-1241."},{"key":"e_1_3_2_1_27_1","volume-title":"Fran\u00e7ois Le Gall, and Sanjay K. Singh","author":"Jethwani Dhawal","year":"2019","unstructured":"Dhawal Jethwani , Fran\u00e7ois Le Gall, and Sanjay K. Singh . 2019 . Quantum-inspired classical algorithms for singular value transformation. ( 2019 ). arXiv: 1910.05699 Dhawal Jethwani, Fran\u00e7ois Le Gall, and Sanjay K. Singh. 2019. Quantum-inspired classical algorithms for singular value transformation. ( 2019 ). arXiv: 1910.05699"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Ravindran Kannan and Santosh Vempala. 2017. Randomized algorithms in numerical linear algebra. Acta Numerica 26 ( 2017 ) 95-135.  Ravindran Kannan and Santosh Vempala. 2017. Randomized algorithms in numerical linear algebra. Acta Numerica 26 ( 2017 ) 95-135.","DOI":"10.1017\/S0962492917000058"},{"key":"e_1_3_2_1_29_1","volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS). 49 : 1-49 : 21","author":"Kerenidis Iordanis","year":"2017","unstructured":"Iordanis Kerenidis and Anupam Prakash . 2017 . Quantum recommendation systems . In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS). 49 : 1-49 : 21 . arXiv: 1603. 08675 Iordanis Kerenidis and Anupam Prakash. 2017. Quantum recommendation systems. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS). 49 : 1-49 : 21. arXiv: 1603. 08675"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.101.022316"},{"key":"e_1_3_2_1_31_1","unstructured":"Seth Lloyd Silvano Garnerone and Paolo Zanardi. 2016. Quantum algorithms for topological and geometric analysis of data. Nature Communications 7 ( 2016 ) 10138. arXiv: 1408. 3106  Seth Lloyd Silvano Garnerone and Paolo Zanardi. 2016. Quantum algorithms for topological and geometric analysis of data. Nature Communications 7 ( 2016 ) 10138. arXiv: 1408. 3106"},{"key":"e_1_3_2_1_32_1","unstructured":"Seth Lloyd Masoud Mohseni and Patrick Rebentrost. 2013. Quantum algorithms for supervised and unsupervised machine learning. arXiv: 1307.0411  Seth Lloyd Masoud Mohseni and Patrick Rebentrost. 2013. Quantum algorithms for supervised and unsupervised machine learning. arXiv: 1307.0411"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Seth Lloyd Masoud Mohseni and Patrick Rebentrost. 2014. Quantum principal component analysis. Nature Physics 10 ( 2014 ) 631-633. arXiv: 1307. 0401  Seth Lloyd Masoud Mohseni and Patrick Rebentrost. 2014. Quantum principal component analysis. Nature Physics 10 ( 2014 ) 631-633. arXiv: 1307. 0401","DOI":"10.1038\/nphys3029"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.118.010501"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Michael W. Mahoney. 2011. Randomized algorithms for matrices and data. Foundations and Trends\u00ae in Machine Learning 3 2 ( 2011 ) 123-224.  Michael W. Mahoney. 2011. Randomized algorithms for matrices and data. Foundations and Trends\u00ae in Machine Learning 3 2 ( 2011 ) 123-224.","DOI":"10.1561\/2200000035"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/060665336"},{"key":"e_1_3_2_1_38_1","volume-title":"Quantum Computing in the NISQ era and beyond. Quantum 2 ( 2018 ), 79. arXiv","author":"Preskill John","year":"1801","unstructured":"John Preskill . 2018. Quantum Computing in the NISQ era and beyond. Quantum 2 ( 2018 ), 79. arXiv : 1801 .00862 John Preskill. 2018. Quantum Computing in the NISQ era and beyond. Quantum 2 ( 2018 ), 79. arXiv: 1801.00862"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.113.130503"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/ab2a9e"},{"key":"e_1_3_2_1_41_1","volume-title":"Andrea Rocchetto, Massimiliano Pontil, and Simone Severini.","author":"Rudi Alessandro","year":"2020","unstructured":"Alessandro Rudi , Leonard Wossnig , Carlo Ciliberto , Andrea Rocchetto, Massimiliano Pontil, and Simone Severini. 2020 . Approximating Hamiltonian dynamics with the Nystr\u00f6m method. Quantum 4 ( 2020 ), 234. arXiv: 1804.02484 Alessandro Rudi, Leonard Wossnig, Carlo Ciliberto, Andrea Rocchetto, Massimiliano Pontil, and Simone Severini. 2020. Approximating Hamiltonian dynamics with the Nystr\u00f6m method. Quantum 4 ( 2020 ), 234. arXiv: 1804.02484"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_3_2_1_43_1","first-page":"793","article-title":"Sublinear time orthogonal tensor decomposition. In Advances in Neural Information Processing Systems 29. Curran Associates","author":"Song Zhao","year":"2016","unstructured":"Zhao Song , David Woodruf , and Huan Zhang . 2016 . Sublinear time orthogonal tensor decomposition. In Advances in Neural Information Processing Systems 29. Curran Associates , Inc. , 793 - 801 . Zhao Song, David Woodruf, and Huan Zhang. 2016. Sublinear time orthogonal tensor decomposition. In Advances in Neural Information Processing Systems 29. Curran Associates, Inc., 793-801.","journal-title":"Inc."},{"key":"e_1_3_2_1_44_1","volume-title":"Quantum-inspired classical algorithms for principal component analysis and supervised clustering. ( 2018 ). arXiv","author":"Tang Ewin","year":"1811","unstructured":"Ewin Tang . 2018. Quantum-inspired classical algorithms for principal component analysis and supervised clustering. ( 2018 ). arXiv : 1811 .00414 Ewin Tang. 2018. Quantum-inspired classical algorithms for principal component analysis and supervised clustering. ( 2018 ). arXiv: 1811.00414"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316310"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Maarten Van den Nest. 2011. Simulating quantum computers with probabilistic methods. Quantum Information and Computation 11 9 & 10 ( 2011 ) 784-812. arXiv: 0911. 1624  Maarten Van den Nest. 2011. Simulating quantum computers with probabilistic methods. Quantum Information and Computation 11 9 & 10 ( 2011 ) 784-812. arXiv: 0911. 1624","DOI":"10.26421\/QIC11.9-10-5"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.92917"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"crossref","unstructured":"David P. Woodruf. 2014. Sketching as a tool for numerical linear algebra. Foundations and Trends\u00ae in Theoretical Computer Science 10 1-2 ( 2014 ) 1-157.  David P. Woodruf. 2014. Sketching as a tool for numerical linear algebra. Foundations and Trends\u00ae in Theoretical Computer Science 10 1-2 ( 2014 ) 1-157.","DOI":"10.1561\/0400000060"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.120.050502"},{"key":"e_1_3_2_1_50_1","volume-title":"Fitzsimons","author":"Zhao Zhikuan","year":"2019","unstructured":"Zhikuan Zhao , Jack K. Fitzsimons , and Joseph F . Fitzsimons . 2019 . Quantumassisted Gaussian process regression. Physical Review A 99 (May 2019 ), 052331. Issue 5. arXiv: 1512. 03929 Zhikuan Zhao, Jack K. Fitzsimons, and Joseph F. Fitzsimons. 2019. Quantumassisted Gaussian process regression. Physical Review A 99 (May 2019 ), 052331. Issue 5. arXiv: 1512. 03929"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384314","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384314","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384314","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:13Z","timestamp":1750200073000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384314"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":49,"alternative-id":["10.1145\/3357713.3384314","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384314","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}