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

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 53 references that are in the map.
- First posted on arXiv 17 Jun 2024.

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

- [Barren plateaus in quantum neural network training landscapes](https://mlsanity.com/paper/1803.11173/) (2018)
- [Learning under Concept Drift: A Review](https://mlsanity.com/paper/2004.05785/) (2020)
- [Challenges and Opportunities in Quantum Machine Learning](https://mlsanity.com/paper/2303.09491/) (2023)
- [Noise-Induced Barren Plateaus in Variational Quantum Algorithms](https://mlsanity.com/paper/2007.14384/) (2020)
- [Barren Plateaus in Variational Quantum Computing](https://mlsanity.com/paper/2405.00781/) (2024)
- [Does provable absence of barren plateaus imply classical simulability?](https://mlsanity.com/paper/2312.09121/) (2023)
- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [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)
- [DDG-DA: Data Distribution Generation for Predictable Concept Drift Adaptation](https://mlsanity.com/paper/2201.04038/) (2022)
- [Learngene: From Open-World to Your Learning Task](https://mlsanity.com/paper/2106.06788/) (2021)
- [Representation of binary classification trees with binary features by quantum circuits](https://mlsanity.com/paper/2108.13207/) (2021)
- [The Quantum Version Of Classification Decision Tree Constructing Algorithm C5.0](https://mlsanity.com/paper/1907.06840/) (2019)
- [Universal Quantum Speedup for Branch-and-Bound, Branch-and-Cut, and Tree-Search Algorithms](https://mlsanity.com/paper/2210.03210/) (2022)

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

- [A Quantum Bagging Algorithm with Unsupervised Base Learners for Label Corrupted Datasets](https://mlsanity.com/paper/2509.07040/) (2025)

## Abstract (arXiv)

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.