The Quantum Version Of Classification Decision Tree Constructing Algorithm C5.0
This work addresses computational efficiency for machine learning practitioners by providing incremental improvements and a quantum adaptation to a specific algorithm.
The paper tackles the complexity of the C5.0 decision tree algorithm for classification, improving the classical version to O(h·d·N log N) and proposing a quantum version with a running time of O(h·√d log d·N log N), which is better than the classical complexity.
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.