An improved quantum-inspired algorithm for linear regression
1Alfréd Rényi Institute of Mathematics
2Adobe Research
3University 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
► BibTeX data
► 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] Ashley Montanaro and Changpeng Shao, "Quantum communication complexity of linear regression", ACM Transactions on Computation Theory 3625225 (2023).
[2] 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).
[3] 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).
[4] Kei Majima and Naoko Koide-Majima, "Quantum-Inspired Algorithms for Accelerating Machine Learning", The Brain & Neural Networks 29 4, 186 (2022).
[5] 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).
[6] 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.
[7] Steven Herbert, "Quantum computing for data-centric engineering and science", Data-Centric Engineering 3, e36 (2022).
[8] Shantanav Chakraborty, Aditya Morolia, and Anurudh Peduri, "Quantum Regularized Least Squares", Quantum 7, 988 (2023).
[9] 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).
[10] Yeqi Gao, Zhao Song, Xin Yang, and Ruizhe Zhang, "Fast Quantum Algorithm for Attention Computation", arXiv:2307.08045, (2023).
[11] Adam Bouland, Wim van Dam, Hamed Joorati, Iordanis Kerenidis, and Anupam Prakash, "Prospects and challenges of quantum finance", arXiv:2011.06492, (2020).
[12] 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).
[13] 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).
[14] 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).
[15] Patrick Rall, "Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation", Quantum 5, 566 (2021).
[16] Iordanis Kerenidis and Anupam Prakash, "Quantum machine learning with subspace states", arXiv:2202.00054, (2022).
[17] 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).
[18] Changpeng Shao and Ashley Montanaro, "Faster quantum-inspired algorithms for solving linear systems", arXiv:2103.10309, (2021).
[19] Chenyi Zhang, Jiaqi Leng, and Tongyang Li, "Quantum algorithms for escaping from saddle points", Quantum 5, 529 (2021).
[20] 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).
[21] Qian Zuo and Tongyang Li, "Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems", arXiv:2307.06627, (2023).
[22] 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).
[23] 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).
[24] Zhao Song, Junze Yin, and Ruizhe Zhang, "Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters", arXiv:2311.14823, (2023).
[25] 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 2023-12-07 07:47:11) and SAO/NASA ADS (last updated successfully 2023-12-07 07:47:12). 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.