CoChat
Sign Up
Cited by 518Quantum Computing Algorithms and ArchitectureQuantum many-body systemsQuantum Information and Cryptography

Quantum machine learning: a classical perspective

Open access
Ciliberto, Carlo, Herbster, Mark, Ialongo, Alessandro Davide, Pontil, Massimiliano, Rocchetto, Andrea, Severini, Simone, Wossnig, Leonard·2018·Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
DOI 10.1098/rspa.2017.0551PMC PMC5806018
Open this paper in CoChat — free accountOpen PDF

Abstract

Recently, increased computational power and data availability, as well as algorithmic advances, have led machine learning (ML) techniques to impressive results in regression, classification, data generation and reinforcement learning tasks. Despite these successes, the proximity to the physical limits of chip fabrication alongside the increasing size of datasets is motivating a growing number of researchers to explore the possibility of harnessing the power of quantum computation to speed up classical ML algorithms. Here we review the literature in quantum ML and discuss perspectives for a mixed readership of classical ML and quantum computation experts. Particular emphasis will be placed on clarifying the limitations of quantum algorithms, how they compare with their best classical counterparts and why quantum resources are expected to provide advantages for learning problems. Learning in the presence of noise and certain computationally hard problems in ML are identified as promising directions for the field. Practical questions, such as how to upload classical data into quantum form, will also be addressed.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1098/rspa.2017.0551

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Using quantum machine learning, educational institutions can analyze vast amounts of data to identify students at risk of dropping out or struggling academically.

    “Thus, using QML, educational institutions can analyze a vast amount of data (Ciliberto et al., 2018). This data could include student performance, attendance records, and demographic information, to identify students at risk of dropping out or struggling academically.”

    From Quantum technology for development framework as a tool for science diplomacy (2023) · cites this paper as Ciliberto et al., 2018

    The ‘Setting the problem’ section says quantum computation could help learning methods scale to larger datasets, but cautions that current QML methods may be limited in real settings. The paper does not establish that educational institutions can use QML to analyze their data. The citation is attached to that claim, not to the following sentence about identifying students at risk. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

  • QC provides many other benefits for ML, such as fast linear algebra, quantum sampling, quantum optimization, and quantum artificial neural networks.

    “Moreover, QC provides many other benefits for ML, such as fast linear algebra, quantum sampling, quantum optimization, and quantum artificial neural networks [54].”

    From On Circuit-Based Hybrid Quantum Neural Networks for Remote Sensing Imagery Classification (2022) · cites this paper as [54]

  • Many machine learning techniques have corresponding equivalents in the quantum domain.

    “many machine learning techniques (see, e.g., Refs.[105-109]) have corresponding equivalents in the quantum domain.”

    From Neutral atom quantum computing hardware: performance and end-user perspective (2023) · cites this paper as [105]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

The citation lists haven’t been fetched yet

References 209 · Cited by 518

Research works printed but not linked: 147

  1. [1]Krizhevsky A, Sutskever I, Hinton GE 2012 Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems (eds F Pereira, CJC Burges, L Bottou, KQ Weinberger), pp. 1097–1105. Red Hook, NY: Curran Associates, Inc.
  2. [2]Silver D et al. 2016 Mastering the game of Go with deep neural networks and tree search. Nature 529, 484– 489. (doi:10.1038/nature16961) 26819042 · DOI · Paper page
  3. [3]Markov IL 2014 Limits on fundamental limits to computation. Nature 512, 147– 154. (doi:10.1038/nature13570) 25119233 · DOI · Paper page
  4. [5]Van Dam W, Hallgren S, Ip L 2006 Quantum algorithms for some hidden shift problems. SIAM J. Comput. 36, 763– 778. (doi:10.1137/S009753970343141X) · DOI
  5. [6]Hallgren S 2007 Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem. J. ACM 54, 4 (doi:10.1145/1206035.1206039) · DOI
  6. [7]Adcock J et al. 2015 Advances in quantum machine learning. (http://arxiv.org/abs/1512.02900). · arXiv
  7. [8]Biamonte J, Wittek P, Pancotti N, Rebentrost P, Wiebe N, Lloyd S 2017 Quantum machine learning. Nature 549, 195– 202. (doi:10.1038/nature23474) 28905917 · DOI · Paper page
  8. [10]Bacon D, Van Dam W 2010 Recent progress in quantum algorithms. Commun. ACM. 53, 84– 93. (doi:10.1145/1646353.1646375) · DOI
  9. [11]Bishop CM et al. 2006 Pattern recognition and machine learning, vol. 1 New York, NY: Springer.
  10. [12]Murphy KP 2012 Machine learning: a probabilistic perspective. Cambridge, MA: The MIT Press.
  11. [16]Aaronson S, Ambainis A 2009 The need for structure in quantum speedups. (http://arxiv.org/abs/0911.0996). · arXiv
  12. [17]Preskill J 1998 Fault-tolerant quantum computation. (https://arxiv.org/abs/quant-ph/9712048) · arXiv
  13. [18]Papadimitriou CH 2003 Computational complexity. New York, NY: John Wiley and Sons Ltd.
  14. [21]Vapnik VN 1998 Statistical learning theory, vol. 1 New York, NY: Wiley.
  15. [22]Bauer F, Pereverzev S, Rosasco L 2007 On regularization algorithms in learning theory. J. Complex. 23, 52– 72. (doi:10.1016/j.jco.2006.07.001) · DOI
  16. [23]Cucker F, Smale S 2002 On the mathematical foundations of learning. Bull. Amer. Math. Soc. 39, 1– 49. (doi:10.1090/S0273-0979-01-00923-5) · DOI
  17. [25]Zhang Y, Duchi J, Wainwright M 2013 Divide and conquer kernel ridge regression. In Conf. on Learning Theory, Princeton, NJ, pp. 592–617. Brookline, MA: Microtome Publishing.
  18. [26]Rahimi A, Recht B 2007 Random features for large-scale kernel machines. In Advances Neural Information Processing Systems (eds JC Platt, D Koller, Y Singer, ST Roweis), vol. 3, pp. 1177–1184. Red Hook, NY: Curran Associates, Inc.
  19. [27]Smola AJ, Schölkopf B 2000 Sparse greedy matrix approximation for machine learning. In Proc. of the Int. Conf. on Machine Learning, pp. 911–918. San Francisco, CA: Morgan Kaufmann Publishers.
  20. [28]Williams CK, Seeger M 2000 Using the Nyström method to speed up kernel machines. In Proc. of the 13th Int. Conf. on Neural Information Processing Systems, Vancouver, Canada, pp. 661–667. Cambridge, MA: The MIT Press.
  21. [29]Rudi A, Camoriano R, Rosasco L 2015 Less is more: Nyström computational regularization. In Advances in Neural Information Processing Systems (eds C Cortes, ND Lawrence, DD Lee, M Sugiyama, R Garnett), pp. 1657–1665. Red Hook, NY: Curran Associates, Inc.
  22. [31]Bshouty NH, Jackson JC 1998 Learning DNF over the uniform distribution using a quantum example oracle. SIAM J. Comput. 28, 1136– 1153. (doi:10.1137/S0097539795293123) · DOI
  23. [32]Servedio RA, Gortler SJ 2004 Equivalences and separations between quantum and classical learnability. SIAM J. Comput. 33, 1067– 1092. (doi:10.1137/S0097539704412910) · DOI
  24. [33]Atici A, Servedio RA 2005 Improved bounds on quantum learning algorithms. Quantum Inf. Process. 4, 355– 386. (doi:10.1007/s11128-005-0001-2) · DOI
  25. [34]Zhang C 2010 An improved lower bound on query complexity for quantum PAC learning. Inf. Process. Lett. 111, 40– 45. (doi:10.1016/j.ipl.2010.10.007) · DOI
  26. [35]Arunachalam S, de Wolf R 2017 Optimal quantum sample complexity of learning algorithms. In Proc. 32nd Computational Complexity Conference, CCC 2017, Riga, Latvia, 6–9 July 2017. LIPIcs 79. Wadern, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
  27. [36]Angluin D 1988 Queries and concept learning. Mach. Learn. 2, 319– 342. (doi:10.1023/A:1022821128753) · DOI
  28. [37]Bshouty NH, Cleve R, Kannan S, Tamon C 1994 Oracles and queries that are sufficient for exact learning. In Proc. of the 7th Annu. Conf. on Computational Learning Theory, New Brunswick, NJ, pp. 130–139. New York, NY: ACM.
  29. [38]Klivans AR, Servedio R 2001 Learning DNF in time. In Proc. of the 33rd Annu. ACM Symp. on Theory of Computing, Crete, Greece, pp. 258–265. New York, NY: ACM.
  30. [39]Verbeurgt KA 1990 Learning DNF under the uniform distribution in quasi-polynomial time. In COLT ’90: Proc. of the 3rd Annu. Workshop on Computational Learning Theory, pp. 314–326. Cambridge, MA: The MIT Press.
  31. [43]Kearns M, Valiant L 1994 Cryptographic limitations on learning Boolean formulae and finite automata. J. ACM 41, 67– 95. (doi:10.1145/174644.174647) · DOI
  32. [44]Aaronson S 2013 Quantum computing since Democritus. Cambridge, MA: Cambridge University Press.
  33. [45]Giovannetti V, Lloyd S, Maccone L 2008 Quantum random access memory. Phys. Rev. Lett. 100, 160501 (doi:10.1103/PhysRevLett.100.160501) 18518173 · DOI · Paper page
  34. [46]Giovannetti V, Lloyd S, Maccone L 2008 Architectures for a quantum random access memory. Phys. Rev. A 78, 052310 (doi:10.1103/PhysRevA.78.052310) 18518173 · DOI · Paper page
  35. [48]Arunachalam S, Gheorghiu V, Jochym-O’Connor T, Mosca M, Srinivasan PV 2015 On the robustness of bucket brigade quantum RAM. New. J. Phys. 17, 123010 (doi:10.1088/1367-2630/17/12/123010) · DOI
  36. [50]Steiger DS, Troyer M 2016 Racing in parallel: quantum versus classical. Quantum Machine Learning Workshop. Waterloo, Canada: Perimeter Institute for Theoretical Physics. See http://pirsa.org/displayFlash.php?id=16080019.
  37. [51]Csanky L 1976 Fast parallel matrix inversion algorithms. SIAM J. Comput. 5, 618– 623. (doi:10.1137/0205040) · DOI
  38. [52]Prakash A 2014 Quantum algorithms for linear algebra and machine learning. PhD thesis, University of California, Berkeley, CA, USA.
  39. [54]Grover L, Rudolph T 2002 Creating superpositions that correspond to efficiently integrable probability distributions. (http://arxiv.org/abs/quant-ph/0208112). · arXiv
  40. [56]Frieze A, Kannan R, Vempala S 2004 Fast Monte-Carlo algorithms for finding low-rank approximations. J. ACM 51, 1025– 1041. (doi:10.1145/1039488.1039494) · DOI
  41. [60]Kerenidis I, Prakash A 2017 Quantum recommendation systems. In Proc. 8th Innovations in Theoretical Computer Science Conf., ITCS 2017, Berkeley, CA, 9–11 January 2017. LIPIcs 67. Wadern, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
  42. [61]Zhao Z, Fitzsimons JK, Fitzsimons JF 2015 Quantum assisted Gaussian process regression. (http://arxiv.org/abs/1512.03929). · arXiv
  43. [62]Schuld M, Sinayskiy I, Petruccione F 2016 Prediction by linear regression on a quantum computer. Phys. Rev. A 94, 022342 (doi:10.1103/PhysRevA.94.022342) · DOI
  44. [63]Cosnard M, Robert Y 1986 Complexity of parallel QR factorization. J. ACM 33, 712– 723. (doi:10.1145/6490.214102) · DOI
  45. [64]Li S 2009 Fast algorithms for sparse matrix inverse computations. PhD Thesis, Stanford University, Stanford, CA, USA.
  46. [66]Halko N, Martinsson P-G, Tropp JA 2011 Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53, 217– 288. (doi:10.1137/090771806) · DOI
  47. [69]Ambainis A 2012 Variable time amplitude amplification and quantum algorithms for linear algebra problems. In Proc. 29th Int. Symp. on Theoretical Aspects of Computer Science, STACS 2012, Paris, France, 29 February–3 March 2012. LIPIcs 14. Wadern, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
  48. [70]Childs AM, Kothari R, Somma RD 2015 Quantum linear systems algorithm with exponentially improved dependence on precision. (http://arxiv.org/abs/1511.02306). · arXiv
  49. [71]Clader BD, Jacobs BC, Sprouse CR 2013 Preconditioned quantum linear system algorithm. Phys. Rev. Lett. 110, 250504 (doi:10.1103/PhysRevLett.110.250504) 23829722 · DOI · Paper page
  50. [72]Wossnig L, Zhao Z, Prakash A 2017 A quantum linear system algorithm for dense matrices. (http://arxiv.org/abs/1704.06174). · arXiv
  51. [73]Childs AM 2009 Quantum algorithms: equation solving by simulation. Nat. Phys. 5, 861–861 (doi:10.1038/nphys1473) · DOI
  52. [74]Spielman DA, Teng S-H 2004 Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51, 385– 463. (doi:10.1145/990308.990310) · DOI · Paper page
  53. [75]Spielman DA, Teng S-H 2009 Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM 52, 76– 84. (doi:10.1145/1562764.1562785) · DOI
  54. [76]Duchi JC, Mackey LW, Jordan MI 2010 On the consistency of ranking algorithms. In Proc. of the 27th Int. Conf. on Machine Learning (ICML-10), Haifa, Israel, pp. 327–334. Brookline, MA: Microtome Publishing.
  55. [77]Caponnetto A, De Vito E 2007 Optimal rates for the regularized least-squares algorithm. Found. Comput. Math. 7, 331– 368. (doi:10.1007/s10208-006-0196-8) · DOI
  56. [78]Heller D 1978 A survey of parallel algorithms in numerical linear algebra. SIAM Rev. 20, 740– 777. (doi:10.1137/1020096) · DOI
  57. [79]Jolliffe IT 1986 Principal component analysis, pp. 115–128. New York, NY: Springer.
  58. [81]Szegedy M 2004 Quantum speed-up of Markov chain based algorithms. In Proc. 45th Annu. IEEE Symp. on Foundations of Computer Science, Rome, Italy, pp. 32–41. New York, NY: IEEE.
  59. [83]Neal RM 2001 Annealed importance sampling. Stat. Comput. 11, 125– 139. (doi:10.1023/A:1008923215028) · DOI
  60. [84]Gilks WR, Wild P 1992 Adaptive rejection sampling for Gibbs sampling. Appl. Stat. 41, 337– 348. (doi:10.2307/2347565) · DOI
  61. [85]Propp JG, Wilson DB 1996 Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Struct. Algorithms 9, 223– 252. (doi:10.1002/(SICI)1098-2418(199608/09)9:1/2<223::AID-RSA14>3.0.CO;2-O) · DOI
  62. [86]Doucet A, De Freitas N, Gordon N 2001 Sequential Monte Carlo methods in practice, pp. 3–14. New York, NY: Springer.
  63. [87]Del Moral P, Doucet A, Jasra A 2006 Sequential Monte Carlo samplers. J. R. Stat. Soc. 68, 411– 436. (doi:10.1111/j.1467-9868.2006.00553.x) · DOI
  64. [88]Sinclair A 1993 Markov chains and rapid mixing. In Algorithms for random generation and counting: a Markov chain approach, pp. 42–62. Berlin, Germany: Springer.
  65. [89]Wocjan P, Chiang C-F, Nagaj D, Abeyesinghe A 2009 Quantum algorithm for approximating partition functions. Phys. Rev. A 80, 022340 (doi:10.1103/PhysRevA.80.022340) · DOI
  66. [90]Somma R, Boixo S, Barnum H, Knill E 2008 Quantum simulations of classical annealing processes. Phys. Rev. Lett. 101, 130504 (doi:10.1103/PhysRevLett.101.130504) 18851429 · DOI
  67. [91]Poulin D, Wocjan P 2009 Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer. Phys. Rev. Lett. 103, 220502 (doi:10.1103/PhysRevLett.103.220502) 20366078 · DOI
  68. [93]Bilgin E, Boixo S 2010 Preparing thermal states of quantum systems by dimension reduction. Phys. Rev. Lett. 105, 170405 (doi:10.1103/PhysRevLett.105.170405) 21231028 · DOI
  69. [94]Temme K, Osborne TJ, Vollbrecht KG, Poulin D, Verstraete F 2011 Quantum metropolis sampling. Nature 471, 87– 90. (doi:10.1038/nature09770) 21368829 · DOI · Paper page
  70. [95]Schwarz M, Temme K, Verstraete F 2012 Preparing projected entangled pair states on a quantum computer. Phys. Rev. Lett. 108, 110502 (doi:10.1103/PhysRevLett.108.110502) 22540445 · DOI
  71. [96]Chowdhury AN, Somma RD 2016 Quantum algorithms for Gibbs sampling and hitting-time estimation. (http://arxiv.org/abs/1603.02940). · arXiv
  72. [97]Ambainis A, Kempe J, Rivosh A 2005 Coins make quantum walks faster. In Proc. of the 16th Annu. ACM-SIAM Symp. on Discrete algorithms, Stockholm, Sweden, pp. 1099–1108. Philadelphia, PA: Society for Industrial and Applied Mathematics.
  73. [98]Krovi H, Brun TA 2006 Hitting time for quantum walks on the hypercube. Phys. Rev. A 73, 032341 (doi:10.1103/PhysRevA.73.032341) · DOI
  74. [99]Krovi H, Ozols M, Roland J 2010 Adiabatic condition and the quantum hitting time of Markov chains. Phys. Rev. A 82, 022333 (doi:10.1103/PhysRevA.82.022333) · DOI
  75. [101]Knill E, Ortiz G, Somma RD 2007 Optimal quantum measurements of expectation values of observables. Phys. Rev. A 75, 012328 (doi:10.1103/PhysRevA.75.012328) · DOI
  76. [102]Vandenberghe L, Boyd S 1996 Semidefinite programming. SIAM Rev. 38, 49– 95. (doi:10.1137/1038003) · DOI
  77. [103]Grötschel M, Lovász L, Schrijver A 2012 Geometric algorithms and combinatorial optimization, vol. 2 Berlin, Germany: Springer Science & Business Media.
  78. [105]Weinberger KQ, Sha F, Zhu Q, Saul LK 2007 Graph Laplacian regularization for large-scale semidefinite programming. In Advances in Neural Information Processing Systems (eds JC Platt, D Koller, Y Singer, ST Roweis), pp. 1489–1496. Red Hook, NY: Curran Associates, Inc.
  79. [106]Jacob L, Obozinski G, Vert J-P 2009 Group Lasso with overlap and graph Lasso. In Proc. of the 26th Annu. Int. Conf. on Machine Learning, Montreal, Canada, pp. 433–440. New York, NY: ACM.
  80. [107]Lee YT, Sidford A, Wong SC-W 2015 A faster cutting plane method and its implications for combinatorial and convex optimization. In Proc. 2015 IEEE 56th Annu. Symp. on Foundations of Computer Science (FOCS), Berkeley, CA, pp. 1049–1065. New York, NY: IEEE.
  81. [108]Arora S, Kale S 2007 A combinatorial, primal-dual approach to semidefinite programs. In Proc. of the 39th Annu. ACM Symp. on Theory of Computing, San Diego, CA, pp. 227–236. New York, NY: ACM.
  82. [109]Brandão FGSL, Svore K 2016 Quantum speed-ups for semidefinite programming. (http://arxiv.org/abs/1609.05537). · arXiv
  83. [110]van Apeldoorn J, Gilyén A, Gribling S, de Wolf R 2017 Quantum SDP-solvers: better upper and lower bounds. (http://arxiv.org/abs/1705.01843). · arXiv
  84. [112]Farhi E, Goldstone J, Gutmann S 2014 A quantum approximate optimization algorithm. (http://arxiv.org/abs/1411.4028). · arXiv
  85. [113]Farhi E, Goldstone J, Gutmann S, Neven H 2017 Quantum algorithms for fixed qubit architectures. (http://arxiv.org/abs/1703.06199). · arXiv
  86. [114]Farhi E, Goldstone J, Gutmann S 2014 A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem. (http://arxiv.org/abs/1412.6062). · arXiv
  87. [115]Barak B et al. 2015 Beating the random assignment on constraint satisfaction problems of bounded degree. (http://arxiv.org/abs/1505.03424). · arXiv
  88. [116]Farhi E, Goldstone J, Gutmann S, Sipser M 2000 Quantum computation by adiabatic evolution. (http://arxiv.org/abs/quant-ph/0001106). · arXiv
  89. [117]Kirkpatrick S 1984 Optimization by simulated annealing: quantitative studies. J. Stat. Phys. 34, 975– 986. (doi:10.1007/BF01009452) · DOI
  90. [118]Messiah A 1958 Quantum mechanics, vol. 1 New York, NY: Interscience.
  91. [119]Reichardt BW 2004 The quantum adiabatic optimization algorithm and local minima. In Proc. of the 36th Annu. ACM Symp. on Theory of Computing, Chicago, IL, pp. 502–510. New York, NY: ACM.
  92. [120]Crosson E, Harrow AW 2016 Simulated quantum annealing can be exponentially faster than classical simulated annealing. In Proc. 2016 IEEE 57th Annu. Symp. on Foundations of Computer Science (FOCS), New Brunswick, NJ, pp. 714–723. New York, NY: IEEE.
  93. [122]Barahona F 1982 On the computational complexity of Ising spin glass models. J. Phys. A 15, 3241– 3253. (doi:10.1088/0305-4470/15/10/028) · DOI
  94. [123]Farhi E, Goldstone J, Gutmann S 2000 A numerical study of the performance of a quantum adiabatic evolution algorithm for satisfiability. (http://arxiv.org/abs/quant-ph/0007071). · arXiv
  95. [124]Farhi E, Goldstone J, Gutmann S, Lapan J, Lundgren A, Preda D 2001 A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292, 472– 475. (doi:10.1126/science.1057726) 11313487 · DOI · Paper page
  96. [125]Farhi E, Gosset D, Hen I, Sandvik A, Shor P, Young A, Zamponi F 2012 Performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs. Phys. Rev. A 86, 052334 (doi:10.1103/PhysRevA.86.052334) · DOI
  97. [126]Hen I, Young A 2011 Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems. Phys. Rev. E 84, 061152 (doi:10.1103/PhysRevE.84.061152) 22304085 · DOI
  98. [127]Young AP, Knysh S, Smelyanskiy VN 2008 Size dependence of the minimum excitation gap in the quantum adiabatic algorithm. Phys. Rev. Lett. 101, 170503 (doi:10.1103/PhysRevLett.101.170503) 18999732 · DOI
  99. [128]Young A, Knysh S, Smelyanskiy V 2010 First-order phase transition in the quantum adiabatic algorithm. Phys. Rev. Lett. 104, 020502 (doi:10.1103/PhysRevLett.104.020502) 20366577 · DOI
  100. [129]Kak S 1995 On quantum neural computing. Inf. Sci. (NY) 83, 143– 160. (doi:10.1016/0020-0255(94)00095-S) · DOI
  101. [131]Long PM, Servedio R 2010 Restricted Boltzmann machines are hard to approximately evaluate or simulate. In Proc. of the 27th Int. Conf. on Machine Learning (ICML-10), Haifa, Israel, pp. 703–710. Brookline, MA: Microtome Publishing.
  102. [132]Dumoulin V, Goodfellow IJ, Courville A, Bengio Y 2014 On the challenges of physical implementations of RBMs. In Proc. 28th AAAI Conf. on Artificial Intelligence, Quebec City, Canada, 27–31 July 2014. Palo Alto, CA: The AAAI Press.
  103. [134]Brassard G, Hoyer P, Mosca M, Tapp A 2002 Quantum amplitude amplification and estimation. Contemp. Math. 305, 53– 74. (doi:10.1090/conm/305/05215) · DOI · Paper page
  104. [136]Wiebe N, Kapoor A, Granade C, Svore KM 2015 Quantum inspired training for Boltzmann machines. (http://arxiv.org/abs/1507.02642). · arXiv
  105. [138]Denil M, De Freitas N 2011 Toward the implementation of a quantum RBM. Paper presented at the Learning and Unsupervised Feature Learning Workshop of the 25th Ann. Conf. on Neural Information Processing Systems (NIPS), Granada, Spain, 2011.
  106. [140]Amin MH, Andriyash E, Rolfe J, Kulchytskyy B, Melko R 2016 Quantum Boltzmann machine. (http://arxiv.org/abs/1601.02036). · arXiv
  107. [141]Kieferova M, Wiebe N 2016 Tomography and generative data modeling via quantum Boltzmann training. (http://arxiv.org/abs/1612.05204). · arXiv
  108. [143]Cybenko G 1989 Approximation by superpositions of a sigmoidal function. Math. Control Signals Syst. 2, 303– 314. (doi:10.1007/BF02551274) · DOI · Paper page
  109. [146]Bishop CM 1995 Training with noise is equivalent to Tikhonov regularization. Neural. Comput. 7, 108– 116. (doi:10.1162/neco.1995.7.1.108) · DOI · Paper page
  110. [147]An G 1996 The effects of adding noise during backpropagation training on a generalization performance. Neural. Comput. 8, 643– 674. (doi:10.1162/neco.1996.8.3.643) · DOI · Paper page
  111. [148]Neelakantan A, Vilnis L, Le QV, Sutskever I, Kaiser L, Kurach K, Martens J 2015 Adding gradient noise improves learning for very deep networks. (http://arxiv.org/abs/1511.06807). · arXiv
  112. [149]Bottou L 1991 Stochastic gradient learning in neural networks. In Proc. Neuro-Nımes. 91. Nimes, France: EC2.
  113. [150]Welling M, Teh YW 2011 Bayesian learning via stochastic gradient Langevin dynamics. In Proc. of the 28th Int. Conf. on Machine Learning (ICML-11), Bellevue, WA, pp. 681–688. Brookline, MA: Microtome Publishing.
  114. [151]Goodfellow I, Pouget-Abadie J, Mirza M, Xu B, Warde-Farley D, Ozair S, Courville A, Bengio Y 2014 Generative adversarial nets. In Advances in Neural Information Processing Systems (eds Z Ghahramani, M Welling, C Cortes, ND Lawrence, KQ Weinberger), pp. 2672–2680. Red Hook, NY: Curran Associates, Inc.
  115. [152]Szegedy C, Vanhoucke V, Ioffe S, Shlens J, Wojna Z 2016 Rethinking the inception architecture for computer vision. In Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition, Las Vegas, NV, pp. 2818–2826. New York, NY: IEEE.
  116. [153]Salimans T, Goodfellow I, Zaremba W, Cheung V, Radford A, Chen X 2016 Improved techniques for training gans. In Advances in Neural Information Processing Systems (eds DD Lee, M Sugiyama, UV Luxburg, I Guyon, R Garnett), pp. 2234–2242. Red Hook, NY: Curran Associates, Inc.
  117. [154]Warde-Farley D, Goodfellow I 2016 Adversarial perturbations of deep neural networks. In Perturbation, optimization, and statistics (eds T Hazan, G Papandreou, D Tarlow), pp. 311–342. Cambridge, MA: The MIT Press.
  118. [156]Blum A, Furst M, Jackson J, Kearns M, Mansour Y, Rudich S 1994 Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In Proc. of the 26th Annu. ACM Symp. on Theory of Computing, Santa Fe, NM, pp. 253–262. New York, NY: ACM.
  119. [157]Cross AW, Smith G, Smolin JA 2015 Quantum learning robust against noise. Phys. Rev. A 92, 012327 (doi:10.1103/PhysRevA.92.012327) · DOI · Paper page
  120. [158]Lyubashevsky V 2005 The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In Approximation, randomization and combinatorial optimization. Algorithms and techniques (eds M Goemans, K Jansen, JDP Rolim, L Trevisan), pp. 378–389. Berlin, Germany: Springer.
  121. [159]Berlekamp E, McEliece R, Van Tilborg H 1978 On the inherent intractability of certain coding problems (corresp.). IEEE Trans. Inf. Theory 24, 384– 386. (doi:10.1109/TIT.1978.1055873) · DOI
  122. [160]Håstad J 2001 Some optimal inapproximability results. J. ACM 48, 798– 859. (doi:10.1145/502090.502098) · DOI · Paper page
  123. [161]Grilo AB, Kerenidis I 2017 Learning with errors is easy with quantum samples. (http://arxiv.org/abs/1702.08255). · arXiv
  124. [162]Fortnow L 2009 The status of the P versus NP problem. Commun. ACM 52, 78– 86. (doi:10.1145/1562164.1562186) · DOI
  125. [163]Suchanek FM, Kasneci G, Weikum G 2007 Yago: a core of semantic knowledge. In Proc. of the 16th Int. Conf. on World Wide Web, Banff, Canada, pp. 697–706. New York, NY: ACM.
  126. [164]Dong X, Gabrilovich E, Heitz G, Horn W, Lao N, Murphy K, Strohmann T, Sun S, Zhang W 2014 Knowledge vault: a web-scale approach to probabilistic knowledge fusion. In Proc. of the 20th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, New York, NY, pp. 601–610. New York, NY: ACM.
  127. [165]Carlson A, Betteridge J, Kisiel B, Settles B, Hruschka ER Jr, Mitchell TM 2010 Toward an architecture for never-ending language learning. In Proc. of the 24th AAAI Conf. on Artificial Intelligence, Atlanta, GA, 11–15 July 2010, vol. 5, p. 3. Palo Alto, CA: Association for the Advancement of Artificial Intelligence.
  128. [167]Kolda TG, Bader BW 2009 Tensor decompositions and applications. SIAM Rev. 51, 455– 500. (doi:10.1137/07070111X) · DOI
  129. [168]Hillar CJ, Lim L-H 2013 Most tensor problems are NP-hard. J. ACM 60, 45 (doi:10.1145/2512329) · DOI
  130. [169]Mu C, Huang B, Wright J, Goldfarb D 2014 Square deal: lower bounds and improved relaxations for tensor recovery. In Proc. Int. Conf. on Machine Learning, Beijing, China, pp. 73–81. Brookline, MA: Microtome Publishing.
  131. [170]Richard E, Montanari A 2014 A statistical model for tensor PCA. In Advances in Neural Information Processing Systems (eds Z Ghahramani, M Welling, C Cortes, ND Lawrence, KQ Weinberger), pp. 2897–2905. Red Hook, NY: Curran Associates, Inc.
  132. [171]Romera-Paredes B, Pontil M 2013 A new convex relaxation for tensor completion. In Advances in Neural Information Processing Systems (eds CJC Burges, L Bottou, M Welling, Z Ghahramani, KQ Weinberger), pp. 2967–2975. Red Hook, NY: Curran Associates, Inc.
  133. [172]Romera-Paredes B, Aung H, Bianchi-Berthouze N, Pontil M 2013 Multilinear multitask learning. In Proc. Int. Conf. on Machine Learning, Atlanta, GA, pp. 1444–1452. Brookline, MA: Microtome Publishing.
  134. [173]Signoretto M, Dinh QT, De Lathauwer L, Suykens JA 2014 Learning with tensors: a framework based on convex optimization and spectral regularization. Mach. Learn. 94, 303– 351. (doi:10.1007/s10994-013-5366-3) · DOI
  135. [174]Gandy S, Recht B, Yamada I 2011 Tensor completion and low-n-rank tensor recovery via convex optimization. Inverse. Probl. 27, 025010 (doi:10.1088/0266-5611/27/2/025010) · DOI
  136. [175]Lin H, Bilmes J 2011 A class of submodular functions for document summarization. In Proc. of the 49th Annu. Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1, Association for Computational Linguistics, Portland, OR, pp. 510–520. Cambridge, MA: The MIT Press.
  137. [176]Kempe D, Kleinberg J, Tardos É 2003 Maximizing the spread of influence through a social network. In Proc. of the 9th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Washington, DC, pp. 137–146. New York, NY: ACM.
  138. [177]Narasimhan M, Bilmes JA 2007 Local search for balanced submodular clusterings. In IJCAI’07: Proc. of the 20th Int. Joint Conf. on Artificial Intelligence, Hyderabad, India, 6–12 January 2007, pp. 981–986. San Francisco, CA: Morgan Kaufmann Publishers.
  139. [178]Bach F 2015 Submodular functions: from discrete to continous domains. (http://arxiv.org/abs/1511.00394). · arXiv
  140. [179]Lovász L 1983 Submodular functions and convexity. In Mathematical programming: the state of the art (eds A Bachem, B Korte, M Grötschel), pp. 235–257. Berlin, Germany: Springer.
  141. [180]Schrijver A 2000 A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Comb. Theory 80, 346– 355. (doi:10.1006/jctb.2000.1989) · DOI
  142. [181]Iwata S, Fleischer L, Fujishige S 2001 A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48, 761– 777. (doi:10.1145/502090.502096) · DOI
  143. [182]Orlin JB 2009 A faster strongly polynomial time algorithm for submodular function minimization. Math. Program. 118, 237– 251. (doi:10.1007/s10107-007-0189-2) · DOI
  144. [183]Pearl J 1985 Bayesian networks: a model of self-activated memory for evidential reasoning. In Proc. of the 7th Conf. of the Cognitive Science Society, Irvine, CA, 15–17 August 1985, pp. 329–334. Austin, TX: Cognitive Science Society.
  145. [184]Kindermann R, Snell L 1980 Markov random fields and their applications, vol. 1. Providence, RI: American Mathematical Society.
  146. [185]Cooper GF 1990 The computational complexity of probabilistic inference using Bayesian belief networks. Artif. Intell. 42, 393– 405. (doi:10.1016/0004-3702(90)90060-D) · DOI
  147. [186]Lloyd S, Garnerone S, Zanardi P 2014 Quantum algorithms for topological and geometric analysis of big data. (http://arxiv.org/abs/1408.3106). PMC4737711 26806491 · arXiv

Authors
Ciliberto, C., Herbster, M., Ialongo, A. D., Pontil, M., Rocchetto, A., Severini, S., & Wossnig, L.
Affiliations
  • University College London (GB)
  • University of Cambridge (GB)
  • Italian Institute of Technology (IT)
  • University of Oxford (GB)
  • Department of Computer Science, University College London, London, UK
  • ETH Zurich (CH)
Corresponding author
Rocchetto, Andrea
ORCID
Venue
Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
Publisher
The Royal Society
Published
2018-01
Volume
474
Issue
2209
Pages
20170551
ISSN
  • 1364-5021 (ISSN-L)
  • 1471-2946
DOI
10.1098/rspa.2017.0551
PMC
PMC5806018
OpenAlex
W2736592352
Cited by
518
References
209
Citations by year
2026: 46 · 2025: 85 · 2024: 69 · 2023: 72 · 2022: 60 · 2021: 78 · 2020: 55 · 2019: 36 · 2018: 14 · 2017: 3
FWCI
5.28
Type
journal article
Language
en
Open access
Licence
Locations
  • Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences (publishedVersion, cc-by)
  • Europe PMC (PubMed Central) (publishedVersion, cc-by)
  • PubMed Central (publishedVersion, cc-by)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • UCL Discovery (University College London) (submittedVersion)
  • MPG.PuRe (Max Planck Society) (submittedVersion)
  • Repository for Publications and Research Data (ETH Zurich) (submittedVersion, cc-by)
  • arXiv (Cornell University)
  • ETH Zürich Research Collection (cc-by)
Funders
  • Innovate UK
  • Qualcomm Innovation Fellowship
  • The Royal Society
  • Cambridge-Tuebingen Fellowship
  • Engineering and Physical Sciences Research Council
  • National Natural Science Foundation of China
  • QinetiQ
  • Cambridge Quantum Computing
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
Keywords
quantum machine learning, quantum algorithms, classical machine learning, quantum advantage, quantum computing hardware

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review