Abstract
Recently, several quantum machine learning algorithms have been proposed that may offer quantum speed-ups over their classical counterparts. Most of these algorithms are either heuristic or assume that data can be accessed quantum-mechanically, making it unclear whether a quantum advantage can be proven without resorting to strong assumptions. Here we construct a classification problem with which we can rigorously show that heuristic quantum kernel methods can provide an end-to-end quantum speed-up with only classical access to data. To prove the quantum speed-up, we construct a family of datasets and show that no classical learner can classify the data inverse-polynomially better than random guessing, assuming the widely believed hardness of the discrete logarithm problem. Furthermore, we construct a family of parameterized unitary circuits, which can be efficiently implemented on a fault-tolerant quantum computer, and use them to map the data samples to a quantum feature space and estimate the kernel entries. The resulting quantum classifier achieves high accuracy and is robust against additive errors in the kernel entries that arise from finite sampling statistics.
This is a preview of subscription content, access via your institution
Access options
Access Nature and 54 other Nature Portfolio journals
Get Nature+, our best-value online-access subscription
$29.99 / 30 days
cancel any time
Subscribe to this journal
Receive 12 print issues and online access
$259.00 per year
only $21.58 per issue
Buy this article
- Purchase on SpringerLink
- Instant access to full article PDF
Prices may be subject to local taxes which are calculated during checkout
Similar content being viewed by others
Data availability
Data sharing is not applicable to this paper as no datasets were generated or analysed during the current study.
References
Biamonte, J. et al. Quantum machine learning. Nature 549, 195–202 (2017).
Arunachalam, S. & de Wolf, R. Guest column: a survey of quantum learning theory. SIGACT News 48, 41–67 (2017).
Dunjko, V. & Briegel, H. J. Machine learning & artificial intelligence in the quantum domain: a review of recent progress. Rep. Prog. Phys. 81, 074001 (2018).
Ciliberto, C. et al. Quantum machine learning: a classical perspective. Proc. R. Soc. A. 474, 20170551 (2018).
Carleo, G. et al. Machine learning and the physical sciences. Rev. Mod. Phys. 91, 045002 (2019).
Harrow, A. W., Hassidim, A. & Lloyd, S. Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103, 150502 (2009).
Wiebe, N., Braun, D. & Lloyd, S. Quantum algorithm for data fitting. Phys. Rev. Lett. 109, 050505 (2012).
Lloyd, S., Mohseni, M. & Rebentrost, P. Quantum algorithms for supervised and unsupervised machine learning. Preprint at https://arxiv.org/pdf/1307.0411.pdf (2013).
Lloyd, S., Mohseni, M. & Rebentrost, P. Quantum principal component analysis. Nat. Phys. 10, 631–633 (2014).
Rebentrost, P., Mohseni, M. & Lloyd, S. Quantum support vector machine for big data classification. Phys. Rev. Lett. 113, 130503 (2014).
Lloyd, S., Garnerone, S. & Zanardi, P. Quantum algorithms for topological and geometric analysis of data. Nat. Commun. 7, 10138 (2016).
Cong, I. & Duan, L. Quantum discriminant analysis for dimensionality reduction and classification. New J. Phys. 18, 073011 (2016).
Kerenidis, I. & Prakash, A. Quantum recommendation systems. In Proc. 8th Innovations in Theoretical Computer Science Conference, Leibniz International Proc. Informatics Vol. 67 (ed. Papadimitriou, C. H.) 49:1–49:21 (Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 2017).
Brandão, F. G. S. L. et al. Quantum SDP solvers: large speed-ups, optimality and applications to quantum learning. In Proc. 46th International Colloquium on Automata, Languages and Programming, Leibniz International Proc. Informatics Vol. 132 (eds Baier, C. et al.) 27:1–27:14 (Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 2019); http://drops.dagstuhl.de/opus/volltexte/2019/10603
Rebentrost, P., Steffens, A., Marvian, I. & Lloyd, S. Quantum singular-value decomposition of nonsparse low-rank matrices. Phys. Rev. A 97, 012327 (2018).
Zhao, Z., Fitzsimons, J. K. & Fitzsimons, J. F. Quantum-assisted Gaussian process regression. Phys. Rev. A 99, 052331 (2019).
Aaronson, S. Read the fine print. Nat. Phys. 11, 291–293 (2015).
Tang, E. A quantum-inspired classical algorithm for recommendation systems. In Proc. 51st Annual ACM SIGACT Symposium on Theory of Computing (eds Charikar, M. & Cohen, E.) 217–228 (ACM, 2019); https://doi.org/10.1145/3313276.3316310
Tang, E. Quantum-inspired classical algorithms for principal component analysis and supervised clustering. Preprint at https://arxiv.org/pdf/1811.00414.pdf (2018).
Chia, N.-H. et al. Quantum-inspired algorithms for solving low-rank linear equation systems with logarithmic dependence on the dimension. In 31st International Symposium on Algorithms and Computation, Leibniz International Proc. Informatics Vol. 181 (eds Cao, Y. et al) 47:1–47:17 (Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 2020); https://doi.org/10.4230/LIPIcs.ISAAC.2020.47
Ding, C., Bao, T.-Y. & Huang, H.-L. Quantum-inspired support vector machine. In IEEE Transactions on Neural Networks and Learning Systems 1–13 (IEEE, 2021); https://doi.org/10.1109/TNNLS.2021.3084467
Chia, N.-H. et al. Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning. In Proc. 52nd Annual ACM SIGACT Symposium on Theory of Computing (eds Makarychev, K. et al.) 387–400 (ACM, 2020); https://doi.org/10.1145/3357713.3384314
Mitarai, K., Negoro, M., Kitagawa, M. & Fujii, K. Quantum circuit learning. Phys. Rev. A 98, 032309 (2018).
Farhi, E. & Neven, H. Classification with quantum neural networks on near term processors. Preprint at https://arxiv.org/pdf/1802.06002.pdf (2018).
Schuld, M., Bocharov, A., Svore, K. M. & Wiebe, N. Circuit-centric quantum classifiers. Phys. Rev. A 101, 032308 (2020).
Liu, J.-G. & Wang, L. Differentiable learning of quantum circuit born machines. Phys. Rev. A 98, 062324 (2018).
Dallaire-Demers, P.-L. & Killoran, N. Quantum generative adversarial networks. Phys. Rev. A 98, 012324 (2018).
Lloyd, S. & Weedbrook, C. Quantum generative adversarial learning. Phys. Rev. Lett. 121, 040502 (2018).
Havlíček, V. et al. Supervised learning with quantum-enhanced feature spaces. Nature 567, 209–212 (2019).
Schuld, M. & Killoran, N. Quantum machine learning in feature Hilbert spaces. Phys. Rev. Lett. 122, 040504 (2019).
Vapnik, V. The Nature of Statistical Learning Theory (Springer Science & Business Media, 2013).
Shawe-Taylor, J. & Cristianini, N. On the generalization of soft margin algorithms. IEEE Trans. Inf. Theory 48, 2721–2735 (2002).
Kearns, M. J. The Computational Complexity of Machine Learning (MIT Press, 1990).
Servedio, R. A. & Gortler, S. J. Equivalences and separations between quantum and classical learnability. SIAM J. Comput. 33, 1067–1092 (2004).
Sweke, R., Seifert, J.-P., Hangleiter, D. & Eisert, J. On the quantum versus classical learnability of discrete distributions. Quantum 5, 417 (2021).
Harrow, A. W. Small quantum computers and large classical data sets. Preprint at https://arxiv.org/pdf/2004.00026.pdf (2020).
Gao, X., Zhang, Z.-Y. & Duan, L.-M. A quantum machine learning algorithm based on generative models. Sci. Adv. 4, eaat9004 (2018).
Shawe-Taylor, J. & Cristianini, N. Kernel Methods for Pattern Analysis (Cambridge Univ. Press, 2004).
Kearns, M. J. & Vazirani, U. V. An Introduction to Computational Learning Theory (MIT Press, 1994).
Shor, P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484–1509 (1997).
Blum, M. & Micali, S. How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput. 13, 850–864 (1984).
Aharonov, D. & Ta-Shma, A. Adiabatic quantum state generation. SIAM J. Comput. 37, 47–82 (2007).
Daniel, J. W. Stability of the solution of definite quadratic programs. Math. Program. 5, 41–53 (1973).
Temme, K., Bravyi, S. & Gambetta, J. M. Error mitigation for short-depth quantum circuits. Phys. Rev. Lett. 119, 180509 (2017).
Li, Y. & Benjamin, S. C. Efficient variational quantum simulator incorporating active error minimization. Phys. Rev. X 7, 021050 (2017).
Kandala, A. et al. Error mitigation extends the computational reach of a noisy quantum processor. Nature 567, 491–495 (2019).
Kusumoto, T., Mitarai, K., Fujii, K., Kitagawa, M. & Negoro, M. Experimental quantum kernel trick with nuclear spins in a solid. npj Quantum Inf. 7, 92 (2021).
Bartkiewicz, K. et al. Experimental kernel-based quantum machine learning in finite feature space. Sci. Rep. 10, 12356 (2020).
Peters, E. et al. Machine learning of high dimensional data on a noisy quantum processor. Preprint at https://arxiv.org/pdf/2101.09581.pdf (2021).
Acknowledgements
We thank S. Bravyi and R. Kothari for helpful comments and discussions. Y.L. was supported by DOE NQISRC QSA grant number FP00010905, Vannevar Bush faculty fellowship N00014-17-1-3025 and NSF award DMR-1747426. Part of this work was done when Y.L. was a research intern at IBM. S.A. and K.T. acknowledge support from the MIT-IBM Watson AI Lab under the project ‘Machine Learning in Hilbert Space’, the IBM Research Frontiers Institute and ARO grant W911NF-20-1-0014.
Author information
Authors and Affiliations
Contributions
All authors contributed important ideas during initial discussions and contributed equally to deriving the technical proofs and writing the manuscript.
Corresponding author
Ethics declarations
Competing interests
The authors declare no competing interests.
Additional information
Peer review information Nature Physics thanks Ewin Tang and Zhikuan Zhao for their contribution to the peer review of this work.
Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Supplementary information
Supplementary Information
Additional proof details and derivations.
Rights and permissions
About this article
Cite this article
Liu, Y., Arunachalam, S. & Temme, K. A rigorous and robust quantum speed-up in supervised machine learning. Nat. Phys. 17, 1013–1017 (2021). https://doi.org/10.1038/s41567-021-01287-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1038/s41567-021-01287-z