Quantum algorithm for ensemble learning

The idea of ensemble learning is to build a prediction model by combining the strengths of a collection of simpler base models. Al- though they are extensively used, ensemble methods have high require- ments in terms of memory and computational time. In this work, we propose a quantum algorithm that allows reproducing ensemble classification using bagging strategy. The algorithm generates many sub-samples in superposition, in such a way that only a single exe- cution of a quantum classifier is required. In particular, the entanglement between a quantum register and different training sub-samples in super- position allows obtaining a sum of individual results which gives rise to the ensemble prediction. When considering the overall temporal cost of the algorithm, the single base classifier impacts additively rather than multiplicatively, as it usually happens in ensemble framework. Further- more, given that the number of base models scales exponentially with the number of qubits of the control register, our algorithm opens up the possibility of exponential speed-up for quantum ensemble.