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.
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 |
Archive Staff Only
 |
View Item |
