An improved quantum-inspired algorithm for linear regression

András Gilyén; Zhao Song; Ewin Tang

doi:10.22331/q-2022-06-30-754

An improved quantum-inspired algorithm for linear regression

András Gilyén¹, Zhao Song², and Ewin Tang³

¹Alfréd Rényi Institute of Mathematics
²Adobe Research
³University of Washington

Published:	2022-06-30, volume 6, page 754
Eprint:	arXiv:2009.07268v4
Doi:	https://doi.org/10.22331/q-2022-06-30-754
Citation:	Quantum 6, 754 (2022).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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$ is stored in a data structure applicable for QRAM-based state preparation.

Namely, suppose we are given an $A \in \mathbb{C}^{m\times n}$ with minimum non-zero singular value $\sigma$ which supports certain efficient $\ell_2$-norm importance sampling queries, along with a $b \in \mathbb{C}^m$. Then, for some $x \in \mathbb{C}^n$ satisfying $\|x – A^+b\| \leq \varepsilon\|A^+b\|$, we can output a measurement of $|x\rangle$ in the computational basis and output an entry of $x$ with classical algorithms that run in $\tilde{\mathcal{O}}\big(\frac{\|A\|_{\mathrm{F}}^6\|A\|^6}{\sigma^{12}\varepsilon^4}\big)$ and $\tilde{\mathcal{O}}\big(\frac{\|A\|_{\mathrm{F}}^6\|A\|^2}{\sigma^8\varepsilon^4}\big)$ time, respectively. This improves on previous "quantum-inspired" algorithms in this line of research by at least a factor of $\frac{\|A\|^{16}}{\sigma^{16}\varepsilon^2}$ [Chia, Gilyén, 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.

Featured image: The computational complexity of the prior best algorithm for quantum-inspired linear regression (as described in the abstract), by Chia, Gilyén, Li, Lin, Tang, Wang, alongside the complexity of the algorithm achieved in this work. Both algorithms work in more general settings (the prior work can be applied to a more robust notion of regression, and this work supports regularization), but restricting to this setting does not significantly affect the comparison.

Popular summary

In this work, we combine two powerful ideas: stochastic gradient descent and the "quantum-inspired" access model of vectors and matrices. Algorithms in this access model have been previously used to demonstrate that certain quantum machine learning algorithms cannot give exponential speedups, and faster algorithms in this model imply stronger barriers to quantum speedup. So, to analyze the potential for quantum speedup in machine learning, we study the problem of linear regression, or solving a linear system $Ax=b$. We notice that, in the quantum-inspired setting, the quantum-like operations we can perform enable us to efficiently sample gradients of $f(x) = \tfrac12\|Ax-b\|^2$ when the matrix $A$ is low rank. This fits nicely with stochastic gradient descent techniques, so we use them to develop much faster algorithms over prior work, which was bottlenecked by its use of costly singular value decompositions. We break through this barrier and obtain a quartic dependence on precision, making significant progress towards practically applicable quantum-inspired algorithms. Later, Shao and Montanaro showed that in certain cases, variants of stochastic gradient descent can run even faster, with quadratic dependence on precision.

► BibTeX data

@article{Gilyen2022improvedquantum,
  doi = {10.22331/q-2022-06-30-754},
  url = {https://doi.org/10.22331/q-2022-06-30-754},
  title = {An improved quantum-inspired algorithm for linear regression},
  author = {Gily{\'{e}}n, Andr{\'{a}}s and Song, Zhao and Tang, Ewin},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {754},
  month = jun,
  year = {2022}
}

► References

[1] John Preskill. ``Quantum Computing in the NISQ era and beyond''. Quantum 2, 79 (2018). arXiv:1801.00862.
https://doi.org/10.22331/q-2018-08-06-79
arXiv:1801.00862

[2] Andrew M Childs. ``Equation solving by simulation''. Nature Physics 5, 861–861 (2009).
https://doi.org/10.1038/nphys1473

[3] Scott Aaronson. ``Read the fine print''. Nature Physics 11, 291–293 (2015).
https://doi.org/10.1038/nphys3272

[4] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. ``Quantum machine learning''. Nature 549, 195–202 (2017). arXiv:1611.09347.
https://doi.org/10.1038/nature23474
arXiv:1611.09347

[5] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Physical Review Letters 103, 150502 (2009). arXiv:0811.3171.
https://doi.org/10.1103/PhysRevLett.103.150502
arXiv:0811.3171

[6] András Gilyén, 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–204. (2019). arXiv:1806.01838.
https://doi.org/10.1145/3313276.3316366
arXiv:1806.01838

[7] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. ``Quantum random access memory''. Physical Review Letters 100, 160501 (2008). arXiv:0708.1879.
https://doi.org/10.1103/PhysRevLett.100.160501
arXiv:0708.1879

[8] 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.
https://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-211.pdf

[9] Nai-Hui Chia, András Gilyén, 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–400. (2020). arXiv:1910.06151.
https://doi.org/10.1145/3357713.3384314
arXiv:1910.06151

[10] Iordanis Kerenidis and Anupam Prakash. ``Quantum recommendation systems''. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS). Pages 49:1–49:21. (2017). arXiv:1603.08675.
https://doi.org/10.4230/LIPIcs.ITCS.2017.49
arXiv:1603.08675

[11] 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–228. (2019). arXiv:1807.04271.
https://doi.org/10.1145/3313276.3316310
arXiv:1807.04271

[12] 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.
arXiv:1812.03584

[13] Iordanis Kerenidis and Anupam Prakash. ``Quantum gradient descent for linear systems and least squares''. Physical Review A 101, 022316 (2020). arXiv:1704.04992.
https://doi.org/10.1103/PhysRevA.101.022316
arXiv:1704.04992

[14] Danial Dervovic, Mark Herbster, Peter Mountney, Simone Severini, Naïri Usher, and Leonard Wossnig. ``Quantum linear systems algorithms: a primer'' (2018). arXiv:1802.08227.
arXiv:1802.08227

[15] Leonard Wossnig, Zhikuan Zhao, and Anupam Prakash. ``Quantum linear system algorithm for dense matrices''. Physical Review Letters 120, 050502 (2018). arXiv:1704.06174.
https://doi.org/10.1103/PhysRevLett.120.050502
arXiv:1704.06174

[16] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. ``Quantum support vector machine for big data classification''. Physical Review Letters 113, 130503 (2014). arXiv:1307.0471.
https://doi.org/10.1103/PhysRevLett.113.130503
arXiv:1307.0471

[17] Shantanav Chakraborty, András Gilyén, 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–33:14. (2019). arXiv:1804.01973.
https://doi.org/10.4230/LIPIcs.ICALP.2019.33
arXiv:1804.01973

[18] Nai-Hui Chia, András Gilyén, 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–47:17. (2020). arXiv:1811.04852 and 1811.04909 (merged).
https://doi.org/10.4230/LIPIcs.ISAAC.2020.47
arXiv:1811.04852 and 1811.04909 (merged)

[19] Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan, and Seth Lloyd. ``Quantum-inspired algorithms in practice''. Quantum 4, 307 (2020). arXiv:1905.10415.
https://doi.org/10.22331/q-2020-08-13-307
arXiv:1905.10415

[20] 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.
https://doi.org/10.1103/PhysRevLett.127.060503
arXiv:1811.00414

[21] 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.
https://doi.org/10.1098/rspa.2017.0551
arXiv:1707.08561

[22] 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.
https://doi.org/10.1088/1367-2630/17/12/123010
arXiv:1502.03450

[23] 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–5278. (2018). arXiv:1811.10866.
arXiv:1811.10866

[24] 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–293. IEEE (2020). arXiv:2009.08447.
https://doi.org/10.1109/focs46700.2020.00035
arXiv:2009.08447

[25] Sébastien Bubeck. ``Convex optimization: Algorithms and complexity''. Foundations and Trends in Machine Learning 8, 231–357 (2015). arXiv:1405.4980.
https://doi.org/10.1561/2200000050
arXiv:1405.4980

[26] 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–2548. (2015). arXiv:1506.07512.
arXiv:1506.07512

[27] Francis Bach and Eric Moulines. ``Non-asymptotic analysis of stochastic approximation algorithms for machine learning''. In Advances in Neural Information Processing Systems. Pages 451–459. (2011). url: http://papers.nips.cc/paper/4316-non-asymptotic-analysis-of-stochastic-approximation-algorithms-for-machine-learning.pdf.
http://papers.nips.cc/paper/4316-non-asymptotic-analysis-of-stochastic-approximation-algorithms-for-machine-learning.pdf

[28] András Gilyén, Seth Lloyd, and Ewin Tang. ``Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension'' (2018). arXiv:1811.04909.
arXiv:1811.04909

[29] Nai-Hui Chia, Han-Hsuan Lin, and Chunhao Wang. ``Quantum-inspired sublinear classical algorithms for solving low-rank linear systems'' (2018). arXiv:1811.04852.
arXiv:1811.04852

[30] David P. Woodruff. ``Sketching as a tool for numerical linear algebra''. Foundations and Trends in Theoretical Computer Science 10, 1–157 (2014).
https://doi.org/10.1561/0400000060

[31] 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.
arXiv:2011.04125

[32] Changpeng Shao and Ashley Montanaro. ``Faster quantum-inspired algorithms for solving linear systems'' (2021). arXiv:2103.10309.
arXiv:2103.10309

[33] Thomas Strohmer and Roman Vershynin. ``A randomized Kaczmarz algorithm with exponential convergence''. Journal of Fourier Analysis and Applications 15, 262–278 (2008). arXiv:math/0702226.
https://doi.org/10.1007/s00041-008-9030-4
arXiv:math/0702226

[34] Deanna Needell, Nathan Srebro, and Rachel Ward. ``Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm''. Mathematical Programming 155, 549–573 (2015). arXiv:1310.5715.
https://doi.org/10.1007/s10107-015-0864-7
arXiv:1310.5715

[35] 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–183 (2006).
https://doi.org/10.1137/S0097539704442696

Cited by

[1] Manuel H. Muñoz-Arias, Stefanos Kourtis, and Alexandre Blais, "Low-depth Clifford circuits approximately solve MaxCut", Physical Review Research 6 2, 023294 (2024).

[2] Ashley Montanaro and Changpeng Shao, "Quantum Communication Complexity of Linear Regression", ACM Transactions on Computation Theory 16 1, 1 (2024).

[3] Kamaleswari Pandurangan, A. Priyadharshini, Rakheeba Taseen, B. Galebathullah, Haseeba Yaseen, and P. Ravichandran, Advances in Mechatronics and Mechanical Engineering 79 (2024) ISBN:9798369370766.

[4] Nikhil S. Mande and Changpeng Shao, "Lower bounds for quantum-inspired classical algorithms via communication complexity", Quantum 9, 1593 (2025).

[5] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan, "Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications", Physical Review Letters 129 23, 230504 (2022).

[6] Youde Dong, Haoran Zheng, and Jiehua Zhu, "A narrative review on quantum finance theory", International Journal of Quantum Information 22 06, 2450016 (2024).

[7] Quynh T. Nguyen, Bobak T. Kiani, and Seth Lloyd, "Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra", Quantum 6, 876 (2022).

[8] Jérémie Gince, Jean-Michel Pagé, Marco Armenta, Ayana Sarkar, and Stefanos Kourtis, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 1672 (2024) ISBN:979-8-3315-4137-8.

[9] Yuchun Li, Mohammad Khishe, Halmat Ayub, and Aseel Smerat, "Quantum‐Inspired Chimp Optimizer Evolving Kernel Extreme Learning Machine for Financial Risk Prediction: A Case Study on Bankruptcy", Journal of Forecasting for.70171 (2026).

[10] Xuyang Guo, Jun Dai, and Roman V Krems, "Benchmarking of quantum fidelity kernels for Gaussian process regression", Machine Learning: Science and Technology 5 3, 035081 (2024).

[11] Kei Majima and Naoko Koide-Majima, "Quantum-Inspired Algorithms for Accelerating Machine Learning", The Brain & Neural Networks 29 4, 186 (2022).

[12] Shantanav Chakraborty, "Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers", Quantum 8, 1496 (2024).

[13] Mina Doosti, Petros Wallden, Conor Brian Hamill, Robert Hankache, Oliver Thomson Brown, and Chris Heunen, "A brief review of quantum machine learning techniques for financial services", Machine Learning: Science and Technology 7 2, 021002 (2026).

[14] Jehn-Ruey Jiang, 2023 IEEE 5th Eurasia Conference on IOT, Communication and Engineering (ECICE) 301 (2023) ISBN:979-8-3503-1469-4.

[15] Shantanav Chakraborty, Aditya Morolia, and Anurudh Peduri, "Quantum Regularized Least Squares", Quantum 7, 988 (2023).

[16] Ye-Eun Jang, Na-Yeon Kim, and Young-Jin Kim, "Review of Applications of Quantum Computing in Power Flow Calculation", Journal of Electrical Engineering & Technology 19 2, 877 (2024).

[17] David K. Ferry, Synthesis Lectures on Engineering, Science, and Technology 177 (2025) ISBN:978-3-031-62924-2.

[18] Patrick Rebentrost and Seth Lloyd, "Quantum Computational Finance: Quantum Algorithm for Portfolio Optimization", KI - Künstliche Intelligenz 38 4, 327 (2024).

[19] Emmanuel Zambrini Cruzeiro, Christine De Mol, Serge Massar, and Stefano Pironio, "Quantum-inspired classification based on quantum state discrimination", Quantum Machine Intelligence 6 2, 79 (2024).

[20] Yunting Li, Xiaopeng Cui, Zhaoping Xiong, Zuoheng Zou, Bowen Liu, Bi-Ying Wang, Runqiu Shu, Huangjun Zhu, Nan Qiao, and Man-Hong Yung, "Efficient molecular conformation generation with quantum-inspired algorithm", Journal of Molecular Modeling 30 7, 228 (2024).

[21] Santiago Cifuentes, Samson Wang, Thais L. Silva, Mario Berta, and Leandro Aolita, "Quantum Computational Complexity of Matrix Functions", PRX Quantum 7 2, 020364 (2026).

[22] ZHANG Xin, GUO GongDe, YU ChaoHua, and LIN Song, "Quantum nonlinear dimensionality reduction based on maximum variance unfolding", SCIENTIA SINICA Physica, Mechanica & Astronomica 54 12, 120312 (2024).

[23] Roberto Giuntini, Andrés Camilo Granda Arango, Hector Freytes, Federico Hernan Holik, and Giuseppe Sergioli, "Multi-class classification based on quantum state discrimination", Fuzzy Sets and Systems 467, 108509 (2023).

[24] Vinooth Rao Kulkarni, Daniel Chen, Shuai Xu, Qiang Guan, and Vipin Chaudhary, Smart Innovation, Systems and Technologies 333, 29 (2023) ISBN:978-981-19-8093-0.

[25] Steven Herbert, "Quantum computing for data-centric engineering and science", Data-Centric Engineering 3, e36 (2022).

[26] Paul Beame, Niels Kornerup, and Michael Whitmeyer, "Quantum Time-Space Tradeoffs for Matrix Problems", SIAM Journal on Computing 55 3, 469 (2026).

[27] Samson Wang, Sam McArdle, and Mario Berta, "Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra", PRX Quantum 5 2, 020324 (2024).

[28] Suchitra Labhane, J. Radha, Kiran Sree Pokkuluri, R. Somasundaram, R. Shiva Shankar, and Prateek Srivastava, Advances in Computational Intelligence and Robotics 13 (2024) ISBN:9798369358320.

[29] Manoranjan Gandhudi, P. J. A. Alphonse, and G. R. Gangadharan, Uncertainty and Operations Research 181 (2026) ISBN:978-981-95-2428-0.

[30] Shreeya Sanjeev Gokhale, Rishit Ravi Dhote, and Radhakrishnan Delhibabu, "A review of quantum machine learning algorithms, applications, and emerging advantages", Discover Computing 29 1, 226 (2026).

[31] Xiao-Fan Xu, Xi-Ning Zhuang, Cheng Xue, Zhao-Yun Chen, Yu-Chun Wu, and Guo-Ping Guo, "An efficient quantum algorithm for independent component analysis", New Journal of Physics 26 7, 073030 (2024).

[32] François Le Gall, "Robust Dequantization of the Quantum Singular Value Transformation and Quantum Machine Learning Algorithms", computational complexity 34 1, 2 (2025).

[33] Paul Beame, Niels Kornerup, and Michael Whitmeyer, Proceedings of the 56th Annual ACM Symposium on Theory of Computing 596 (2024) ISBN:9798400703836.

[34] Ahmad Alomari and Sathish A. P. Kumar, 2025 IEEE 7th International Conference on Cognitive Machine Intelligence (CogMI) 352 (2025) ISBN:979-8-3315-9205-9.

[35] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

[36] Adam Bouland, Wim van Dam, Hamed Joorati, Iordanis Kerenidis, and Anupam Prakash, "Prospects and challenges of quantum finance", arXiv:2011.06492, (2020).

[37] Xuyang Guo, Zhao Song, Xin Yang, and Ruizhe Zhang, "Beyond Classical Attention: Quantum Attention for Scalable Computation", arXiv:2307.08045, (2023).

[38] Travis L. Scholten, Carl J. Williams, Dustin Moody, Michele Mosca, William Hurley, William J. Zeng, Matthias Troyer, and Jay M. Gambetta, "Assessing the Benefits and Risks of Quantum Computers", arXiv:2401.16317, (2024).

[39] Iordanis Kerenidis and Anupam Prakash, "Quantum machine learning with subspace states", arXiv:2202.00054, (2022).

[40] Patrick Rall, "Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation", Quantum 5, 566 (2021).

[41] Sevag Gharibian and François Le Gall, "Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture", arXiv:2111.09079, (2021).

[42] Lvzhou Li and Jingquan Luo, "Nearly Optimal Circuit Size for Sparse Quantum State Preparation", arXiv:2406.16142, (2024).

[43] Changpeng Shao and Ashley Montanaro, "Faster quantum-inspired algorithms for solving linear systems", arXiv:2103.10309, (2021).

[44] Bujiao Wu, Maharshi Ray, Liming Zhao, Xiaoming Sun, and Patrick Rebentrost, "Quantum-classical algorithms for skewed linear systems with an optimized Hadamard test", Physical Review A 103 4, 042422 (2021).

[45] Benjamin A. Cordier, Nicolas P. D. Sawaya, Gian G. Guerreschi, and Shannon K. McWeeney, "Biology and medicine in the landscape of quantum advantages", arXiv:2112.00760, (2021).

[46] Qian Zuo and Tongyang Li, "Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems", arXiv:2307.06627, (2023).

[47] Chenyi Zhang, Jiaqi Leng, and Tongyang Li, "Quantum algorithms for escaping from saddle points", Quantum 5, 529 (2021).

[48] Franco D. Albareti, Thomas Ankenbrand, Denis Bieri, Esther Hänggi, Damian Lötscher, Stefan Stettler, and Marcel Schöngens, "A Structured Survey of Quantum Computing for the Financial Industry", arXiv:2204.10026, (2022).

[49] Zhao Song, Junze Yin, and Ruizhe Zhang, "Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters", arXiv:2311.14823, (2023).

[50] Kazuya Kaneko, Koichi Miyamoto, Naoyuki Takeda, and Kazuyoshi Yoshino, "Linear regression by quantum amplitude estimation and its extension to convex optimization", Physical Review A 104 2, 022430 (2021).

[51] Yunting Li, Xiaopeng Cui, Zhaoping Xiong, Zuoheng Zou, Bowen Liu, Bi-Ying Wang, Runqiu Shu, Huangjun Zhu, Nan Qiao, and Man-Hong Yung, "Efficient molecular conformation generation with quantum-inspired algorithm", arXiv:2404.14101, (2024).

[52] Nikhil S. Mande and Changpeng Shao, "Lower bounds for quantum-inspired classical algorithms via communication complexity", arXiv:2402.15686, (2024).

[53] Amirhossein Nourbakhsh, Mark Nicholas Jones, Kaur Kristjuhan, Deborah Carberry, Jay Karon, Christian Beenfeldt, Kyarash Shahriari, Martin P. Andersson, Mojgan A. Jadidi, and Seyed Soheil Mansouri, "Quantum Computing: Fundamentals, Trends and Perspectives for Chemical and Biochemical Engineers", arXiv:2201.02823, (2022).

[54] Jonathan Weare and Robert J. Webber, "Randomly sparsified Richardson iteration: A dimension-independent sparse linear solver", arXiv:2309.17270, (2023).

[55] Tyler Chen, Junhyung Lyle Kim, Archan Ray, Shouvanik Chakrabarti, Dylan Herman, and Niraj Kumar, "A simple analysis of a quantum-inspired algorithm for solving low-rank linear systems", arXiv:2508.13108, (2025).

[56] Daniel Chen, Yekun Xu, Betis Baheri, Samuel A. Stein, Chuan Bi, Ying Mao, Qiang Quan, and Shuai Xu, "Quantum-Inspired Classical Algorithm for Slow Feature Analysis", arXiv:2012.00824, (2020).

[57] Ebrahim Ardeshir-Larijani, "Parametrized Complexity of Quantum Inspired Algorithms", arXiv:2112.11686, (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-17 15:19:29) and SAO/NASA ADS (last updated successfully 2026-08-17 15:19:30). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.