Des-q: a quantum algorithm to provably speedup retraining of decision trees
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 algorith...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2025-01-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2025-01-13-1588/pdf/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841543116766576640 |
|---|---|
| author | Niraj Kumar Romina Yalovetzky Changhao Li Pierre Minssen Marco Pistoia |
| author_facet | Niraj Kumar Romina Yalovetzky Changhao Li Pierre Minssen Marco Pistoia |
| author_sort | Niraj Kumar |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-aa47063ca241461e8b2fa77950fe9669 |
| institution | Kabale University |
| issn | 2521-327X |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | Article |
| series | Quantum |
| spelling | doaj-art-aa47063ca241461e8b2fa77950fe96692025-01-13T15:48:45ZengVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenQuantum2521-327X2025-01-019158810.22331/q-2025-01-13-158810.22331/q-2025-01-13-1588Des-q: a quantum algorithm to provably speedup retraining of decision treesNiraj KumarRomina YalovetzkyChanghao LiPierre MinssenMarco PistoiaDecision 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.https://quantum-journal.org/papers/q-2025-01-13-1588/pdf/ |
| spellingShingle | Niraj Kumar Romina Yalovetzky Changhao Li Pierre Minssen Marco Pistoia Des-q: a quantum algorithm to provably speedup retraining of decision trees Quantum |
| title | Des-q: a quantum algorithm to provably speedup retraining of decision trees |
| title_full | Des-q: a quantum algorithm to provably speedup retraining of decision trees |
| title_fullStr | Des-q: a quantum algorithm to provably speedup retraining of decision trees |
| title_full_unstemmed | Des-q: a quantum algorithm to provably speedup retraining of decision trees |
| title_short | Des-q: a quantum algorithm to provably speedup retraining of decision trees |
| title_sort | des q a quantum algorithm to provably speedup retraining of decision trees |
| url | https://quantum-journal.org/papers/q-2025-01-13-1588/pdf/ |
| work_keys_str_mv | AT nirajkumar desqaquantumalgorithmtoprovablyspeedupretrainingofdecisiontrees AT rominayalovetzky desqaquantumalgorithmtoprovablyspeedupretrainingofdecisiontrees AT changhaoli desqaquantumalgorithmtoprovablyspeedupretrainingofdecisiontrees AT pierreminssen desqaquantumalgorithmtoprovablyspeedupretrainingofdecisiontrees AT marcopistoia desqaquantumalgorithmtoprovablyspeedupretrainingofdecisiontrees |