SCIENCE CHINA Physics, Mechanics & Astronomy, Volume 64 , Issue 2 : 220311(2021) https://doi.org/10.1007/s11433-020-1638-5

Quantum speedup in adaptive boosting of binary classification

More info
  • ReceivedJul 7, 2020
  • AcceptedNov 4, 2020
  • PublishedDec 30, 2020
PACS numbers



This work was supported by the Natural Science Foundation of Guangdong Province (Grant No. 2017B030308003), the Key RD Prog-ram of Guangdong Province (Grant No. 2018B030326001), the Science, Technology and Innovation Commission of Shenzhen Municipality (Grant Nos. JCYJ20170412152620376, JCYJ20170817105046702, and KYTDPT20181011104202253), the National Natural Science Foundation of China (Grant Nos. 11875160, and U1801661), the Economy, Trade and Information Commission of Shenzhen Municipality (Grant No. 201901161512), and Guangdong Provincial Key Laboratory (Grant No. 2019B121203002). We sincerely thank Dr. Srinivasan Arunachalam and Mr. Reevu Maity for their helpful discussions.


[1] Y. Freund, and S. Re Robert E, in International Conference on Machine Learning (Margan Kaufmann, San Francisco, 1996). Google Scholar

[2] M. Mohri, A. Rostamizadeh, and A. Talwalkar, Fundations of Machine Learning. (The MIT Press, Cambridge, 2012). Google Scholar

[3] Kong K. K., Hong K. S.. Pattern Recogn. Lett., 2015, 6863-69 CrossRef Google Scholar

[4] B. Markoski, Z. Ivanković L. Ratgeber, P. Pecev, and D. Glušac, Acta Polytechnica Hungarica (2015). Google Scholar

[5] Owusu E., Zhan Y., Mao Q. R.. Expert Syst. Appl., 2014, 413383-3390 CrossRef Google Scholar

[6] Y. L. Jiang, Y. F. Shen, Y. Liu, and W. C. Liu, Mathematical Problems in Engineering, 2015, 1--9 (2015). Google Scholar

[7] Li X., Wang L., Sung E.. Eng. Appl. Artif. Intell., 2008, 21785-795 CrossRef Google Scholar

[8] B. P. Roe, H. J. Yang, J. Zhu, Y. Liu, I. Stancu, and G. McGregor, Nuclear Instruments and Methods in Physics Research, Section A: Accelerators, Spectrometers, Detectors and Associated Equipment (Elsevier, Amsterdam, 2005). Google Scholar

[9] Zhang C. X., Zhang J. S.. Pattern Recogn. Lett., 2008, 291524-1536 CrossRef Google Scholar

[10] L. K. Grover, in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC '96, Association for Computing Machinery, (New York, 1996), pp. 212--219. Google Scholar

[11] A. Y. Kitaev,. arXiv Google Scholar

[12] Shor P. W.. SIAM J. Comput., 1997, 261484-1509 CrossRef Google Scholar

[13] Harrow A. W., Hassidim A., Lloyd S.. Phys. Rev. Lett., 2009, 103150502 CrossRef ADS arXiv Google Scholar

[14] Childs A. M., Kothari R., Somma R. D.. SIAM J. Comput., 2017, 461920-1950 CrossRef Google Scholar

[15] P. J. Coles, S. Eidenbenz, S. Pakin, A. Adedoyin, J. Ambrosiano, P. Anisimov, W. Casper, G. Chennupati, C. Coffrin, H. Djidjev, D. Gunter, S. Karra, N. Lemons, S. Z. Lin, A. Lokhov, A. Malyzhenkov, D. Mascarenas, S. Mniszewski, B. Nadiga, D. O'Malley, D. Oyen, L. Prasad, R. Roberts, P. Romero, N. Santhi, N. Sinitsyn, P. Swart, M. Vuffray, J. Wendelberger, B. Yoon, R. Zamora, and W. Zhu,. arXiv Google Scholar

[16] Buhrman H., de Wolf R.. Theor. Comput. Sci., 2002, 28821-43 CrossRef Google Scholar

[17] Biamonte J., Wittek P., Pancotti N., Rebentrost P., Wiebe N., Lloyd S.. Nature, 2017, 549195-202 CrossRef ADS arXiv Google Scholar

[18] C. Ciliberto, M. Herbster, A. D. Ialongo, M. Pontil, A. Rocchetto, S. Severini, and L. Wossnig, in Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science 474, 20170551 (2018). Google Scholar

[19] Cai X. D., Wu D., Su Z. E., Chen M. C., Wang X. L., Li L., Liu N. L., Lu C. Y., Pan J. W.. Phys. Rev. Lett., 2015, 114110504 CrossRef ADS arXiv Google Scholar

[20] Li Z., Liu X., Xu N., Du J.. Phys. Rev. Lett., 2015, 114140504 CrossRef ADS Google Scholar

[21] Dunjko V., Taylor J. M., Briegel H. J.. Phys. Rev. Lett., 2016, 117130501 CrossRef ADS arXiv Google Scholar

[22] Schuld M., Fingerhuth M., Petruccione F.. Europhy. Lett., 2017, 11960002 CrossRef ADS arXiv Google Scholar

[23] Rebentrost P., Mohseni M., Lloyd S.. Phys. Rev. Lett., 2014, 113130503 CrossRef ADS arXiv Google Scholar

[24] Cong I., Duan L.. New J. Phys., 2016, 18073011 CrossRef ADS arXiv Google Scholar

[25] Lloyd S., Mohseni M., Rebentrost P.. Nat. Phys., 2014, 10631-633 CrossRef ADS arXiv Google Scholar

[26] Sasaki M., Carlini A., Jozsa R.. Phys. Rev. A, 2001, 64022317 CrossRef ADS arXiv Google Scholar

[27] Bae J., Kwek L. C.. J. Phys. A-Math. Theor., 2015, 48083001 CrossRef ADS arXiv Google Scholar

[28] S. Arunachalam, and R. Maity. in Proceedings of the International Conference on Machine Learning, edited by H. Daume and A. Singh, (2020), pp. 9063--9073. Google Scholar

[29] A. Izdebski, and R. De Wolf,. arXiv Google Scholar

[30] M. Kearns, and L. Valiant, J. ACM, 41, 67--95 (1994). Google Scholar

[31] D. Dervovic, M. Herbster, P. Mountney, S. Severini, N. Usher, and L. Wossnig,. arXiv Google Scholar

[32] A. W. Harrow, and A. Y. Wei, Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (ACM Press, New York, 2020). pp. 193-212. Google Scholar

[33] H. J. Zhu, R. Kueng, M. Grassl, and D. Gross,. arXiv Google Scholar

[34] Y. X. Du, M.-H. Hsieh, T. L. Liu, and D. C. Tao,. arXiv Google Scholar

  • Figure 1

    (Color online) Visualized quantum AdaBoost algorithm.

  • Table 1  

    Table 1Query complexity of AdaBoost models

    Model Type of classifier $^{\rm~a)}$Query complexity
    Conventional D $\mathcal{O}(NT)$
    Probabilistic D/P $\mathcal{O}(NT)$
    Quantum D/P/Q $\mathcal{O}(\sqrt{N}T^2)$

    a) D for deterministic classifier, P for probabilistic classifier, and Q for quantum classifier.


    Algorithm 1 Adaboost

    Import $H_t$; The $T$ basis classifiers

    Input $S$; The sample of size $N$

    Initialize $W^x_0~\equiv~1$;

    for $t$ from $1$ to $T$

    for $x$ in $S$


    end for

    end for

    Iterate over all classifiers, only arithmetic partbelow.

    for $t$ from $1$ to $T$

    $\hat{R}_t\leftarrow \frac{1}{\abs{S}}\sum_{x\in~S}~r^x_t~W^x_{\pmb{s}_t}$ Take the average over $x$

    for $x$ in $S$

    if $r^x_t~=~0$ then

    $W^x_{\pmb{s}_t}~\leftarrow{W^x_{\pmb{s}_{t-1}}} /{2(1-\hat{R}_t)}$;


    $W^x_{\pmb{s}_t}~\leftarrow{W^x_{\pmb{s}_{t-1}}} /{2\hat{R}_t}$;

    end if

    end for

    $\alpha_t~\leftarrow~\frac{1}{2} \ln\left(\frac{1-\hat{R}_t}{\hat{R}_t}\right)$;

    end for

    Output $\qty{\alpha_1,\ldots,\alpha_{T}}$;


Contact and support