Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Des-q: a Quantum Algorithm to Construct and Efficiently Retrain Decision Trees for Regression and Binary Classification

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

Published Oct 16, 2023• 0 citations
Publisher

Abstract

Abstract Decision trees are widely used in machine learning for their simplicity in construction and interpretability. However, as data sizes grow, traditional methods for constructing and retraining decision trees become increasingly slow, scaling polynomially with the number of training examples. We introduce a novel quantum algorithm, Des-q, for constructing and retraining decision trees in regression and binary classification. Assuming the data stream produces small increments of new training examples, Des-q significantly reduces the tree retraining time, achieving poly-logarithmic time complexity in the number of examples, even accounting for the time needed to load the new examples into quantum-accessible memory. Our approach involves building a decision tree algorithm to perform k-piecewise linear tree splits at each internal node. These splits simultaneously generate multiple hyperplanes, dividing the feature space into k distinct regions. To determine the k suitable anchor points for these splits, we develop an efficient quantum-supervised clustering method, building upon the q-means algorithm by Kerenidis et al. Des-q first efficiently estimates each feature weight using a novel quantum technique to estimate the Pearson correlation. Subsequently, we employ weighted distance estimation to cluster the training examples in k disjoint regions based on nearest-neighbor matching and then proceed to expand the tree using the same procedure. We benchmark the performance of the simulated version of our algorithm against the state-of-the-art classical decision tree on multiple data sets with numerical features. Further, we showcase that the proposed algorithm exhibits similar performance to the state-of-the-art decision tree while significantly speeding up the periodic tree retraining.

DOI
10.21203/rs.3.rs-3434278/v1

Related papers

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

Niraj Kumar, Romina Yalovetzky, Changhao Li +2 more

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.

arXiv:2309.09976•Quantum•Jan 13, 2025•3 citations

QC-Forest: a Classical-Quantum Algorithm to Provably Speedup Retraining of Random Forest

Romina Yalovetzky, Kumar, Niraj, Changhao Li +1 more

Random Forest (RF) is a popular tree-ensemble method for supervised learning, prized for its ease of use and flexibility. Online RF models require to account for new training data to maintain model accuracy. This is particularly important in applications where data is periodically and sequentially generated over time in data streams, such as auto-driving systems, and credit card payments. In this setting, performing periodic model retraining with the old and new data accumulated is beneficial as it fully captures possible drifts in the data distribution over time. However, this is unpractical with state-of-the-art classical algorithms for RF as they scale linearly with the accumulated number of samples. We propose QC-Forest, a classical-quantum algorithm designed to time-efficiently retrain RF models in the streaming setting for multi-class classification and regression, achieving a runtime poly-logarithmic in the total number of accumulated samples. QC-Forest leverages Des-q, a quantum algorithm for single tree construction and retraining proposed by Kumar et al. by expanding to multi-class classification, as the original proposal was limited to binary classes, and introducing an exact classical method to replace an underlying quantum subroutine incurring a finite error, while maintaining the same poly-logarithmic dependence. Finally, we showcase that QC-Forest achieves competitive accuracy in comparison to state-of-the-art RF methods on widely used benchmark datasets with up to 80,000 samples, while significantly speeding up the model retrain.

arXiv:2406.12008•Jun 17, 2024•0 citations

The Quantum Version Of Classification Decision Tree Constructing Algorithm C5.0

Kamil Ravilevich Khadiev, Ilnaz Mannapov, Liliya Safina

In the paper, we focus on complexity of C5.0 algorithm for constructing decision tree classifier that is the models for the classification problem from machine learning. In classical case the decision tree is constructed in $O(hd(NM+N \log N))$ running time, where $M$ is a number of classes, $N$ is the size of a training data set, $d$ is a number of attributes of each element, $h$ is a tree height. Firstly, we improved the classical version, the running time of the new version is $O(h\cdot d\cdot N\log N)$. Secondly, we suggest a quantum version of this algorithm, which uses quantum subroutines like the amplitude amplification and the D{ü}rr-Høyer minimum search algorithms that are based on Grover's algorithm. The running time of the quantum algorithm is $O\big(h\cdot \sqrt{d}\log d \cdot N \log N\big)$ that is better than complexity of the classical algorithm.

arXiv:1907.06840•Jul 16, 2019•18 citations

Kvantti puudiagrammit

Oskari Luukkonen

Quantum computers and machine learning are on the forefront of research in both science and engineering. Quantum computers offer significant computational speed-ups in certain tasks. Machine learning on the other hand requires a lot of computational power and is heavily used by both governments and businesses. Thus it is no wonder that the possibility of leveraging the computational efficiency of quantum computers for machine learning tasks is attractive. This thesis focuses on decision trees models, due to their interpretability and wide use cases. This thesis tries to answer the question, how can quantum technology be leveraged to improve the performance and construction of decision trees. The thesis will explore the full implementation of decision trees in quantum circuits as quantum decision trees and their viability in modern hardware and its future relevance. Quantum algorithms for construction and retraining of classical decision trees will also be explored and compared to classical methods. The work found that quantum decision trees show comparable performance to classical decision trees when applied to simple data sets. However, due to hardware limitations quantum decision trees suffer when applied to more complex data sets. Quantum algorithms for tree construction show significant theoretical speed-ups at larger models when compared to classical methods of tree construction.

•May 11, 2026•0 citations

Variational Decision Trees with Structured Ansatzes

Alessandro Poggiali, Giacomo Antonioli, Alessandro Berti +2 more

Decision trees are among the most interpretable models in machine learning, widely valued for their transparency, simplicity, and alignment with human reasoning. However, traditional decision tree algorithms rely on greedy heuristics, splitting nodes one at a time based on local criteria, which often leads to suboptimal trees and limits their effectiveness in complex scenarios. In this work, we propose a quantum-enhanced approach for learning decision trees, with the aim of identifying a optimal tree according to a specified global criterion. This approach employs a Variational Quantum Algorithm (VQA) to encode and optimize the decision tree represented as matrix, leveraging tailored ansatzes that constrain the search to a specific subspace of the Hilbert space.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

Quantum Ensemble for Classification

Antonio Macaluso, L. Clissa, Stefano Lodi +1 more

A powerful way to improve performance in machine learning is to construct an ensemble that combines the predictions of multiple models. Ensemble methods are often much more accurate and lower variance than the individual classifiers that make them up but have high requirements in terms of memory and computational time. In fact, a large number of alternative algorithms is usually adopted, each requiring to query all available data. We propose a new quantum algorithm that exploits quantum superposition, entanglement and interference to build an ensemble of classification models. Thanks to the generation of the several quantum trajectories in superposition, we obtain $B$ transformations of the quantum state which encodes the training set in only $log\left(B\right)$ operations. This implies exponential growth of the ensemble size while increasing linearly the depth of the correspondent circuit. Furthermore, when considering the overall cost of the algorithm, we show that the training of a single weak classifier impacts additively the overall time complexity rather than multiplicatively, as it usually happens in classical ensemble methods. We also present small-scale experiments on real-world datasets, defining a quantum version of the cosine classifier and using the IBM qiskit environment to show how the algorithms work.

arXiv:2007.01028•Jul 2, 2020•9 citations
Abstract Decision trees are widely used in machine learning for their simplicity in construction and interpretability. However, as data sizes grow, traditional methods for constructing and retraining decision trees become increasingly slow, scaling polynomially with the number of training examples. We introduce a novel quantum algorithm, Des-q, for constructing and retraining decision trees in regression and binary classification. Assuming the data stream produces small increments of new training examples, Des-q significantly reduces the tree retraining time, achieving poly-logarithmic time complexity in the number of examples, even accounting for the time needed to load the new examples into quantum-accessible memory. Our approach involves building a decision tree algorithm to perform k-piecewise linear tree splits at each internal node. These splits simultaneously generate multiple hyperplanes, dividing the feature space into k distinct regions. To determine the k suitable anchor points for these splits, we develop an efficient quantum-supervised clustering method, building upon the q-means algorithm by Kerenidis et al. Des-q first efficiently estimates each feature weight using a novel quantum technique to estimate the Pearson correlation. Subsequently, we employ weighted distance estimation to cluster the training examples in k disjoint regions based on nearest-neighbor matching and then proceed to expand the tree using the same procedure. We benchmark the performance of the simulated version of our algorithm against the state-of-the-art classical decision tree on multiple data sets with numerical features. Further, we showcase that the proposed algorithm exhibits similar performance to the state-of-the-art decision tree while significantly speeding up the periodic tree retraining.
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.
Random Forest (RF) is a popular tree-ensemble method for supervised learning, prized for its ease of use and flexibility. Online RF models require to account for new training data to maintain model accuracy. This is particularly important in applications where data is periodically and sequentially generated over time in data streams, such as auto-driving systems, and credit card payments. In this setting, performing periodic model retraining with the old and new data accumulated is beneficial as it fully captures possible drifts in the data distribution over time. However, this is unpractical with state-of-the-art classical algorithms for RF as they scale linearly with the accumulated number of samples. We propose QC-Forest, a classical-quantum algorithm designed to time-efficiently retrain RF models in the streaming setting for multi-class classification and regression, achieving a runtime poly-logarithmic in the total number of accumulated samples. QC-Forest leverages Des-q, a quantum algorithm for single tree construction and retraining proposed by Kumar et al. by expanding to multi-class classification, as the original proposal was limited to binary classes, and introducing an exact classical method to replace an underlying quantum subroutine incurring a finite error, while maintaining the same poly-logarithmic dependence. Finally, we showcase that QC-Forest achieves competitive accuracy in comparison to state-of-the-art RF methods on widely used benchmark datasets with up to 80,000 samples, while significantly speeding up the model retrain.
In the paper, we focus on complexity of C5.0 algorithm for constructing decision tree classifier that is the models for the classification problem from machine learning. In classical case the decision tree is constructed in O(hd(NM+Nlog⁡N))O(hd(NM+N \log N))O(hd(NM+NlogN)) running time, where MMM is a number of classes, NNN is the size of a training data set, ddd is a number of attributes of each element, hhh is a tree height. Firstly, we improved the classical version, the running time of the new version is O(h⋅d⋅Nlog⁡N)O(h\cdot d\cdot N\log N)O(h⋅d⋅NlogN). Secondly, we suggest a quantum version of this algorithm, which uses quantum subroutines like the amplitude amplification and the D{ü}rr-Høyer minimum search algorithms that are based on Grover's algorithm. The running time of the quantum algorithm is O(h⋅dlog⁡d⋅Nlog⁡N)O\big(h\cdot \sqrt{d}\log d \cdot N \log N\big)O(h⋅d​logd⋅NlogN) that is better than complexity of the classical algorithm.
Quantum computers and machine learning are on the forefront of research in both science and engineering. Quantum computers offer significant computational speed-ups in certain tasks. Machine learning on the other hand requires a lot of computational power and is heavily used by both governments and businesses. Thus it is no wonder that the possibility of leveraging the computational efficiency of quantum computers for machine learning tasks is attractive. This thesis focuses on decision trees models, due to their interpretability and wide use cases. This thesis tries to answer the question, how can quantum technology be leveraged to improve the performance and construction of decision trees. The thesis will explore the full implementation of decision trees in quantum circuits as quantum decision trees and their viability in modern hardware and its future relevance. Quantum algorithms for construction and retraining of classical decision trees will also be explored and compared to classical methods. The work found that quantum decision trees show comparable performance to classical decision trees when applied to simple data sets. However, due to hardware limitations quantum decision trees suffer when applied to more complex data sets. Quantum algorithms for tree construction show significant theoretical speed-ups at larger models when compared to classical methods of tree construction.
Decision trees are among the most interpretable models in machine learning, widely valued for their transparency, simplicity, and alignment with human reasoning. However, traditional decision tree algorithms rely on greedy heuristics, splitting nodes one at a time based on local criteria, which often leads to suboptimal trees and limits their effectiveness in complex scenarios. In this work, we propose a quantum-enhanced approach for learning decision trees, with the aim of identifying a optimal tree according to a specified global criterion. This approach employs a Variational Quantum Algorithm (VQA) to encode and optimize the decision tree represented as matrix, leveraging tailored ansatzes that constrain the search to a specific subspace of the Hilbert space.
A powerful way to improve performance in machine learning is to construct an ensemble that combines the predictions of multiple models. Ensemble methods are often much more accurate and lower variance than the individual classifiers that make them up but have high requirements in terms of memory and computational time. In fact, a large number of alternative algorithms is usually adopted, each requiring to query all available data. We propose a new quantum algorithm that exploits quantum superposition, entanglement and interference to build an ensemble of classification models. Thanks to the generation of the several quantum trajectories in superposition, we obtain BBB transformations of the quantum state which encodes the training set in only log(B)log\left(B\right)log(B) operations. This implies exponential growth of the ensemble size while increasing linearly the depth of the correspondent circuit. Furthermore, when considering the overall cost of the algorithm, we show that the training of a single weak classifier impacts additively the overall time complexity rather than multiplicatively, as it usually happens in classical ensemble methods. We also present small-scale experiments on real-world datasets, defining a quantum version of the cosine classifier and using the IBM qiskit environment to show how the algorithms work.