{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T03:43:44Z","timestamp":1775706224063,"version":"3.50.1"},"reference-count":35,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T00:00:00Z","timestamp":1656547200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["PHY-1733907"],"award-info":[{"award-number":["PHY-1733907"]}]},{"name":"ERC","award":["QPROGRESS"],"award-info":[{"award-number":["QPROGRESS"]}]},{"DOI":"10.13039\/501100020314","name":"QuantERA","doi-asserted-by":"crossref","award":["QuantAlgo 680-91-034"],"award-info":[{"award-number":["QuantAlgo 680-91-034"]}],"id":[{"id":"10.13039\/501100020314","id-type":"DOI","asserted-by":"crossref"}]},{"name":"EU\u2019s Horizon 2020 Marie Sk\u0142odowska-Curie program","award":["891889-QuantOrder"],"award-info":[{"award-number":["891889-QuantOrder"]}]},{"name":"NSF","award":["DGE-1762114"],"award-info":[{"award-number":["DGE-1762114"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review Letters'09] for low-rank matrices [Wossnig, Zhao, and Prakash, Physical Review Letters'18], when the input matrix A<\/mml:mi><\/mml:math> is stored in a data structure applicable for QRAM-based state preparation.Namely, suppose we are given an A<\/mml:mi>&#x2208;<\/mml:mo>C<\/mml:mi><\/mml:mrow>m<\/mml:mi>&#x00D7;<\/mml:mo>n<\/mml:mi><\/mml:mrow><\/mml:msup><\/mml:math> with minimum non-zero singular value &#x03C3;<\/mml:mi><\/mml:math> which supports certain efficient &#x2113;<\/mml:mi>2<\/mml:mn><\/mml:msub><\/mml:math>-norm importance sampling queries, along with a b<\/mml:mi>&#x2208;<\/mml:mo>C<\/mml:mi><\/mml:mrow>m<\/mml:mi><\/mml:msup><\/mml:math>. Then, for some x<\/mml:mi>&#x2208;<\/mml:mo>C<\/mml:mi><\/mml:mrow>n<\/mml:mi><\/mml:msup><\/mml:math> satisfying &#x2016;<\/mml:mo>x<\/mml:mi>&#x2013;<\/mml:mo>A<\/mml:mi>+<\/mml:mo><\/mml:msup>b<\/mml:mi>&#x2016;<\/mml:mo>&#x2264;<\/mml:mo>&#x03B5;<\/mml:mi>&#x2016;<\/mml:mo>A<\/mml:mi>+<\/mml:mo><\/mml:msup>b<\/mml:mi>&#x2016;<\/mml:mo><\/mml:math>, we can output a measurement of |<\/mml:mo><\/mml:mrow>x<\/mml:mi>&#x27E9;<\/mml:mo><\/mml:math> in the computational basis and output an entry of x<\/mml:mi><\/mml:math> with classical algorithms that run in O<\/mml:mi><\/mml:mrow>&#x007E;<\/mml:mo><\/mml:mover><\/mml:mrow>(<\/mml:mo><\/mml:mrow>&#x2016;<\/mml:mo>A<\/mml:mi>&#x2016;<\/mml:mo>F<\/mml:mi><\/mml:mrow><\/mml:mrow>6<\/mml:mn><\/mml:msubsup>&#x2016;<\/mml:mo>A<\/mml:mi>&#x2016;<\/mml:mo>6<\/mml:mn><\/mml:msup><\/mml:mrow>&#x03C3;<\/mml:mi>12<\/mml:mn><\/mml:mrow><\/mml:msup>&#x03B5;<\/mml:mi>4<\/mml:mn><\/mml:msup><\/mml:mrow><\/mml:mfrac>)<\/mml:mo><\/mml:mrow><\/mml:math> and O<\/mml:mi><\/mml:mrow>&#x007E;<\/mml:mo><\/mml:mover><\/mml:mrow>(<\/mml:mo><\/mml:mrow>&#x2016;<\/mml:mo>A<\/mml:mi>&#x2016;<\/mml:mo>F<\/mml:mi><\/mml:mrow><\/mml:mrow>6<\/mml:mn><\/mml:msubsup>&#x2016;<\/mml:mo>A<\/mml:mi>&#x2016;<\/mml:mo>2<\/mml:mn><\/mml:msup><\/mml:mrow>&#x03C3;<\/mml:mi>8<\/mml:mn><\/mml:msup>&#x03B5;<\/mml:mi>4<\/mml:mn><\/mml:msup><\/mml:mrow><\/mml:mfrac>)<\/mml:mo><\/mml:mrow><\/mml:math> time, respectively. This improves on previous \"quantum-inspired\" algorithms in this line of research by at least a factor of &#x2016;<\/mml:mo>A<\/mml:mi>&#x2016;<\/mml:mo>16<\/mml:mn><\/mml:mrow><\/mml:msup><\/mml:mrow>&#x03C3;<\/mml:mi>16<\/mml:mn><\/mml:mrow><\/mml:msup>&#x03B5;<\/mml:mi>2<\/mml:mn><\/mml:msup><\/mml:mrow><\/mml:mfrac><\/mml:math> [Chia, Gily\u00e9n, Li, Lin, Tang, and Wang, STOC'20]. As a consequence, we show that quantum computers can achieve at most a factor-of-12 speedup for linear regression in this QRAM data structure setting and related settings. Our work applies techniques from sketching algorithms and optimization to the quantum-inspired literature. Unlike earlier works, this is a promising avenue that could lead to feasible implementations of classical regression in a quantum-inspired settings, for comparison against future quantum computers.<\/jats:p>","DOI":"10.22331\/q-2022-06-30-754","type":"journal-article","created":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T13:03:59Z","timestamp":1656594239000},"page":"754","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":30,"title":["An improved quantum-inspired algorithm for linear regression"],"prefix":"10.22331","volume":"6","author":[{"given":"Andr\u00e1s","family":"Gily\u00e9n","sequence":"first","affiliation":[{"name":"Alfr\u00e9d R\u00e9nyi Institute of Mathematics"}]},{"given":"Zhao","family":"Song","sequence":"additional","affiliation":[{"name":"Adobe Research"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7451-9687","authenticated-orcid":false,"given":"Ewin","family":"Tang","sequence":"additional","affiliation":[{"name":"University of Washington"}]}],"member":"9598","published-online":{"date-parts":[[2022,6,30]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"John Preskill. ``Quantum Computing in the NISQ era and beyond''. Quantum 2, 79 (2018). arXiv:1801.00862.","DOI":"10.22331\/q-2018-08-06-79"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Andrew M Childs. ``Equation solving by simulation''. Nature Physics 5, 861\u2013861 (2009).","DOI":"10.1038\/nphys1473"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Scott Aaronson. ``Read the fine print''. Nature Physics 11, 291\u2013293 (2015).","DOI":"10.1038\/nphys3272"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. ``Quantum machine learning''. Nature 549, 195\u2013202 (2017). arXiv:1611.09347.","DOI":"10.1038\/nature23474"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Physical Review Letters 103, 150502 (2009). arXiv:0811.3171.","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, Yuan Su, Guang Hao Low, and Nathan Wiebe. ``Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics''. In Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC). Pages 193\u2013204. (2019). arXiv:1806.01838.","DOI":"10.1145\/3313276.3316366"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. ``Quantum random access memory''. Physical Review Letters 100, 160501 (2008). arXiv:0708.1879.","DOI":"10.1103\/PhysRevLett.100.160501"},{"key":"7","unstructured":"Anupam Prakash. ``Quantum algorithms for linear algebra and machine learning''. PhD thesis. University of California at Berkeley. (2014). url: www2.eecs.berkeley.edu\/Pubs\/TechRpts\/2014\/EECS-2014-211.pdf."},{"key":"8","doi-asserted-by":"publisher","unstructured":"Nai-Hui Chia, Andr\u00e1s Gily\u00e9n, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang. ``Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning''. In Proceedings of the 52nd ACM Symposium on the Theory of Computing (STOC). Page 387\u2013400. (2020). arXiv:1910.06151.","DOI":"10.1145\/3357713.3384314"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Iordanis Kerenidis and Anupam Prakash. ``Quantum recommendation systems''. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS). Pages 49:1\u201349:21. (2017). arXiv:1603.08675.","DOI":"10.4230\/LIPIcs.ITCS.2017.49"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Ewin Tang. ``A quantum-inspired classical algorithm for recommendation systems''. In Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC). Pages 217\u2013228. (2019). arXiv:1807.04271.","DOI":"10.1145\/3313276.3316310"},{"key":"11","unstructured":"Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash. ``q-means: A quantum algorithm for unsupervised machine learning''. In Advances in Neural Information Processing Systems. Volume 32. (2019). arXiv:1812.03584."},{"key":"12","doi-asserted-by":"publisher","unstructured":"Iordanis Kerenidis and Anupam Prakash. ``Quantum gradient descent for linear systems and least squares''. Physical Review A 101, 022316 (2020). arXiv:1704.04992.","DOI":"10.1103\/PhysRevA.101.022316"},{"key":"13","unstructured":"Danial Dervovic, Mark Herbster, Peter Mountney, Simone Severini, Na\u00efri Usher, and Leonard Wossnig. ``Quantum linear systems algorithms: a primer'' (2018). arXiv:1802.08227."},{"key":"14","doi-asserted-by":"publisher","unstructured":"Leonard Wossnig, Zhikuan Zhao, and Anupam Prakash. ``Quantum linear system algorithm for dense matrices''. Physical Review Letters 120, 050502 (2018). arXiv:1704.06174.","DOI":"10.1103\/PhysRevLett.120.050502"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. ``Quantum support vector machine for big data classification''. Physical Review Letters 113, 130503 (2014). arXiv:1307.0471.","DOI":"10.1103\/PhysRevLett.113.130503"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Shantanav Chakraborty, Andr\u00e1s Gily\u00e9n, and Stacey Jeffery. ``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). Pages 33:1\u201333:14. (2019). arXiv:1804.01973.","DOI":"10.4230\/LIPIcs.ICALP.2019.33"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Nai-Hui Chia, Andr\u00e1s Gily\u00e9n, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, and Chunhao Wang. ``Quantum-inspired algorithms for solving low-rank linear equation systems with logarithmic dependence on the dimension''. In Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC). Pages 47:1\u201347:17. (2020). arXiv:1811.04852 and 1811.04909 (merged).","DOI":"10.4230\/LIPIcs.ISAAC.2020.47"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan, and Seth Lloyd. ``Quantum-inspired algorithms in practice''. Quantum 4, 307 (2020). arXiv:1905.10415.","DOI":"10.22331\/q-2020-08-13-307"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Ewin Tang. ``Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions''. Physical Review Letters 127, 060503 (2021). arXiv:1811.00414.","DOI":"10.1103\/PhysRevLett.127.060503"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, and Leonard Wossnig. ``Quantum machine learning: a classical perspective''. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 474, 20170551 (2018). arXiv:1707.08561.","DOI":"10.1098\/rspa.2017.0551"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Srinivasan Arunachalam, Vlad Gheorghiu, Tomas Jochym-O'Connor, Michele Mosca, and Priyaa Varshinee Srinivasan. ``On the robustness of bucket brigade quantum RAM''. New Journal of Physics 17, 123010 (2015). arXiv:1502.03450.","DOI":"10.1088\/1367-2630\/17\/12\/123010"},{"key":"22","unstructured":"Neha Gupta and Aaron Sidford. ``Exploiting numerical sparsity for efficient learning: Faster eigenvector computation and regression''. In Advances in Neural Information Processing Systems. Pages 5269\u20135278. (2018). arXiv:1811.10866."},{"key":"23","doi-asserted-by":"publisher","unstructured":"Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. ``Coordinate methods for matrix games''. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). Pages 283\u2013293. IEEE (2020). arXiv:2009.08447.","DOI":"10.1109\/focs46700.2020.00035"},{"key":"24","doi-asserted-by":"publisher","unstructured":"S\u00e9bastien Bubeck. ``Convex optimization: Algorithms and complexity''. Foundations and Trends in Machine Learning 8, 231\u2013357 (2015). arXiv:1405.4980.","DOI":"10.1561\/2200000050"},{"key":"25","unstructured":"Roy Frostig, Rong Ge, Sham Kakade, and Aaron Sidford. ``Un-regularizing: Approximate proximal point and faster stochastic algorithms for empirical risk minimization''. In International Conference on Machine Learning. Pages 2540\u20132548. (2015). arXiv:1506.07512."},{"key":"26","unstructured":"Francis Bach and Eric Moulines. ``Non-asymptotic analysis of stochastic approximation algorithms for machine learning''. In Advances in Neural Information Processing Systems. Pages 451\u2013459. (2011). url: http:\/\/papers.nips.cc\/paper\/4316-non-asymptotic-analysis-of-stochastic-approximation-algorithms-for-machine-learning.pdf."},{"key":"27","unstructured":"Andr\u00e1s Gily\u00e9n, Seth Lloyd, and Ewin Tang. ``Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension'' (2018). arXiv:1811.04909."},{"key":"28","unstructured":"Nai-Hui Chia, Han-Hsuan Lin, and Chunhao Wang. ``Quantum-inspired sublinear classical algorithms for solving low-rank linear systems'' (2018). arXiv:1811.04852."},{"key":"29","doi-asserted-by":"publisher","unstructured":"David P. Woodruff. ``Sketching as a tool for numerical linear algebra''. Foundations and Trends in Theoretical Computer Science 10, 1\u2013157 (2014).","DOI":"10.1561\/0400000060"},{"key":"30","unstructured":"Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, Honghao Lin, and David P. Woodruff. ``Quantum-inspired algorithms from randomized numerical linear algebra'' (2020). arXiv:2011.04125."},{"key":"31","unstructured":"Changpeng Shao and Ashley Montanaro. ``Faster quantum-inspired algorithms for solving linear systems'' (2021). arXiv:2103.10309."},{"key":"32","doi-asserted-by":"publisher","unstructured":"Thomas Strohmer and Roman Vershynin. ``A randomized Kaczmarz algorithm with exponential convergence''. Journal of Fourier Analysis and Applications 15, 262\u2013278 (2008). arXiv:math\/0702226.","DOI":"10.1007\/s00041-008-9030-4"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Deanna Needell, Nathan Srebro, and Rachel Ward. ``Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm''. Mathematical Programming 155, 549\u2013573 (2015). arXiv:1310.5715.","DOI":"10.1007\/s10107-015-0864-7"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Petros Drineas, Ravi Kannan, and Michael W Mahoney. ``Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix''. SIAM Journal on Computing 36, 158\u2013183 (2006).","DOI":"10.1137\/S0097539704442696"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-06-30-754\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T13:04:13Z","timestamp":1656594253000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-06-30-754\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,30]]},"references-count":35,"URL":"https:\/\/doi.org\/10.22331\/q-2022-06-30-754","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,30]]},"article-number":"754"}}