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

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2019.

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

- [Representation of binary classification trees with binary features by quantum circuits](https://mlsanity.com/paper/2108.13207/) (2021)
- [The Quantum Version of Prediction for Binary Classification Problem by Ensemble Methods](https://mlsanity.com/paper/2112.13346/) (2021)
- [Des-q: a quantum algorithm to provably speedup retraining of decision trees](https://mlsanity.com/paper/2309.09976/) (2023)
- [The Improvement of Decision Tree Construction Algorithm Based On Quantum Heuristic Algorithms](https://mlsanity.com/paper/2212.14725/) (2022)
- [QC-Forest: a Classical-Quantum Algorithm to Provably Speedup Retraining of Random Forest](https://mlsanity.com/paper/2406.12008/) (2024)
- [Quantum Random Forest for the Regression Problem](https://mlsanity.com/paper/2603.22790/) (2026)

## Abstract (arXiv)

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· d· Nlog N). Secondly, we suggest a quantum version of this algorithm, which uses quantum subroutines like the amplitude amplification and the D"urr-Hoyer minimum search algorithms that are based on Grover's algorithm. The running time of the quantum algorithm is Obig(h· √dlog d · N log Nbig) that is better than complexity of the classical algorithm.