Quantum Algorithms for the Pathwise Lasso

Joao F. Doriguello; Debbie Lim; Chi Seng Pun; Patrick Rebentrost; Tushar Vaidya

doi:10.22331/q-2025-03-25-1674

Quantum Algorithms for the Pathwise Lasso

Joao F. Doriguello^1,2, Debbie Lim^2,3, Chi Seng Pun⁴, Patrick Rebentrost^2,5, and Tushar Vaidya⁴

¹HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary
²Centre for Quantum Technologies, National University of Singapore, Singapore
³Center for Quantum Computer Science, Faculty of Computing, University of Latvia, Latvia
⁴School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore
⁵Department of Computer Science, National University of Singapore, Singapore

Published:	2025-03-25, volume 9, page 1674
Editor:	Yu Tong
Eprint:	arXiv:2312.14141v3
Doi:	https://doi.org/10.22331/q-2025-03-25-1674
Citation:	Quantum 9, 1674 (2025).

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

Abstract

We present a novel quantum high-dimensional linear regression algorithm with an $\ell_1$-penalty based on the classical LARS (Least Angle Regression) pathwise algorithm. Similarly to available classical algorithms for Lasso, our quantum algorithm provides the full regularisation path as the penalty term varies, but quadratically faster per iteration under specific conditions. A quadratic speedup on the number of features $d$ is possible by using the simple quantum minimum-finding subroutine from Dürr and Hoyer (arXiv'96) in order to obtain the joining time at each iteration. We then improve upon this simple quantum algorithm and obtain a quadratic speedup both in the number of features $d$ and the number of observations $n$ by using the approximate quantum minimum-finding subroutine from Chen and de Wolf (ICALP'23). In order to do so, we approximately compute the joining times to be searched over by the approximate quantum minimum-finding subroutine. As another main contribution, we prove, via an approximate version of the KKT conditions and a duality gap, that the LARS algorithm (and therefore our quantum algorithm) is robust to errors. This means that it still outputs a path that minimises the Lasso cost function up to a small error if the joining times are only approximately computed. Furthermore, we show that, when the observations are sampled from a Gaussian distribution, our quantum algorithm's complexity only depends polylogarithmically on $n$, exponentially better than the classical LARS algorithm, while keeping the quadratic improvement on $d$. Moreover, we propose a dequantised version of our quantum algorithm that also retains the polylogarithmic dependence on $n$, albeit presenting the linear scaling on $d$ from the standard LARS algorithm. Finally, we prove query lower bounds for classical and quantum Lasso algorithms.

Multimedia: Quantum Algorithms for the Pathwise Lasso – Tushar Vaidya, QTML 2024 Conference at University of Melbourne

Popular summary

LASSO, which stands for Least Absolute Shrinkage and Selection operator, is a regression problem with a 1-norm penalty term. LASSO is a very popular tool in extracting a sparse and easy-to-digest description of a data set, specially for problems in which there are too many variables and very few data points. There are several algorithms to solve LASSO, one of the most popular ones being the classical LARS (Least Angle Regression) pathwise algorithm, which returns the full solution path as the penalty term varies. Here in this work we propose a quantum version of the standard LARS algorithm that is quadratically faster per iteration and, in some cases, even exponentially better in some parameters.

► BibTeX data

@article{Doriguello2025quantumalgorithms,
  doi = {10.22331/q-2025-03-25-1674},
  url = {https://doi.org/10.22331/q-2025-03-25-1674},
  title = {Quantum {A}lgorithms for the {P}athwise {L}asso},
  author = {Doriguello, Joao F. and Lim, Debbie and Pun, Chi Seng and Rebentrost, Patrick and Vaidya, Tushar},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1674},
  month = mar,
  year = {2025}
}

► References

[1] Jonathan Allcock, Jinge Bao, Joao F. Doriguello, Alessandro Luongo, and Miklos Santha. Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates. Quantum, 8:1530, November 2024. doi:10.22331/q-2024-11-20-1530.
https://doi.org/10.22331/q-2024-11-20-1530

[2] Muhammad Asim, Max Daniels, Oscar Leong, Ali Ahmed, and Paul Hand. Invertible generative models for inverse problems: mitigating representation error and dataset bias. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 399–409. PMLR, 13–18 Jul 2020. URL: https://proceedings.mlr.press/v119/asim20a.html.
https://proceedings.mlr.press/v119/asim20a.html

[3] Greg W. Anderson, Alice Guionnet, and Ofer Zeitouni. An Introduction to Random Matrices. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2009. doi:10.1017/CBO9780511801334.
https://doi.org/10.1017/CBO9780511801334

[4] Joran Van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-solvers: Better upper and lower bounds. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 403–414, 2017. doi:10.1109/FOCS.2017.44.
https://doi.org/10.1109/FOCS.2017.44

[5] Taylor B. Arnold and Ryan J. Tibshirani. Efficient implementations of the generalized lasso dual path algorithm. Journal of Computational and Graphical Statistics, 25(1):1–27, 2016. doi:10.1080/10618600.2015.1008638.
https://doi.org/10.1080/10618600.2015.1008638

[6] Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders. Efficient quantum algorithms for simulating sparse Hamiltonians. Communications in Mathematical Physics, 270(2):359–371, Mar 2007. doi:10.1007/s00220-006-0150-x.
https://doi.org/10.1007/s00220-006-0150-x

[7] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Exponential improvement in precision for simulating sparse Hamiltonians. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC '14, page 283–292, New York, NY, USA, 2014. Association for Computing Machinery. doi:10.1145/2591796.2591854.
https://doi.org/10.1145/2591796.2591854

[8] Armando Bellante. Quantum algorithms for sparse recovery and machine learning. PhD thesis, Politecnico di Milano, 2024. URL: https://hdl.handle.net/10589/228972.
https://hdl.handle.net/10589/228972

[9] Mohsen Bayati, Murat A. Erdogdu, and Andrea Montanari. Estimating lasso risk and noise level. In Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 1, NIPS'13, page 944–952, Red Hook, NY, USA, 2013. Curran Associates Inc. URL: https://dl.acm.org/doi/abs/10.5555/2999611.2999717.
https://dl.acm.org/doi/abs/10.5555/2999611.2999717

[10] Peter Bühlmann and Sara van de Geer Statistics for high-dimensional data: methods, theory and applications. Springer Science & Business Media, 2011. doi:10.1007/978-3-642-20192-9.
https://doi.org/10.1007/978-3-642-20192-9

[11] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53–74, 2002. doi:10.1090/conm/305/05215.
https://doi.org/10.1090/conm/305/05215

[12] Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G. Dimakis. Compressed sensing using generative models. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 537–546. PMLR, 06–11 Aug 2017. URL: https://proceedings.mlr.press/v70/bora17a.html.
https://proceedings.mlr.press/v70/bora17a.html

[13] Jonathan Borwein and Adrian Lewis. Convex Analysis. Springer, 2006. doi:10.1007/978-0-387-31256-9.
https://doi.org/10.1007/978-0-387-31256-9

[14] Giorgos Borboudakis and Ioannis Tsamardinos. Forward-backward selection with early dropping. Journal of Machine Learning Research, 20(8):1–39, 2019. URL: http://jmlr.org/papers/v20/17-334.html.
http://jmlr.org/papers/v20/17-334.html

[15] Armando Bellante and Stefano Zanero. Quantum matching pursuit: A quantum algorithm for sparse representations. Phys. Rev. A, 105:022414, Feb 2022. doi:10.1103/PhysRevA.105.022414.
https://doi.org/10.1103/PhysRevA.105.022414

[16] Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders. Atomic decomposition by basis pursuit. SIAM Review, 43(1):129–159, 2001. doi:10.1137/S003614450037906X.
https://doi.org/10.1137/S003614450037906X

[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 Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1–33:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2019.33.
https://doi.org/10.4230/LIPIcs.ICALP.2019.33

[18] Shantanav Chakraborty, Aditya Morolia, and Anurudh Peduri. Quantum Regularized Least Squares. Quantum, 7:988, April 2023. doi:10.22331/q-2023-04-27-988.
https://doi.org/10.22331/q-2023-04-27-988

[19] Emmanuel J. Candès and Yaniv Plan. Near-ideal model selection by $\ell_1$ minimization. The Annals of Statistics, 37(5A):2145 – 2177, 2009. doi:10.1214/08-AOS653.
https://doi.org/10.1214/08-AOS653

[20] Mei Choi Chiu, Chi Seng Pun, and Hoi Ying Wong. Big data challenges of high-dimensional continuous-time mean-variance portfolio selection and a remedy. Risk Analysis, 37(8):1532–1549, 2017. doi:10.1111/risa.12801.
https://doi.org/10.1111/risa.12801

[21] Emmanuel J. Candès, Justin K. Romberg, and Terence Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics, 59(8):1207–1223, 2006. doi:10.1002/cpa.20124.
https://doi.org/10.1002/cpa.20124

[22] Alex Coad and Stjepan Srhoj. Catching Gazelles with a Lasso: Big data techniques for the prediction of high-growth firms. Small Business Economics, 55(3):541–565, Oct 2020. doi:10.1007/s11187-019-00203-3.
https://doi.org/10.1007/s11187-019-00203-3

[23] Emmanuel J. Candès, Michael B. Wakin, and Stephen P. Boyd. Enhancing sparsity by reweighted $\ell_1$ minimization. Journal of Fourier Analysis and Applications, 14(5):877–905, Dec 2008. doi:10.1007/s00041-008-9045-x.
https://doi.org/10.1007/s00041-008-9045-x

[24] Yanlin Chen and Ronald de Wolf. Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1–38:21, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2023.38.
https://doi.org/10.4230/LIPIcs.ICALP.2023.38

[25] Menghan Chen, Chaohua Yu, Gongde Guo, and Song Lin. Faster quantum ridge regression algorithm for prediction. International Journal of Machine Learning and Cybernetics, 14(1):117–124, Jan 2023. doi:10.1007/s13042-022-01526-6.
https://doi.org/10.1007/s13042-022-01526-6

[26] Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum. arXiv preprint quant-ph/9607014, 1996. doi:10.48550/arXiv.quant-ph/9607014.
https://doi.org/10.48550/arXiv.quant-ph/9607014
arXiv:quant-ph/9607014

[27] D. L. Donoho and X. Huo. Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inf. Theor., 47(7):2845–2862, sep 2006. doi:10.1109/18.959265.
https://doi.org/10.1109/18.959265

[28] Abhimanyu Das and David Kempe. Algorithms for subset selection in linear regression. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC '08, page 45–54, New York, NY, USA, 2008. Association for Computing Machinery. doi:10.1145/1374376.1374384.
https://doi.org/10.1145/1374376.1374384

[29] David L. Donoho. For most large underdetermined systems of linear equations the minimal $\ell_1$-norm solution is also the sparsest solution. Communications on Pure and Applied Mathematics, 59(6):797–829, 2006. doi:10.1002/cpa.20132.
https://doi.org/10.1002/cpa.20132

[30] A.V. Dorugade. New ridge parameters for ridge regression. Journal of the Association of Arab Universities for Basic and Applied Sciences, 15:94–99, 2014. doi:10.1016/j.jaubas.2013.03.005.
https://doi.org/10.1016/j.jaubas.2013.03.005

[31] Charles Dossal. A necessary and sufficient condition for exact sparse recovery by $\ell_1$ minimization. Comptes Rendus Mathematique, 350(1):117–120, 2012. doi:10.1016/j.crma.2011.12.014.
https://doi.org/10.1016/j.crma.2011.12.014

[32] M. Elad and A.M. Bruckstein. A generalized uncertainty principle and sparse representation in pairs of bases. IEEE Transactions on Information Theory, 48(9):2558–2567, 2002. doi:10.1109/TIT.2002.801410.
https://doi.org/10.1109/TIT.2002.801410

[33] Bradley Efron, Trevor Hastie, Iain Johnstone, and Robert Tibshirani. Least angle regression. The Annals of Statistics, 32(2):407 – 499, 2004. doi:10.1214/009053604000000067.
https://doi.org/10.1214/009053604000000067

[34] Jerome Friedman, Trevor Hastie, and Rob Tibshirani. Regularization paths for generalized linear models via coordinate descent. J Stat Softw, 33(1):1–22, 2010. doi:10.18637/jss.v033.i01.
https://doi.org/10.18637/jss.v033.i01

[35] Jerome Friedman, Trevor Hastie, and Robert Tibshirani. A note on the group lasso and a sparse group lasso. arXiv preprint arXiv:1001.0736, 2010. doi:10.48550/arXiv.1001.0736.
https://doi.org/10.48550/arXiv.1001.0736
arXiv:1001.0736

[36] Jianqing Fan and Jinchi Lv. A selective overview of variable selection in high dimensional feature space. Statistica Sinica, 20(1):101, 2010. URL: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3092303/.
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3092303/

[37] Mário A. T. Figueiredo, Robert D. Nowak, and Stephen J. Wright. Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems. IEEE Journal of Selected Topics in Signal Processing, 1(4):586–597, 2007. doi:10.1109/JSTSP.2007.910281.
https://doi.org/10.1109/JSTSP.2007.910281

[38] Simon Foucart and Holger Rauhut. An Invitation to Compressive Sensing, pages 1–39. Springer New York, New York, NY, 2013. doi:10.1007/978-0-8176-4948-7_1.
https://doi.org/10.1007/978-0-8176-4948-7_1

[39] J.-J. Fuchs. Recovery of exact sparse representations in the presence of noise. In 2004 IEEE International Conference on Acoustics, Speech, and Signal Processing, volume 2, pages ii–533, 2004. doi:10.1109/ICASSP.2004.1326312.
https://doi.org/10.1109/ICASSP.2004.1326312

[40] J.J. Fuchs. Recovery of exact sparse representations in the presence of bounded noise. IEEE Transactions on Information Theory, 51(10):3601–3608, 2005. doi:10.1109/TIT.2005.855614.
https://doi.org/10.1109/TIT.2005.855614

[41] Pierre J. Garrigues and Laurent El Ghaoui. An homotopy algorithm for the lasso with online observations. In Proceedings of the 21st International Conference on Neural Information Processing Systems, NIPS'08, page 489–496, Red Hook, NY, USA, 2008. Curran Associates Inc. URL: https://dl.acm.org/doi/abs/10.5555/2981780.2981841.
https://dl.acm.org/doi/abs/10.5555/2981780.2981841

[42] Brian R. Gaines, Juhyun Kim, and Hua Zhou. Algorithms for fitting the constrained lasso. Journal of Computational and Graphical Statistics, 27(4):861–871, 2018. PMID: 30618485. doi:10.1080/10618600.2018.1473777.
https://doi.org/10.1080/10618600.2018.1473777

[43] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Architectures for a quantum random access memory. Phys. Rev. A, 78:052310, Nov 2008. doi:10.1103/PhysRevA.78.052310.
https://doi.org/10.1103/PhysRevA.78.052310

[44] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Phys. Rev. Lett., 100:160501, Apr 2008. doi:10.1103/PhysRevLett.100.160501.
https://doi.org/10.1103/PhysRevLett.100.160501

[45] 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 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 193–204, New York, NY, USA, 2019. Association for Computing Machinery. doi:10.1145/3313276.3316366.
https://doi.org/10.1145/3313276.3316366

[46] Steve R. Gunn. Support vector machines for classification and regression. Technical Report 1, University of Southampton, 1998. URL: https://svms.org/tutorials/Gunn1998.pdf.
https://svms.org/tutorials/Gunn1998.pdf

[47] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 103:150502, Oct 2009. doi:10.1103/PhysRevLett.103.150502.
https://doi.org/10.1103/PhysRevLett.103.150502

[48] Arthur E. Hoerl and Robert W. Kennard. Ridge regression: Biased estimation for nonorthogonal problems. Technometrics, 12(1):55–67, 1970. doi:10.1080/00401706.1970.10488634.
https://doi.org/10.1080/00401706.1970.10488634

[49] Arthur E. Hoerl, Robert W. Kannard, and Kent F. Baldwin. Ridge regression: some simulations. Communications in Statistics, 4(2):105–123, 1975. doi:10.1080/03610927508827232.
https://doi.org/10.1080/03610927508827232

[50] Jian Huang, Shuangge Ma, and Cun-Hui Zhang. Adaptive lasso for sparse high-dimensional regression models. Statistica Sinica, 18(4):1603–1618, 2008. URL: http://www.jstor.org/stable/24308572.
http://www.jstor.org/stable/24308572

[51] Holger Hoefling. A path algorithm for the fused lasso signal approximator. Journal of Computational and Graphical Statistics, 19(4):984–1006, 2010. doi:10.1198/jcgs.2010.09208.
https://doi.org/10.1198/jcgs.2010.09208

[52] Trevor Hastie, Robert Tibshirani, and Martin Wainwright. Statistical Learning with Sparsity: The Lasso and Generalizations. Chapman and Hall/CRC, May 2015. doi:10.1201/b18401.
https://doi.org/10.1201/b18401

[53] Samuel Jaques and Arthur G. Rattew. QRAM: A survey and critique. arXiv preprint arXiv:2305.10310, 2023. doi:10.48550/arXiv.2305.10310.
https://doi.org/10.48550/arXiv.2305.10310
arXiv:2305.10310

[54] Iain M. Johnstone and D. Michael Titterington. Statistical challenges of high-dimensional data. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 367(1906):4237–4253, 2009. doi:10.1098/rsta.2009.0159.
https://doi.org/10.1098/rsta.2009.0159

[55] B. M. Golam Kibria. Performance of some new ridge regression estimators. Communications in Statistics - Simulation and Computation, 32(2):419–435, 2003. doi:10.1081/SAC-120017499.
https://doi.org/10.1081/SAC-120017499

[56] Jinseog Kim, Yuwon Kim, and Yongdai Kim. A gradient-based optimization algorithm for LASSO. Journal of Computational and Graphical Statistics, 17(4):994–1009, 2008. doi:10.1198/106186008X386210.
https://doi.org/10.1198/106186008X386210

[57] Jonathan Kelner, Frederic Koehler, Raghu Meka, and Dhruv Rohatgi. Lower bounds on randomly preconditioned lasso via robust sparse designs. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 24419–24431. Curran Associates, Inc., 2022. URL: https://proceedings.neurips.cc/paper_files/paper/2022/file/9a8d52eb05eb7b13f54b3d9eada667b7-Paper-Conference.pdf.
https://proceedings.neurips.cc/paper_files/paper/2022/file/9a8d52eb05eb7b13f54b3d9eada667b7-Paper-Conference.pdf

[58] Vipin Kumar and Sonajharia Minz. Feature selection: a literature review. SmartCR, 4(3):211–229, 2014. doi:10.6029/smartcr.2014.03.007.
https://doi.org/10.6029/smartcr.2014.03.007

[59] Kazuya Kaneko, Koichi Miyamoto, Naoyuki Takeda, and Kazuyoshi Yoshino. Linear regression by quantum amplitude estimation and its extension to convex optimization. Phys. Rev. A, 104:022430, Aug 2021. doi:10.1103/PhysRevA.104.022430.
https://doi.org/10.1103/PhysRevA.104.022430

[60] Iordanis Kerenidis and Anupam Prakash. Quantum Recommendation Systems. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1–49:21, Dagstuhl, Germany, 2017. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2017.49.
https://doi.org/10.4230/LIPIcs.ITCS.2017.49

[61] Iordanis Kerenidis and Anupam Prakash. Quantum gradient descent for linear systems and least squares. Phys. Rev. A, 101:022316, Feb 2020. doi:10.1103/PhysRevA.101.022316.
https://doi.org/10.1103/PhysRevA.101.022316

[62] Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization. Quantum, 3:163, July 2019. doi:10.22331/q-2019-07-12-163.
https://doi.org/10.22331/q-2019-07-12-163

[63] Debbie Lim, João F Doriguello, and Patrick Rebentrost. Quantum algorithm for robust optimization via stochastic-gradient online learning. arXiv preprint arXiv:2304.02262, 2023. doi:10.48550/arXiv.2304.02262.
https://doi.org/10.48550/arXiv.2304.02262
arXiv:2304.02262

[64] Michel Ledoux. The Concentration of Measure Phenomenon. Mathematical surveys and monographs. American Mathematical Society, 2001. doi:10.1090/surv/089.
https://doi.org/10.1090/surv/089

[65] Seth Lloyd, Silvano Garnerone, and Paolo Zanardi. Quantum algorithms for topological and geometric analysis of data. Nature Communications, 7(1):10138, Jan 2016. doi:10.1038/ncomms10138.
https://doi.org/10.1038/ncomms10138

[66] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10(9):631–633, Sep 2014. doi:10.1038/nphys3029.
https://doi.org/10.1038/nphys3029

[67] Richard Lockhart, Jonathan Taylor, Ryan J. Tibshirani, and Robert Tibshirani. A significance test for the lasso. The Annals of Statistics, 42(2):413, 2014. doi:10.1214/13-AOS1175.
https://doi.org/10.1214/13-AOS1175

[68] K.Z. Mao. Fast orthogonal forward selection algorithm for feature subset selection. IEEE Transactions on Neural Networks, 13(5):1218–1224, 2002. doi:10.1109/TNN.2002.1031954.
https://doi.org/10.1109/TNN.2002.1031954

[69] K.Z. Mao. Orthogonal forward selection and backward elimination algorithms for feature subset selection. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 34(1):629–634, 2004. doi:10.1109/TSMCB.2002.804363.
https://doi.org/10.1109/TSMCB.2002.804363

[70] MathOverflow. Orthogonal projection $XX^+$ from random Gaussian matrix $X$, 2024. Accessed on 9th June 2024. URL: https://mathoverflow.net/questions/472759/.
https://mathoverflow.net/questions/472759/

[71] Nicolai Meinshausen and Peter Bühlmann. High-dimensional graphs and variable selection with the Lasso. The Annals of Statistics, 34(3):1436 – 1462, 2006. doi:10.1214/009053606000000281.
https://doi.org/10.1214/009053606000000281

[72] Gary C. McDonald. Ridge regression. WIREs Computational Statistics, 1(1):93–100, 2009. doi:10.1002/wics.14.
https://doi.org/10.1002/wics.14

[73] Elizabeth S. Meckes. The Random Matrix Theory of the Classical Compact Groups. Cambridge Tracts in Mathematics. Cambridge University Press, 2019. doi:10.1017/9781108303453.
https://doi.org/10.1017/9781108303453

[74] Carl D. Meyer, Jr. Generalized inversion of modified matrices. SIAM Journal on Applied Mathematics, 24(3):315–323, 1973. doi:10.1137/0124033.
https://doi.org/10.1137/0124033

[75] Xiangming Meng, Tomoyuki Obuchi, and Yoshiyuki Kabashima. On model selection consistency of lasso for high-dimensional ising models. In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 6783–6805. PMLR, 25–27 Apr 2023. URL: https://proceedings.mlr.press/v206/meng23a.html.
https://proceedings.mlr.press/v206/meng23a.html

[76] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, second edition, 2018. URL: https://mitpress.mit.edu/9780262039406/foundations-of-machine-learning/.
https://mitpress.mit.edu/9780262039406/foundations-of-machine-learning/

[77] Donald W. Marquardt and Ronald D. Snee. Ridge regression in practice. The American Statistician, 29(1):3–20, 1975. doi:10.1080/00031305.1975.10479105.
https://doi.org/10.1080/00031305.1975.10479105

[78] Vitali D. Milman and Gideon Schechtman. Asymptotic theory of finite dimensional normed spaces: Isoperimetric inequalities in Riemannian manifolds, volume 1200. Springer Science & Business Media, 1986. doi:10.1007/978-3-540-38822-7.
https://doi.org/10.1007/978-3-540-38822-7

[79] W. James Murdoch, Chandan Singh, Karl Kumbier, Reza Abbasi-Asl, and Bin Yu. Definitions, methods, and applications in interpretable machine learning. Proceedings of the National Academy of Sciences, 116(44):22071–22080, 2019. doi:10.1073/pnas.1900654116.
https://doi.org/10.1073/pnas.1900654116

[80] Julien Mairal and Bin Yu. Complexity analysis of the lasso regularization path. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML'12, page 1835–1842, Madison, WI, USA, 2012. Omnipress. URL: https://dl.acm.org/doi/10.5555/3042573.3042807.
https://dl.acm.org/doi/10.5555/3042573.3042807

[81] Michael R. Osborne, Brett Presnell, and Berwin A. Turlach. On the LASSO and its dual. Journal of Computational and Graphical Statistics, 9(2):319–337, 2000. doi:10.1080/10618600.2000.10474883.
https://doi.org/10.1080/10618600.2000.10474883

[82] MR Osborne, B Presnell, and BA Turlach. A new approach to variable selection in least squares problems. IMA Journal of Numerical Analysis, 20(3):389–403, 07 2000. doi:10.1093/imanum/20.3.389.
https://doi.org/10.1093/imanum/20.3.389

[83] Yiming Peng and Vadim Linetsky. Portfolio selection: A statistical learning approach. In Proceedings of the Third ACM International Conference on AI in Finance, ICAIF '22, page 257–263, New York, NY, USA, 2022. Association for Computing Machinery. doi:10.1145/3533271.3561707.
https://doi.org/10.1145/3533271.3561707

[84] Anupam Prakash. Quantum algorithms for linear algebra and machine learning. University of California, Berkeley, 2014. URL: https://escholarship.org/uc/item/5v9535q4.
https://escholarship.org/uc/item/5v9535q4

[85] John Preskill. Quantum Computing in the NISQ era and beyond. Quantum, 2:79, August 2018. doi:10.22331/q-2018-08-06-79.
https://doi.org/10.22331/q-2018-08-06-79

[86] Chi Seng Pun and Hoi Ying Wong. A linear programming model for selection of sparse high-dimensional multiperiod portfolios. European Journal of Operational Research, 273(2):754–771, 2019. doi:10.1016/j.ejor.2018.08.025.
https://doi.org/10.1016/j.ejor.2018.08.025

[87] Yihui Quek, Clement Canonne, and Patrick Rebentrost. Robust quantum minimum finding with an application to hypothesis selection. arXiv preprint arXiv:2003.11777, 2020. doi:10.48550/arXiv.2003.11777.
https://doi.org/10.48550/arXiv.2003.11777
arXiv:2003.11777

[88] Cynthia Rudin, Chaofan Chen, Zhi Chen, Haiyang Huang, Lesia Semenova, and Chudi Zhong. Interpretable machine learning: Fundamental principles and 10 grand challenges. Statistics Surveys, 16:1 – 85, 2022. doi:10.1214/21-SS133.
https://doi.org/10.1214/21-SS133

[89] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Phys. Rev. Lett., 113:130503, Sep 2014. doi:10.1103/PhysRevLett.113.130503.
https://doi.org/10.1103/PhysRevLett.113.130503

[90] Saharon Rosset. Following curved regularized optimization solution paths. In Proceedings of the 17th International Conference on Neural Information Processing Systems, NIPS'04, page 1153–1160, Cambridge, MA, USA, 2004. MIT Press. URL: https://proceedings.neurips.cc/paper_files/paper/2004/file/32b991e5d77ad140559ffb95522992d0-Paper.pdf.
https://proceedings.neurips.cc/paper_files/paper/2004/file/32b991e5d77ad140559ffb95522992d0-Paper.pdf

[91] V. Roth. The generalized LASSO. IEEE Transactions on Neural Networks, 15(1):16–28, 2004. doi:10.1109/TNN.2003.809398.
https://doi.org/10.1109/TNN.2003.809398

[92] Matthias Reif and Faisal Shafait. Efficient feature size reduction via predictive forward selection. Pattern Recognition, 47(4):1664–1673, 2014. doi:10.1016/j.patcog.2013.10.009.
https://doi.org/10.1016/j.patcog.2013.10.009

[93] Saharon Rosset and Ji Zhu. Piecewise linear regularized solution paths. The Annals of Statistics, 35(3):1012 – 1030, 2007. doi:10.1214/009053606000001370.
https://doi.org/10.1214/009053606000001370

[94] Karl Sjöstrand, Line Harder Clemmensen, Rasmus Larsen, Gudmundur Einarsson, and Bjarne Ersbøll. SpaSM: A MATLAB toolbox for sparse statistical modeling. Journal of Statistical Software, 84(10), 2018. doi:10.18637/jss.v084.i10.
https://doi.org/10.18637/jss.v084.i10

[95] Yang Song and Stefano Ermon. Improved techniques for training score-based generative models. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc. URL: https://dl.acm.org/doi/abs/10.5555/3495724.3496767.
https://dl.acm.org/doi/abs/10.5555/3495724.3496767

[96] Noah Simon, Jerome Friedman, Trevor Hastie, and Robert Tibshirani. A sparse-group lasso. Journal of Computational and Graphical Statistics, 22(2):231–245, 2013. doi:10.1080/10618600.2012.681250.
https://doi.org/10.1080/10618600.2012.681250

[97] Craig Saunders, Alexander Gammerman, and Volodya Vovk. Ridge regression learning algorithm in dual variables. In Proceedings of the Fifteenth International Conference on Machine Learning, ICML '98, page 515–521, San Francisco, CA, USA, 1998. Morgan Kaufmann Publishers Inc. URL: https://dl.acm.org/doi/10.5555/645527.657464.
https://dl.acm.org/doi/10.5555/645527.657464

[98] Changpeng Shao. Quantum speedup of leverage score sampling and its application. arXiv preprint arXiv:2301.06107, 2023. doi:10.48550/arXiv.2301.06107.
https://doi.org/10.48550/arXiv.2301.06107
arXiv:2301.06107

[99] P.W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134, 1994. doi:10.1109/SFCS.1994.365700.
https://doi.org/10.1109/SFCS.1994.365700

[100] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review, 41(2):303–332, 1999. doi:10.1137/S0036144598347011.
https://doi.org/10.1137/S0036144598347011

[101] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. Prediction by linear regression on a quantum computer. Phys. Rev. A, 94:022342, Aug 2016. doi:10.1103/PhysRevA.94.022342.
https://doi.org/10.1103/PhysRevA.94.022342

[102] Mihailo Stojnic. A framework to characterize performance of LASSO algorithms. arXiv preprint arXiv:1303.7291, 2013. doi:10.48550/arXiv.1303.7291.
https://doi.org/10.48550/arXiv.1303.7291
arXiv:1303.7291

[103] J. A. K. Suykens and J. Vandewalle. Least squares support vector machine classifiers. Neural Processing Letters, 9(3):293–300, Jun 1999. doi:10.1023/A:1018628609742.
https://doi.org/10.1023/A:1018628609742

[104] Changpeng Shao and Hua Xiang. Quantum regularized least squares solver with parameter estimate. Quantum Information Processing, 19(4):113, Feb 2020. doi:10.1007/s11128-020-2615-9.
https://doi.org/10.1007/s11128-020-2615-9

[105] Feng Tan, Xuezheng Fu, Yanqing Zhang, and Anu G. Bourgeois. A genetic algorithm-based method for feature subset selection. Soft Computing, 12(2):111–120, Jan 2008. doi:10.1007/s00500-007-0193-8.
https://doi.org/10.1007/s00500-007-0193-8

[106] Ryan J. Tibshirani. The lasso problem and uniqueness. Electronic Journal of Statistics, 7:1456 – 1490, 2013. doi:10.1214/13-EJS815.
https://doi.org/10.1214/13-EJS815

[107] Robert Tibshirani. Regression Shrinkage and Selection Via the Lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267–288, 12 2018. doi:10.1111/j.2517-6161.1996.tb02080.x.
https://doi.org/10.1111/j.2517-6161.1996.tb02080.x

[108] J.A. Tropp. Just relax: convex programming methods for identifying sparse signals in noise. IEEE Transactions on Information Theory, 52(3):1030–1051, 2006. doi:10.1109/TIT.2005.864420.
https://doi.org/10.1109/TIT.2005.864420

[109] Robert Tibshirani, Michael Saunders, Saharon Rosset, Ji Zhu, and Keith Knight. Sparsity and Smoothness Via the Fused Lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology, 67(1):91–108, 12 2004. doi:10.1111/j.1467-9868.2005.00490.x.
https://doi.org/10.1111/j.1467-9868.2005.00490.x

[110] Shaonan Tian, Yan Yu, and Hui Guo. Variable selection and corporate bankruptcy forecasts. Journal of Banking & Finance, 52:89–100, 2015. doi:10.1016/j.jbankfin.2014.12.003.
https://doi.org/10.1016/j.jbankfin.2014.12.003

[111] M. Graziano Usai, Mike E. Goddard, and Ben J. Hayes. LASSO with cross-validation for genomic selection. Genetics Research, 91(6):427–436, 2009. doi:10.1017/S0016672309990334.
https://doi.org/10.1017/S0016672309990334

[112] Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018. doi:10.1017/9781108231596.
https://doi.org/10.1017/9781108231596

[113] Hrishikesh D. Vinod. A survey of ridge regression and related techniques for improvements over ordinary least squares. The Review of Economics and Statistics, 60(1):121–131, 1978. URL: http://www.jstor.org/stable/1924340.
http://www.jstor.org/stable/1924340

[114] Dimitrios Ververidis and Constantine Kotropoulos. Sequential forward feature selection with low computational cost. In 2005 13th European Signal Processing Conference, pages 1–4, 2005. doi:10.5281/ZENODO.39057.
https://doi.org/10.5281/ZENODO.39057

[115] Martin J. Wainwright. Sharp thresholds for high-dimensional and noisy sparsity recovery using $\ell_{1}$-constrained quadratic programming (lasso). IEEE Transactions on Information Theory, 55(5):2183–2202, 2009. doi:10.1109/TIT.2009.2016018.
https://doi.org/10.1109/TIT.2009.2016018

[116] Martin J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi:10.1017/9781108627771.
https://doi.org/10.1017/9781108627771

[117] Guoming Wang. Quantum algorithm for linear regression. Phys. Rev. A, 96:012335, Jul 2017. doi:10.1103/PhysRevA.96.012335.
https://doi.org/10.1103/PhysRevA.96.012335

[118] Hua-liang Wei and Stephen A. Billings. Feature subset selection and ranking for data dimensionality reduction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(1):162–166, 2007. doi:10.1109/TPAMI.2007.250607.
https://doi.org/10.1109/TPAMI.2007.250607

[119] Nathan Wiebe, Daniel Braun, and Seth Lloyd. Quantum algorithm for data fitting. Phys. Rev. Lett., 109:050505, Aug 2012. doi:10.1103/PhysRevLett.109.050505.
https://doi.org/10.1103/PhysRevLett.109.050505

[120] Tong Tong Wu, Yi Fang Chen, Trevor Hastie, Eric Sobel, and Kenneth Lange. Genome-wide association analysis by lasso penalized logistic regression. Bioinformatics, 25(6):714–721, 01 2009. doi:10.1093/bioinformatics/btp041.
https://doi.org/10.1093/bioinformatics/btp041

[121] D. C. Whitley, M. G. Ford, and D. J. Livingstone. Unsupervised forward selection: a method for eliminating redundant variables. Journal of Chemical Information and Computer Sciences, 40(5):1160–1168, Sep 2000. doi:10.1021/ci000384c.
https://doi.org/10.1021/ci000384c

[122] Wessel N. van Wieringen. Lecture notes on ridge regression. arXiv preprint arXiv:1509.09169, 2015. doi:10.48550/arXiv.1509.09169.
https://doi.org/10.48550/arXiv.1509.09169
arXiv:1509.09169

[123] John Wright and Yi Ma. High-dimensional data analysis with low-dimensional models: Principles, computation, and applications. Cambridge University Press, 2022. doi:10.1017/9781108779302.
https://doi.org/10.1017/9781108779302

[124] Bo Xin, Yoshinobu Kawahara, Yizhou Wang, Lingjing Hu, and Wen Gao. Efficient generalized fused lasso and its applications. ACM Trans. Intell. Syst. Technol., 7(4), may 2016. doi:10.1145/2847421.
https://doi.org/10.1145/2847421

[125] Chao-Hua Yu, Fei Gao, and Qiao-Yan Wen. An improved quantum algorithm for ridge regression. IEEE Transactions on Knowledge and Data Engineering, 33(3):858–866, 2021. doi:10.1109/TKDE.2019.2937491.
https://doi.org/10.1109/TKDE.2019.2937491

[126] D. Zongker and A. Jain. Algorithms for feature selection: An evaluation. In Proceedings of 13th International Conference on Pattern Recognition, volume 2, pages 18–22 vol.2, 1996. doi:10.1109/ICPR.1996.546716.
https://doi.org/10.1109/ICPR.1996.546716

[127] Tuo Zhao, Han Liu, and Tong Zhang. Pathwise coordinate optimization for sparse learning: Algorithm and theory. The Annals of Statistics, 46(1):180 – 218, 2018. doi:10.1214/17-AOS1547.
https://doi.org/10.1214/17-AOS1547

[128] Peng Zhao and Bin Yu. On model selection consistency of lasso. Journal of Machine Learning Research, 7(90):2541–2563, 2006. URL: http://jmlr.org/papers/v7/zhao06a.html.
http://jmlr.org/papers/v7/zhao06a.html

Cited by

[1] Rochelle van Emmenis, Michael Dineen, Christina Fleming, Frank Buckley, and Maria Frizzarin, "Developing near-infrared spectroscopy models for predicting the nutritive value of perennial ryegrass and perennial ryegrass white clover swards: a multi-location validation approach", (2026).

[2] Mohammed Al-Haidary, Ahmed Bouridane, and Raouf Dridi, 2025 8th International Conference on Signal Processing and Information Security (ICSPIS) 1 (2025) ISBN:979-8-3315-8529-7.

[3] Bisma Majid, Shabir Ahmed Sofi, and Zamrooda Jabeen, "Quantum machine learning: a systematic categorization based on learning paradigms, NISQ suitability, and fault tolerance", Quantum Machine Intelligence 7 1, 39 (2025).

[4] Xiaojuan Zhu, Xianting Meng, Yufen Li, Chenhao Li, Xiujing Zhu, Zixin Yin, Tao Jiang, and Xin Su, "Revealing the Immunomodulatory Targets and Mechanisms of Sijing Pill for Postmenopausal Osteoporosis: A UHPLC-MS-Based Bioinformatics and Machine Learning Study", Journal of Pharmaceutical Innovation 21 3, 263 (2026).

[5] Debbie Lim, Joao F. Doriguello, and Patrick Rebentrost, "Hybrid Quantum-Classical Algorithm for Robust Optimization via Stochastic-Gradient Online Learning", Quantum Machine Intelligence 8 1, 28 (2026).

[6] Debbie Lim, Yixian Qiu, Patrick Rebentrost, and Qisheng Wang, "Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent", arXiv:2411.03925, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2026-07-16 23:58:58) and SAO/NASA ADS (last updated successfully 2026-07-16 23:58:59). 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.