UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Statistical limits of supervised quantum learning

Ciliberto, C; Rocchetto, A; Rudi, A; Wossnig, L; (2020) Statistical limits of supervised quantum learning. Physical Review A , 102 (4) , Article 042414. 10.1103/PhysRevA.102.042414. Green open access

[img]
Preview
Text
PhysRevA.102.042414.pdf - Published version

Download (189kB) | Preview

Abstract

Within the framework of statistical learning theory it is possible to bound the minimum number of samples required by a learner to reach a target accuracy. We show that if the bound on the accuracy is taken into account, quantum machine learning algorithms for supervised learning—for which statistical guarantees are available—cannot achieve polylogarithmic runtimes in the input dimension. We conclude that, when no further assumptions on the problem are made, quantum machine learning algorithms for supervised learning can have at most polynomial speedups over efficient classical algorithms, even in cases where quantum access to the data is naturally available.

Type: Article
Title: Statistical limits of supervised quantum learning
Open access status: An open access version is available from UCL Discovery
DOI: 10.1103/PhysRevA.102.042414
Publisher version: https://doi.org/10.1103/PhysRevA.102.042414
Language: English
Additional information: This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10118628
Downloads since deposit
31Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item