Quantum AdaBoost with Supervised Learning Guarantee

Thank you very much for your insightful comments. We have thoroughly revised the manuscript to make our contributions clearer.

We utilize multi-qubit quantum gates for the following reasons. 1) Parametric quantum circuits constructed by using only single quantum parametric gates are classical in essence and cannot provide sufficient expressibility for variational quantum algorithms to ensure a good approximation to the solution. 2) We agree with you that multi-qubit quantum gates may suffer from more noise and lead to Barren Plateau issues. There have been many schemes to mitigate the training issues. 3) In our experiments, we only employ 2-qubit quantum gates. 4) 2-qubit quantum gates can be realized in a native way to minimize the hardware noise. 5) 2-qubit quantum gates are necessary components in most of the existing parametric quantum circuits.

Thank you for pointing out the reference. We have read it in detail. First of all, Eq. (5) in our paper is a widely-adopted figure of merit to depict the generalization error, see e.g.,

1. Matthias C. Caro, et.al., Generalization in quantum machine learning from few training data, Nature Communications, 13:4919, 2022.
2. Matthias C. Caro, et.al., Out-of-distribution generalization for learning quantum dynamics, Nature Communications, 14:3751, 2023.
3. Hsin-Yuan Huang, et.al., Power of data in quantum machine learning, Nature Communications, 12:2631, 2021.

In quantum machine learning, the prediction accuracy is what we really concern, but it cannot be directly accessed as both the label of unseen data and the distribution is unknown. Nevertheless, we do have access to the empirical or training error. The difference between the prediction error and the training error is referred to as the generalization error. It is unknown but we can bound it as we have done in our work.

In your mentioned reference, they provided another way for error decomposition, but the so-called training error (whose meaning is different from ours) that results from the optimization bias of gradient-based algorithms is hard to bound. In fact, they did not give such a bound. In addition, to obtain their main results, they assumed a crucial PL condition which assumes that the norm of the cost function gradient is bounded below by the cost function multiplied by a parameter $\mu$, namely, $\frac{1}{2}\\|\nabla\mathcal{L}_S(\boldsymbol{\theta})\\|^2_2\geq\mu\mathcal{L}_S(\boldsymbol{\theta})$. This is a very strong assumption, as it is well-known that training quantum parameterized circuits often suffers from the Barren Plateau issue, where the cost gradient vanishes exponentially fast as the scale of the problem increases. Thus, the strong PL constraint may limit the applicability of their main result. Our work provides the first theoretical proof that for binary classification the prediction error of variational quantum AdaBoost can converge to 0 as the increase of the number of boosting rounds and sample size.

• Why more rounds T can be beneficial to the proposed Adaboost method?

The fact that more rounds are beneficial to the performance of quantum AdaBoost is owing to the characteristic of AdaBoost. Take Algorithm 2 for an illustration. When $t=1$, it starts from a selected base classifier whose error is less than 1/2. Then at each round ($t\in[T]$), a new base classifier, whose error is less than 1/2, is selected and the distribution is updated to have the effect of focusing more on the points incorrectly classified at the next round. After $T$ rounds, the classifier returned by AdaBoost is a non-negative linear combination of the base classifiers selected at each round. In Figure 4 and Figure 5, when $T=1$, namely, at the beginning stage of AdaBoost, the classifier is only a base classifier, which is weak. Thus, its performance is relatively bad. We have made this clearer in the current manuscript.

• Why not provide the classical neural networks to compare the Adaboost performance?
• If using the same Adaboost algorithm, what are the quantum advantages of using quantum neural networks?

According to your suggestion, we have performed new experiments to compare our quantum AdaBoost with its classical counterpart. For classical AdaBoost, weak classifiers can be boosted to obtain a strong classifier which has a high level of training accuracy. However, it is generally hard to theoretically guarantee that the generalization error of the strong classifier is small. In contrast, for quantum machine learning, the generalization of quantum classifiers can be guaranteed, while the training is often difficult. In our paper we combine the advantages of quantum machine learning in generalization and classical ensemble methods in training to obtain our main result, namely, variational quantum AdaBoost with supervised learning guarantee for binary classification. In the revised manuscript, as demonstrated in Table 1, we numerically validate that while the training accuracy of quantum AdaBoost is lower than that of classical AdaBoost, the prediction accuracy on new data of quantum AdaBoost is better as compared with classical AdaBoost.

Thank you very much for your insightful comments. We have thoroughly revised the manuscript to make our contributions clearer.

Finding various practical tasks that can demonstrate quantum superiority remains an open question. Here, we combine the advantages of quantum machine learning in generalization and classical AdaBoost in training to provide the first theoretical proof that for binary classification the prediction error of variational quantum AdaBoost can converge to 0 as the increase of the number of boosting rounds and sample size. In the revised manuscript, we also numerically validate that while the training accuracy of quantum AdaBoost is lower than that of classical AdaBoost, the prediction accuracy on new data of quantum AdaBoost is better as compared with classical AdaBoost. We have demonstrated the new numerical results in Table 1 in the revised manuscript. And we have performed more runs of experiments and all the results support our conclusion.

• The algorithm 2 points out the error of the base classifier should be small. However, under the limitation of circuit depth, how to guarantee the classifier $h_t$ has a small test error meanwhile with shallow circuit depth.

Algorithm 2 only requires that quantum weak classifiers are slightly better than random guess, which is easy to be satisfied. We have made this clearer in the revised version.

• In theorem 3.1, it points out that the generalization error is bounded by the number of training samples $n$ and independent trainable gates $K$. Since we can increase the number of $K$ to improve the model and decrease the error, however, why do we increase $K$, the bound is getting worse, which is not reasonable.

When increasing $K$, the bound is getting worse. This is owing to the Occam’s Razor principle: Plurality should not be posited without necessity. Specifically, there is a trade-off between reducing the training error versus controlling the size of the hypothesis set: a larger hypothesis set ($K$ is larger) could help reduce the training error, but is penalized by the second and third terms in Eq. (9). For a similar training error, it suggests using a smaller hypothesis set.

• The quantum advantages are not quite clear, is there any evidence that the proposed method gives quantum advantages?

Finding various practical tasks that can demonstrate quantum superiority remains an open question. Here, we utilize the advantage of quantum machine learning in generalization to provide the first theoretical proof that for binary classification the prediction error of variational quantum AdaBoost can converge to 0 as the increase of the number of boosting rounds and sample size.

Thank you very much for your insightful comments. We have thoroughly revised the manuscript to present our contributions and the differences from existing works more clearly.

• Theoretical novelty

To the best of our knowledge, our work provides the first theoretical proof that for binary classification the prediction error of variational quantum AdaBoost can converge to 0 as the increase of the number of boosting rounds and sample size. To be specific, for classical AdaBoost, weak classifiers can be boosted to obtain a strong classifier which has a high level of training accuracy. However, it is generally hard to theoretically guarantee that the generalization error of the strong classifier is small. In contrast, for variational quantum machine learning, the generalization of quantum classifiers can be guaranteed, while the training is often difficult. In this paper we combine the advantages of quantum machine learning in generalization and classical ensemble methods in training, and utilize their analytical tools to obtain our main result, namely, variational quantum AdaBoost with supervised learning guarantee for binary classification.

• Difference with related work

We have revised Sec. 1.2 Related Work to make it clearer. For your convenience, we list the differences between our work and existing works in the following.

1. As compared with classical AdaBoost, the training accuracy of quantum AdaBoost is lower, since it is often harder to train a quantum classifier than to train a classical classifier. However, as the generalization is easy to be guaranteed for quantum classifiers, the prediction accuracy on new data of quantum AdaBoost is better as compared with classical AdaBoost. We have performed new experiments to demonstrate this in Table 1 in the revised manuscript.
2. Various quantum versions of AdaBoost have been proposed, such as Arunachalam & Maity, 2020; Wang et al., 2021b; Ohno, 2022. In their works, they employed quantum subroutines, e.g., mean estimation and amplitude amplification, to update quantum weak classifiers and estimate the weighted errors. Therefore, the realizations of these quantum versions of AdaBoost are beyond the scope of current noisy intermediate-scale quantum (NISQ) devices. In contrast, in our work we utilize variational quantum classifiers realized on the current NISQ circuits, which are obtained through a quantum-classical hybrid way.
3. Although the variational quantum AdaBoost has been investigated, e.g., in Li et al., 2023, its performance is validated only through numerical simulations. In our work, we theoretically guarantee the performance of quantum AdaBoost.
4. In the current NISQ era, quantum machine leaning is generally weak owing to limited scale of quantum circuits and inevitable influences of noise. Thus it is better to utilize the ensemble methods, e.g., AdaBoost, to combine weak learners to obtain a strong leaner.

• New findings

The training accuracy of quantum weak learners is lower than that of classical ones, as it is often harder to train quantum learners than to train classical learners. In our new experiments (illustrated in Table 1), under the same number of optimization iterations, the average training accuracy of quantum AdaBoost (having 120 parameters) is 0.975 with standard deviation 0.002, while the classical AdaBoost (having 787 parameters) has a higher level of average training accuracy which is 0.980 with standard deviation 0.004. In contrast, as the generalization is easy to be guaranteed for quantum classifiers, the average prediction accuracy on new data of quantum AdaBoost is 0.973 with standard deviation 0.001, which is better than that of the classical AdaBoost being 0.967 with standard deviation 0.003. We have demonstrated these results in Table 1 in the revised manuscript.

• As there is no code for this work, it is unclear whether the empirical results are reproductible.

We will release the codes when preparing the camera-ready version. If you are interested in reproducing our results, we are also ready to share these codes with you.

Thank you very much for your insightful comments.

• What are the differences between your quantum AdaBoost and other previously proposed quantum AdaBoost algorithms?

We have thoroughly revised the manuscript to more clearly present our contributions and the differences from other previously proposed algorithms. For example, we have changed the title to “Variational Quantum AdaBoost with Supervised Learning Guarantee” and rewritten Sec. 1.2 Related Work and Sec. 1.3 Our Contributions to make them clearer.

To the best of our knowledge, our work provides the first theoretical proof that for binary classification the prediction error of variational quantum AdaBoost can converge to 0 as the increase of the number of boosting rounds and sample size. To be specific, for classical AdaBoost, weak classifiers can be boosted to obtain a strong classifier which has a high level of training accuracy. However, it is generally hard to theoretically guarantee that the generalization error of the strong classifier is small. In contrast, for variational quantum machine learning, the generalization of quantum classifiers can be guaranteed, while the training is often difficult. In this paper we combine the advantages of quantum machine learning in generalization and classical ensemble methods in training to obtain our main result, namely, variational quantum AdaBoost with supervised learning guarantee for binary classification.

Various quantum versions of AdaBoost have been proposed, such as Arunachalam & Maity, 2020; Wang et al., 2021b; Ohno, 2022. In their works, they employed quantum subroutines, e.g., mean estimation and amplitude amplification, to update quantum weak classifiers and estimate the weighted errors. Therefore, the realizations of these quantum versions of AdaBoost are beyond the scope of current noisy intermediate-scale quantum (NISQ) devices. In contrast, in our work we utilize variational quantum classifiers realized on the current NISQ circuits, which are obtained through a quantum-classical hybrid way.

• How does your framework compare to other ensemble methods for quantum classifiers?

Following your suggestion, we have performed new experiments comparing our quantum AdaBoost with Quantum Bagging, classical neural networks+AdaBoost, and classical neural networks+Bagging. We find that our quantum AdaBoost has the best prediction accuracy on new data among all these results. The results are demonstrated in Table 1 in the revised manuscript.

• Why does your framework mitigate the effects of noises in PQCs?

In addition to the depolarizing noise, we also perform new experiments under the amplitude damping noise and phase damping noise. All experimental results demonstrate that quantum AdaBoost can help mitigate the influence of these noises. The reasons are twofold. First, in our variational quantum AdaBoost, weak learners can be boosted to obtain a strong learner as long as the weak learners are slightly better than random guess. Noise may degrade the weak leaners, however, as long as they are still better than random guess, they can be boosted to obtain a strong learner. Second, as the quantum parameterized circuit is shallow, quantum learners are weak, but also, the classifiers are less affected by noise due to shallow circuits.