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

arXiv: https://arxiv.org/abs/2309.09976 · HTML: https://mlsanity.com/paper/2309.09976/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 78 references that are in the map.
- First posted on arXiv 18 Sep 2023.

## Builds on (most cited first, 15 of 15)

- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [q-means: A quantum algorithm for unsupervised machine learning](https://mlsanity.com/paper/1812.03584/) (2018)
- [Extremely Fast Decision Tree](https://mlsanity.com/paper/1802.08780/) (2018)
- [Robust Decision Trees Against Adversarial Examples](https://mlsanity.com/paper/1902.10660/) (2019)
- [The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation](https://mlsanity.com/paper/1804.01973/) (2018)
- [A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees](https://mlsanity.com/paper/2011.03375/) (2020)
- [Representation of binary classification trees with binary features by quantum circuits](https://mlsanity.com/paper/2108.13207/) (2021)
- [Margin Optimal Classification Trees](https://mlsanity.com/paper/2210.10567/) (2022)
- [The Quantum Version Of Classification Decision Tree Constructing Algorithm C5.0](https://mlsanity.com/paper/1907.06840/) (2019)
- [Quantum Approximate Counting, Simplified](https://mlsanity.com/paper/1908.10846/) (2019)
- [Do you know what q-means?](https://mlsanity.com/paper/2308.09701/) (2023)
- [Low depth algorithms for quantum amplitude estimation](https://mlsanity.com/paper/2012.03348/) (2020)
- [Quantum Speedup Based on Classical Decision Trees](https://mlsanity.com/paper/1905.13095/) (2019)
- [A Quantum Approximation Scheme for k-Means](https://mlsanity.com/paper/2308.08167/) (2023)

## Built on by (most cited first, 4 of 4)

- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [Expressive variational quantum circuits provide inherent privacy in federated learning](https://mlsanity.com/paper/2309.13002/) (2023)
- [Quantum Random Forest for the Regression Problem](https://mlsanity.com/paper/2603.22790/) (2026)
- [Quantum Annealing Enhanced Reinforcement Learning for Accurate Remaining Useful Lifetime Prediction](https://mlsanity.com/paper/2606.18503/) (2026)

## Abstract (arXiv)

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.