Des-q: a quantum algorithm to provably speedup retraining of decision trees

Niraj Kumar; Romina Yalovetzky; Changhao Li; Pierre Minssen; Marco Pistoia

doi:10.22331/q-2025-01-13-1588

Des-q: a quantum algorithm to provably speedup retraining of decision trees

Niraj Kumar, Romina Yalovetzky, Changhao Li, Pierre Minssen, and Marco Pistoia

Global Technology Applied Research, JPMorgan Chase, New York, NY 10017 USA

Published:	2025-01-13, volume 9, page 1588
Editor:	Vedran Dunjko
Eprint:	arXiv:2309.09976v5
Doi:	https://doi.org/10.22331/q-2025-01-13-1588
Citation:	Quantum 9, 1588 (2025).

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

Updated version: The authors have uploaded version v6 of this work to the arXiv which may contain updates or corrections not contained in the published version v5. The authors left the following comment on the arXiv:

44 pager, 5 figures, 4 tables

Abstract

Decision trees are widely adopted machine learning models due to their simplicity and explainability. However, as training data size grows, standard methods become increasingly slow, scaling polynomially with the number of training examples. In this work, we introduce Des-q, a novel quantum algorithm to construct and retrain decision trees for regression and binary classification tasks. Assuming the data stream produces small, periodic increments of new training examples, Des-q significantly reduces the tree retraining time. Des-q achieves a logarithmic complexity in the combined total number of old and new examples, even accounting for the time needed to load the new samples into quantum-accessible memory. Our approach to grow the tree from any given node involves performing piecewise linear splits to generate multiple hyperplanes, thus partitioning the input feature space into distinct regions. To determine the suitable anchor points for these splits, we develop an efficient quantum-supervised clustering method, building upon the q-means algorithm introduced by Kerenidis et al. We benchmark the simulated version of Des-q against the state-of-the-art classical methods on multiple data sets and observe that our algorithm exhibits similar performance to the state-of-the-art decision trees while significantly speeding up the periodic tree retraining.

Popular summary

Decision trees are a popular choice in machine learning due to their straightforward nature and ease of interpretation. However, as the amount of data grows, traditional methods for training these models can become slow and inefficient. To tackle this, we introduce Des-q, an innovative quantum algorithm that enhances the efficiency of constructing and updating decision trees for regression and binary classification.
Des-q excels in scenarios where new data is added periodically. It dramatically cuts down the time needed to retrain decision trees, achieving a speed that scales logarithmically with the total amount of data—both old and new. This is a significant improvement over classical methods, which typically slow down as data size increases.
The key advantage of Des-q lies in its novel approach to growing decision trees. It uses piecewise linear splits to create multiple hyperplanes, effectively dividing the data into distinct regions. To find the best points for these splits, Des-q employs a cutting-edge quantum-supervised clustering technique, building on the q-means algorithm introduced by Kerenidis et al.
When tested against the best classical methods on various datasets, Des-q not only matched their performance but also offered a much faster way to update decision trees. This advancement paves the way for more efficient data processing in the age of big data.

► BibTeX data

@article{Kumar2025desqquantum,
  doi = {10.22331/q-2025-01-13-1588},
  url = {https://doi.org/10.22331/q-2025-01-13-1588},
  title = {Des-q: a quantum algorithm to provably speedup retraining of decision trees},
  author = {Kumar, Niraj and Yalovetzky, Romina and Li, Changhao and Minssen, Pierre and Pistoia, Marco},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1588},
  month = jan,
  year = {2025}
}

► References

[1] Scott Aaronson and Patrick Rall. Quantum approximate counting, simplified. In Symposium on simplicity in algorithms, pages 24–32. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611976014.5.
https://doi.org/10.1137/1.9781611976014.5

[2] Haldun Akoglu. User's guide to correlation coefficients. Turkish journal of emergency medicine, 18(3):91–93, 2018. URL: https://doi.org/10.1016/j.tjem.2018.08.001.
https://doi.org/10.1016/j.tjem.2018.08.001

[3] Jonathan Allcock, Jinge Bao, João F Doriguello, Alessandro Luongo, and Miklos Santha. Constant-depth circuits for uniformly controlled gates and boolean functions with application to quantum memory circuits. arXiv preprint arXiv:2308.08539, 2023. URL: https://doi.org/10.22331/q-2024-11-20-1530.
https://doi.org/10.22331/q-2024-11-20-1530
arXiv:2308.08539

[4] David Arthur and Sergei Vassilvitskii. K-means++ the advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1027–1035, 2007. URL: https://dl.acm.org/doi/10.5555/1283383.1283494.
https://dl.acm.org/doi/10.5555/1283383.1283494

[5] Salman Beigi and Leila Taghavi. Quantum speedup based on classical decision trees. Quantum, 4:241, March 2020. URL: https://doi.org/10.22331/q-2020-03-02-241.
https://doi.org/10.22331/q-2020-03-02-241

[6] Fernando Berzal, Juan-Carlos Cubero, Nicolás Marín, and Daniel Sánchez. Building multi-way decision trees with numerical attributes. Information Sciences, 165(1-2):73–90, 2004. URL: https://doi.org/10.1016/j.ins.2003.09.018.
https://doi.org/10.1016/j.ins.2003.09.018

[7] Arnon Boneh and Micha Hofri. The coupon-collector problem revisited — a survey of engineering problems and computational methods. Stochastic Models, 13(1):39–66, 1997. URL: https://doi.org/10.1080/15326349708807412.
https://doi.org/10.1080/15326349708807412

[8] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53–74, 2002. URL: https://doi.org/10.48550/arXiv.quant-ph/0005055.
https://doi.org/10.48550/arXiv.quant-ph/0005055
arXiv:quant-ph/0005055

[9] Gilles Brassard, Peter HØyer, and Alain Tapp. Quantum counting. In Automata, Languages and Programming, pages 820–831. Springer Berlin Heidelberg, 1998. URL: https://doi.org/10.1007/bfb0055105.
https://doi.org/10.1007/bfb0055105

[10] Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone. Classification And Regression Trees. Routledge, October 2017. URL: https://doi.org/10.1201/9781315139470.
https://doi.org/10.1201/9781315139470

[11] RS Bucy and RS Diesposti. Decision tree design by simulated annealing. ESAIM: Mathematical Modelling and Numerical Analysis, 27(5):515–534, 1993. URL: https://doi.org/10.1051/m2an/1993270505151.
https://doi.org/10.1051/m2an/1993270505151

[12] Harry Buhrman, Richard Cleve, John Watrous, and Ronald De Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902, 2001. URL: https://doi.org/10.1103/PhysRevLett.87.167902.
https://doi.org/10.1103/PhysRevLett.87.167902

[13] Wray Buntine. Learning classification trees. Statistics and computing, 2:63–73, 1992. URL: https://doi.org/10.1007/BF01889584.
https://doi.org/10.1007/BF01889584

[14] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power of block-encoded matrix powers: improved regression techniques via faster hamiltonian simulation. arXiv preprint arXiv:1804.01973, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.33.
https://doi.org/10.4230/LIPIcs.ICALP.2019.33
arXiv:1804.01973

[15] Hongge Chen, Huan Zhang, Duane Boning, and Cho-Jui Hsieh. Robust decision trees against adversarial examples. In International Conference on Machine Learning, pages 1122–1131. PMLR, 2019. URL: https://doi.org/10.48550/arXiv.1902.10660.
https://doi.org/10.48550/arXiv.1902.10660

[16] Pedro Domingos and Geoff Hulten. Mining high-speed data streams. In Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 71–80, 2000. URL: https://doi.org/10.1145/347090.347107.
https://doi.org/10.1145/347090.347107

[17] João F Doriguello, Alessandro Luongo, and Ewin Tang. Do you know what q-means? arXiv preprint arXiv:2308.09701, 2023. URL: https://doi.org/10.48550/arXiv.2308.09701.
https://doi.org/10.48550/arXiv.2308.09701
arXiv:2308.09701

[18] Federico D’Onofrio, Giorgio Grani, Marta Monaci, and Laura Palagi. Margin optimal classification trees. Computers & Operations Research, 161:106441, 2024. URL: https://doi.org/10.48550/arXiv.2210.10567.
https://doi.org/10.48550/arXiv.2210.10567

[19] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Physical review letters, 100(16):160501, 2008. URL: https://doi.org/10.1103/PhysRevLett.100.160501.
https://doi.org/10.1103/PhysRevLett.100.160501

[20] Tudor Giurgica-Tiron, Iordanis Kerenidis, Farrokh Labib, Anupam Prakash, and William Zeng. Low depth algorithms for quantum amplitude estimation. Quantum, 6:745, 2022. URL: https://doi.org/10.22331/q-2022-06-27-745.
https://doi.org/10.22331/q-2022-06-27-745

[21] Gene V Glass and Julian C Stanley. Statistical methods in education and psychology. Prentice-Hall, 1970.

[22] Dmitry Grinko, Julien Gacon, Christa Zoufal, and Stefan Woerner. Iterative quantum amplitude estimation. npj Quantum Information, 7(1):52, 2021. URL: https://doi.org/10.1038/s41534-021-00379-1.
https://doi.org/10.1038/s41534-021-00379-1

[23] Thomas Hancock, Tao Jiang, Ming Li, and John Tromp. Lower bounds on learning decision lists and trees. Information and Computation, 126(2):114–122, 1996. URL: https://doi.org/10.1006/inco.1996.0040.
https://doi.org/10.1006/inco.1996.0040

[24] David Harrison Jr and Daniel L Rubinfeld. Hedonic housing prices and the demand for clean air. Journal of environmental economics and management, 5(1):81–102, 1978. URL: https://doi.org/10.1016/0095-0696(78)90006-2.
https://doi.org/10.1016/0095-0696(78)90006-2

[25] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103(15):150502, 2009. URL: https://doi.org/10.1103/PhysRevLett.103.150502.
https://doi.org/10.1103/PhysRevLett.103.150502

[26] Raoul Heese, Patricia Bickert, and Astrid Elisa Niederle. Representation of binary classification trees with binary features by quantum circuits. Quantum, 6:676, March 2022. URL: https://doi.org/10.22331/q-2022-03-30-676.
https://doi.org/10.22331/q-2022-03-30-676

[27] Tin Kam Ho. The random subspace method for constructing decision forests. IEEE transactions on pattern analysis and machine intelligence, 20(8):832–844, 1998. URL: https://doi.org/10.1109/34.709601.
https://doi.org/10.1109/34.709601

[28] Mark Hopkins, Erik Reeber, George Forman, and Jaap Suermondt. Spambase. UCI Machine Learning Repository, 1999. URL: https://doi.org/10.24432/C53G6X.
https://doi.org/10.24432/C53G6X

[29] Ragesh Jaiswal. A quantum approximation scheme for k-means. arXiv preprint arXiv:2308.08167, 2023. URL: https://doi.org/10.48550/arXiv.2308.08167.
https://doi.org/10.48550/arXiv.2308.08167
arXiv:2308.08167

[30] Samuel Jaques and Arthur G Rattew. Qram: A survey and critique. arXiv preprint arXiv:2305.10310, 2023.
arXiv:2305.10310

[31] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash. q-means: A quantum algorithm for unsupervised machine learning. Advances in neural information processing systems, 32, 2019. URL: https://doi.org/10.48550/arXiv.1812.03584.
https://doi.org/10.48550/arXiv.1812.03584

[32] Iordanis Kerenidis and Alessandro Luongo. Classification of the mnist data set with quantum slow feature analysis. Physical Review A, 101(6):062327, 2020. URL: https://doi.org/10.1103/PhysRevA.101.062327.
https://doi.org/10.1103/PhysRevA.101.062327

[33] Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. arXiv preprint arXiv:1603.08675, 2016. URL: https://doi.org/10.1103/PhysRevLett.100.160501.
https://doi.org/10.1103/PhysRevLett.100.160501
arXiv:1603.08675

[34] Kamil Khadiev, Ilnaz Mannapov, and Liliya Safina. The quantum version of classification decision tree constructing algorithm c5.0, 2019. URL: https://arxiv.org/abs/1907.06840.
arXiv:1907.06840

[35] Igor Kononenko. Estimating attributes: Analysis and extensions of relief. In European conference on machine learning, pages 171–182. Springer, 1994.

[36] Roger J. Lewis. An introduction to classification and regression tree (cart) analysis. 2000. URL: https://api.semanticscholar.org/CorpusID:14981989.
https://api.semanticscholar.org/CorpusID:14981989

[37] JM Linacre and G Rasch. The expected value of a point-biserial (or similar) correlation. Rasch Measurement Transactions, 22(1):1154, 2008.

[38] Zhenyu Liu, Tao Wen, Wei Sun, and Qilong Zhang. A novel multiway splits decision tree for multiple types of data. Mathematical Problems in Engineering, 2020:1–12, 2020. URL: https://doi.org/10.1155/2020/7870534.
https://doi.org/10.1155/2020/7870534

[39] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum algorithms for supervised and unsupervised machine learning. arXiv preprint arXiv:1307.0411, 2013. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.49.
https://doi.org/10.4230/LIPIcs.ITCS.2017.49
arXiv:1307.0411

[40] Stuart Lloyd. Least squares quantization in pcm. IEEE Transactions on Information Theory, 28(2):129–137, 1982. doi:10.1109/TIT.1982.1056489.
https://doi.org/10.1109/TIT.1982.1056489

[41] Songfeng Lu and Samuel L. Braunstein. Quantum decision tree classifier. Quantum Information Processing, 13(3):757–770, November 2013. URL: https://doi.org/10.1007/s11128-013-0687-5.
https://doi.org/10.1007/s11128-013-0687-5

[42] Songfeng Lu and Samuel L Braunstein. Quantum decision tree classifier. Quantum information processing, 13(3):757–770, 2014. URL: https://doi.org/10.1007/s11128-013-0687-5.
https://doi.org/10.1007/s11128-013-0687-5

[43] Chaitanya Manapragada, Geoffrey I Webb, and Mahsa Salehi. Extremely fast decision tree. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1953–1962, 2018. URL: https://doi.org/10.1145/3219819.3220005.
https://doi.org/10.1145/3219819.3220005

[44] Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017. URL: https://doi.org/10.1007/s11128-013-0687-5.
https://doi.org/10.1007/s11128-013-0687-5

[45] Ashley Montanaro. Quantum algorithms: an overview. npj Quantum Information, 2(1):1–8, 2016. URL: https://doi.org/10.1038/npjqi.2016.23.
https://doi.org/10.1038/npjqi.2016.23

[46] Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge university press, 2010. URL: https://doi.org/10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667

[47] Andrei Novikov. Pyclustering: Data mining library. Journal of Open Source Software, 4(36):1230, apr 2019. doi:10.21105/joss.01230.
https://doi.org/10.21105/joss.01230

[48] Karl Pearson. Vii. note on regression and inheritance in the case of two parents. proceedings of the royal society of London, 58(347-352):240–242, 1895. URL: http://www.jstor.org/stable/115794.
http://www.jstor.org/stable/115794

[49] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825–2830, 2011. URL: https://doi.org/10.48550/arXiv.1201.0490.
https://doi.org/10.48550/arXiv.1201.0490

[50] J. Ross Quinlan. Induction of decision trees. Machine learning, 1:81–106, 1986. URL: https://doi.org/10.1007/BF00116251.
https://doi.org/10.1007/BF00116251

[51] J Ross Quinlan. C4. 5: programs for machine learning. Elsevier, 2014. URL: https://doi.org/10.1007/BF00993309.
https://doi.org/10.1007/BF00993309

[52] Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. URL: https://doi.org/10.1609/aaai.v29i1.9277.
https://doi.org/10.1609/aaai.v29i1.9277

[53] Lidia Ruiz-Perez and Juan Carlos Garcia-Escartin. Quantum arithmetic with the quantum fourier transform. Quantum Information Processing, 16:1–14, 2017. URL: https://doi.org/10.1007/s11128-017-1603-1.
https://doi.org/10.1007/s11128-017-1603-1

[54] Seref Sagiroglu and Duygu Sinanc. Big data: A review. In 2013 international conference on collaboration technologies and systems (CTS), pages 42–47. IEEE, 2013. URL: https://doi.org/10.1109/CTS.2013.6567202.
https://doi.org/10.1109/CTS.2013.6567202

[55] Wojciech Samek, Grégoire Montavon, Sebastian Lapuschkin, Christopher J Anders, and Klaus-Robert Müller. Explaining deep neural networks and beyond: A review of methods and applications. Proceedings of the IEEE, 109(3):247–278, 2021. URL: https://doi.org/10.1109/CTS.2013.6567202.
https://doi.org/10.1109/CTS.2013.6567202

[56] Himani Sharma, Sunil Kumar, et al. A survey on decision tree algorithms of classification in data mining. International Journal of Science and Research (IJSR), 5(4):2094–2097, 2016.

[57] Matthew Smith, Christian Szongott, Benjamin Henne, and Gabriele Von Voigt. Big data privacy issues in public social media. In 2012 6th IEEE international conference on digital ecosystems and technologies (DEST), pages 1–6. IEEE, 2012. URL: https://doi.org/10.1109/DEST.2012.6227909.
https://doi.org/10.1109/DEST.2012.6227909

[58] Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, pages 217–228, 2019. URL: https://doi.org/10.1145/3313276.3316310.
https://doi.org/10.1145/3313276.3316310

[59] Hao Tang, Boning Li, Guoqing Wang, Haowei Xu, Changhao Li, Ariel Barr, Paola Cappellaro, and Ju Li. Communication-efficient quantum algorithm for distributed machine learning. Phys. Rev. Lett., 130:150602, Apr 2023. URL: https://doi.org/10.1103/PhysRevLett.130.150602.
https://doi.org/10.1103/PhysRevLett.130.150602

[60] Alexey Tsymbal. The problem of concept drift: definitions and related work. Computer Science Department, Trinity College Dublin, 106(2):58, 2004.

[61] Paul E Utgoff. Incremental induction of decision trees. Machine learning, 4:161–186, 1989. URL: https://doi.org/10.1023/A:1022699900025.
https://doi.org/10.1023/A:1022699900025

[62] Nathan Wiebe, Ashish Kapoor, and Krysta Svore. Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning. arXiv preprint arXiv:1401.2142, 2014. URL: https://dl.acm.org/doi/abs/10.5555/2871393.2871400.
arXiv:1401.2142
https://dl.acm.org/doi/abs/10.5555/2871393.2871400

[63] Min Xu, Pakorn Watanachaturaporn, Pramod K Varshney, and Manoj K Arora. Decision tree regression for soft classification of remote sensing data. Remote Sensing of Environment, 97(3):322–336, 2005. URL: https://doi.org/10.1016/j.rse.2005.05.008.
https://doi.org/10.1016/j.rse.2005.05.008

[64] I-Cheng Yeh. Blood Transfusion Service Center. UCI Machine Learning Repository, 2008. DOI: https://doi.org/10.24432/C5GS39.
https://doi.org/10.24432/C5GS39

[65] Zhi-Hua Zhou and Ji Feng. Deep forest: Towards an alternative to deep neural networks. In IJCAI, pages 3553–3559, 2017. URL: https://doi.org/10.24963/ijcai.2017/497.
https://doi.org/10.24963/ijcai.2017/497

[66] Haoran Zhu, Pavankumar Murali, Dzung Phan, Lam Nguyen, and Jayant Kalagnanam. A scalable mip-based method for learning optimal multivariate decision trees. Advances in neural information processing systems, 33:1771–1781, 2020. URL: https://doi.org/10.48550/arXiv.2011.03375.
https://doi.org/10.48550/arXiv.2011.03375

[67] Paul Zikopoulos and Chris Eaton. Understanding big data: Analytics for enterprise class hadoop and streaming data. McGraw-Hill Osborne Media, 2011.

Cited by

[1] Sven Groppe, Valter Uotila, and Jinghua Groppe, Proceedings of the 3rd workshop on Quantum Computing and Quantum-Inspired Technology for Data-Intensive Systems and Applications 25 (2026) ISBN:9798400727030.

[2] Manqoba Q. Hlatshwayo, Manav Babel, Dalila Islas-Sanchez, and Konstantinos Georgopoulos, "A Technical Review of Quantum Computing Use Cases for Finance and Economics", Quantum Reports 8 1, 26 (2026).

[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] Kamil Khadiev and Liliya Safina, 2026 International Conference on Quantum Communications, Networking, and Computing (QCNC) 1 (2026) ISBN:979-8-3315-6110-9.

[5] Niraj Kumar, Jamie Heredge, Changhao Li, Shaltiel Eloul, Shree Hari Sureshbabu, and Marco Pistoia, "Expressive variational quantum circuits provide inherent privacy in federated learning", arXiv:2309.13002, (2023).

[6] Poojan Shah and Ragesh Jaiswal, "Quantum (Inspired) $D^2$-sampling with Applications", arXiv:2405.13351, (2024).

[7] Diksha Sharma, Parvinder Singh, and Atul Kumar, "Quantum-inspired attribute selection algorithms", Quantum Science and Technology 10 1, 015036 (2025).

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