The idea of ensemble learning is to build a prediction model by combining the strengths of a collection of simpler base models. Although they are extensively used, ensemble methods have high requirements in terms of memory and computational time. In this work, we propose a quantum algorithm that allows reproducing ensemble classi cation using bagging strategy. The algorithm generates many sub-samples in superposition, in such a way that only a single execution of a quantum classi er is required. In particular, the entanglement between a quantum register and di erent training sub-samples in superposition 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 classi er impacts additively rather than multiplicatively, as it usually happens in ensemble framework. Furthermore, 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.
Thanks to the quantum mechanical principles of superposition and
entanglement, Quantum Computing (QC) can achieve vast amounts of parallelism [
The idea of a quantum ensemble based on Bayesian Model Averaging (BMA)
is investigated in [
In general, the idea of ensemble learning is to build a prediction model by
combining the strengths of a collection of simpler base models to reduce the
Expected Prediction Error [
X fb(x):
B
b=1
It turns out that Bagging produces a combined model that outperforms the
single model built from all training data, and is never substantially worse [
In this work, we provide a quantum algorithm to perform ensemble classi cation using bagging. The idea is to generate di erent sub-samples of the training set in superposition, each entangled with a quantum state of a control register. Thus, a quantum classi er C is applied to obtain a large number of classi cations in superposition. The proposed algorithm limits the number of state preparation routines and makes the evaluation of large ensemble feasible with small circuits. 3
The quantum algorithm for ensemble involves 5 quantum registers: j 0i =
j0i control
j0i training j0i temp j0i test
j0i target where the size of the control register determines the size of the ensemble (i.e. the number of base models), the size of training and test registers depend on the amount of data. The temp register determines the size of the sub-sample used as input in a single base model. Finally, the number of qubits in the target register depends on the nature of the target variable. Starting from these ve registers, the algorithm involves four steps: (Step 1) The state preparation consists in encoding the training and test set into their respective registers. Also, the control register is initialised into uniform superposition: j 1i = =
H d
S(x;y) 1 X2d jii p2d i=1 ! 1
S(x~)
1 j 0i = jx; yi j0i jx~i where S(x;y) and S(x~) are the unitaries that encode data in quantum states whose form depends on the encoding strategy chosen for data, and H d is the Walsh-Hadamard gate. (1) (2) (Step 2) The second step is sampling in superposition and consists in generating many altered transformation of the original training data, (x; y), in superposition. We consider a quantum oracle V which entangles several sub-sample of data with the control register: j 2i = V 1 1 j 1i =
1 X2d jii jx; yi jxi; yii p2d i=1 ! jx~i (3) where jxi; yii is a random sub-sample of jx; yi. After this step, the training register can be in any state, it will not be used further in the computation. (Step 3) The classi cation step consists in the interaction via interference between the temp and test registers, to store the estimates of the target variable:
C j 2i = p12d Xi2=d1 jii jx; yi jxi; yii jx~i jfi(x~)i ; (4) where fi(x~) is an estimate of the target variable for x~ and it depends on the i-th sub-sample and the test set x~. We refer to C as a quantum oracle that takes as input two sets of data encoded into two di erent registers, and provides an estimate of the target variable in an additional register. (Step 4) Finally, the expectation measurement on the target qubit provides a sum of expectation values that corresponds to the ensemble prediction: hM i = =
3j1 d 1 1 1 M 3 = 21d Xi2=d1 hfi(x~)jM jfi(x~)i = 21d Xi2=d0 hMii = B1 Xb=B1 fb = fbag x~j(x; y) (5) where M is a measurement operator (e.g. P auli gate).
As we can see from Equation 5, measuring the target qubit and leaving untouched the other quantum registers, we obtain the average of di erent classications based on di erent sub-samples. The separate computation of each base model is not required; indeed, it is only necessary to generate the quantum state expressed in Equation 3 and to execute the classi er C once. This implies, when considering the overall temporal cost of the algorithm, that the single classi er impacts additively rather than multiplicatively, as it usually happens in ensemble framework. In fact, in the classical ensemble, it is necessary to train the same algorithm under B di erent training conditions, and the overall temporal cost of the algorithm is, at least, the cost of the single classi er times B. In the case of quantum ensemble, the overall temporal cost of the algorithm depends on the generation of many sub-samples in superposition, plus one execution of the quantum classi er that, working via interference, allows propagating the use of the function f to all sub-samples. Furthermore, given a control register made up of d qubits, the ensemble size B is equal to 2d. This, in turn, implies that the ensemble size B scales exponentially with the number of qubits of the control register, opening up the possibility to achieve exponential speed-up with respect to the classical ensemble methods.
We provide small-scale experiments to show how quantum ensemble works. To the best of our knowledge, there is no quantum classi er which ful ls the requirements of Eq.(4); this problem will be investigated in future works. However, we show that given a unitary C that implements a generic function f , whose output is sensitive to the comparison between two inputs (train and test ), it is possible to leverage the quantum algorithm described in Section 3 to obtain the average of multiple outputs of f , by implementing C only once.
control j0i x1 j0i x2 j0i temp j0i
x~ j0i favg j0i
H S(x)
S(x~)
We consider two 2-dimensional training vectors encoded in the amplitudes of
two di erent qubits (training register) and a single qubit for each of the other
registers (control, temp, test, target ). As quantum gate C, we use the swap test [
The quantum algorithm for the ensemble of swap tests (Figure 1) entangles the two training vectors with the two quantum states of the control qubit. Then, the temp qubit is given as input to the swap test, together with the test qubit. This procedure allows to obtain the average distance between the test vector and the two training vectors through a single execution of the swap test. To show that the idea of ensemble works, we generated 20 random datasets, each made up of three vectors (x1, x2, xtest). We implemented the circuit in Figure 1 and then measured the target qubit. Results are reported in Figure 2. The plot on the left shows the experiments considering the quantum simulator that assumes a fault-tolerant quantum computer. The agreement between the quantum ensemble (orange line) and the classical ensemble (blue line) is almost perfect; this con rms the possibility to perform quantum ensemble with the advantages described in Section 3. The plot on the right shows the results using a real device (ibmq 16 melbourne). In this case, we can see a signi cant deterioration. This may be due to the depth of the implemented circuit, which seems to be prohibitive considering the actual quantum devices. 5
In this work, we proposed a quantum algorithm for ensemble classi cation that uses bagging strategy. Besides the theoretical algorithm, we provided small-scale experiments to show how the algorithm works. In particular, we showed that it is possible to produce a quantum ensemble by executing the classi cation routine only once. The algorithm provides advantages in terms of temporal computational complexity, although it is not complete in its technical formulation.
Future works will be dedicated to design a proper quantum classi er C, which
is able to provide di erent outputs based on di erent training sets. In fact, the
ensemble outperforms the single model only if the outputs of the base models
are accurate and diverse [
Although some challenges still remain, we believe that this work may be the rst step to show that QML can overcome the limitations of classical ML in the context of ensemble classi cation.