An efficient quantum algorithm for ensemble classification using bagging

Ensemble methods aggregate predictions from multiple models, typically demonstrating improved accuracy and reduced variance compared to individual classifiers. However, they often come with significant memory usage and computational time requirements. A novel quantum algorithm that leverages quantum superposition, entanglement, and interference to construct an ensemble of classification models using bagging as an aggregation strategy is introduced. Through the generation of numerous quantum trajectories in superposition, the authors achieve B transformations of the training set with only logB $\mathit{log}\left(B\right)$ operations, allowing an exponential enlargement of the ensemble size while linearly increasing the depth of the corresponding circuit. Moreover, when assessing the algorithm's overall cost, the authors demonstrate that the training of a single weak classifier contributes additively to the overall time complexity, as opposed to the multiplicative impact commonly observed in classical ensemble methods. To illustrate the efficacy of the authors' approach, experiments on reduced real-world datasets utilising the IBM qiskit environment to demonstrate the functionality and performance of the proposed algorithm are introduced.A new quantum algorithm that exploits quantum superposition, entanglement, and interference to build an ensemble of classification models is introduced. Thanks to the generation of several quantum trajectories in superposition, the authors obtain an exponentially large number of base models increasing only linearly the depth of the correspondent quantum circuit. The authors also present small-scale experiments, defining a quantum version of the cosine classifier and using the IBM qiskit environment to show how the algorithm works. image