PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum machine learning: a classical perspective

Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, Leonard Wossnig

arXiv:1707.08561v3quant-phcs.LGstat.ML

TL;DR

The paper reviews whether quantum computation can address the computational demands of machine learning as datasets grow and classical hardware approaches physical limits. It synthesizes QML advances and learning-theory results while examining data access, comparisons with classical methods, and practical caveats. The review identifies model-dependent learning advantages and promising applications, but emphasizes that current algorithms’ assumptions and memory-access requirements limit conclusions about practical impact.

  • Problem

    Growing datasets and the end of classical hardware scaling motivate examining whether quantum computation can speed up machine learning.

  • Method

    The paper reviews QML literature for a mixed audience, analyzing quantum learning models, algorithms, data access, sampling, and optimization through computational complexity.

  • Results

    Quantum learning theory shows model-dependent advantages: exact learning can reduce oracle queries polynomially, while quantum PAC learning can address functions hard for classical learners.

  • Takeaways & Limitations

    Quantum resources may help with selected learning problems, including computationally hard problems, sampling, and optimization, but benefits depend on the learning model and implementation assumptions.

  • Takeaways & Limitations

    Current QML approaches depend on fast memory access and practical loading of classical data into quantum superposition remains an open question.

Abstract

from arXiv · show

Recently, increased computational power and data availability, as well as algorithmic advances, have led machine learning 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 are motivating a growing number of researchers to explore the possibility of harnessing the power of quantum computation to speed-up classical machine learning algorithms. Here we review the literature in quantum machine learning and discuss perspectives for a mixed readership of classical machine learning 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 machine learning are identified as promising directions for the field. Practical questions, like how to upload classical data into quantum form, will also be addressed.

1 Introduction

The review examines quantum machine learning as a bridge between quantum computation and machine learning, motivated by growing datasets and limits of classical hardware. It emphasizes both potential advantages and practical caveats.

  • Motivation: Growing datasets and the end of Moore’s law may make current classical tools insufficient for machine learning.GPUs and TPUs can improve performance but may not provide a structural solution.
  • Scope: Quantum machine learning studies learning models that use quantum resources.The review distinguishes this focus from broader uses of machine learning to analyze quantum-system outputs.
  • Review aims: The review summarizes major QML advances for a mixed audience and analyzes many problems through computational complexity.It aims to bridge machine-learning and quantum-computation communities rather than provide a complete literature survey.
  • Potential advantages: Quantum algorithms may process selected classes of problems faster and, under assumptions, yield separations between classical and quantum learnability.These motivations are presented alongside the review’s emphasis on skepticism and applicability limits.
  • Caveats: Known QML algorithms have caveats that currently prevent concluding that quantum methods will significantly affect machine learning.The review discusses these caveats by comparing quantum methods with classical algorithms.

2 Essential quantum computation

This section introduces quantum information, computational complexity, and the query model used to describe quantum algorithms and their runtime advantages. It also highlights the contrast between compact quantum representations and practical noise and data-access constraints.

  • Quantum computation: Quantum computation uses quantum-mechanical effects such as interference and potentially entanglement to solve selected problems efficiently.These problems are believed to be hard for classical machines.
  • Quantum information: A qubit is represented as ψ = α0e0 + α1e1, with complex amplitudes whose squared magnitudes determine measurement probabilities.The passage also states that a qubit’s information content is equivalent to a single bit.
  • Data representation: Quantum states can represent classical probability distributions with exponentially many points using an n-qubit register.This encoding is introduced for analyzing classical data.
  • Noise: Practical quantum states are fragile and require error correction when physical errors remain below a correctable threshold.The review treats qubits as idealized, error-free objects in its theoretical discussion.
  • Complexity: Quantum speedup is defined as a runtime advantage over classical methods, measured through asymptotic operation counts such as O(f(n)) and ˜O(f(n)).The tilde notation ignores logarithmic factors.
  • Query model: The query model evaluates algorithms by the number of calls to efficiently implementable classical or quantum oracles.Many speedups discussed in the review are obtained in this model.

3 Setting the problem: perspectives in machine learning

The section frames machine learning around generalization and computational efficiency, focusing on regularization-based methods whose costs grow with training-set size. Classical alternatives reduce costs, while quantum algorithms may offer further speedups subject to data-access caveats.

  • Learning theory: PAC and statistical learning theory characterize learning efficiency through sample complexity and time complexity.Sample complexity concerns the number of examples needed, while time complexity concerns computational resources.
  • Learning objectives: Machine learning seeks models that predict well on new observations, not merely models that fit training data.Generalization capability distinguishes statistical learning from standard optimization.
  • Regularization: Regularization limits estimator expressiveness to reduce overfitting, supporting methods including regularized least squares, Gaussian processes, logistic regression, and SVMs.These strategies impose constraints on the hypothesis class or add penalty terms.
  • Classical computational costs: O(N^3) time complexity commonly arises because Gaussian-process and SVM algorithms perform operations comparable to inverting an N-sized square matrix.Increasing dataset sizes are pushing these methods toward the limits of practical applicability.
  • Alternative regularization: Early stopping and divide-and-conquer reduce computational costs while retaining the same generalization performance or statistical guarantees as classical methods.Divide-and-conquer distributes portions of the training data across machines and combines the resulting predictors.
  • Classical alternatives: Training times can typically decrease from O(N^3) to ˜O(N^2) while preserving essentially unchanged statistical performance.The cited reduction applies across the described regularization-based methods.
  • Quantum prospects: Quantum linear-algebra, sampling, and optimization algorithms could in principle provide up to exponential speedups, but current methods require fast memory access and data-loading procedures.These requirements complicate scaling to modern datasets.

4 “Can we do better?”: insights from quantum learning theory

Quantum learning theory compares quantum and classical learners under different learning models. It finds no general sample-complexity reduction in the quantum PAC model, but identifies model-dependent advantages in time complexity and learnability.

  • Sample complexity: In the quantum PAC model, quantum and classical learners require equivalent sample complexity up to constant factors under unknown distributions.Thus quantum mechanics does not generally reduce the amount of data required for learning.
  • Query complexity: Exact learning can make quantum learners polynomially more efficient than classical learners in the number of queries to the data oracle.This advantage depends on changing the learning model from standard PAC learning.
  • Hard learning problems: The best known algorithm for learning DNFs under an unknown distribution has exponential time complexity.Under a uniform-distribution assumption, the best learner’s runtime becomes quasipolynomial.
  • Quantum learnability: A function class believed hard for classical learners under the hardness of factoring Blum integers can be learned efficiently in the quantum PAC model.The quantum advantage follows from using Shor’s quantum factoring algorithm.
  • Supported advantages: Depending on the learning model, quantum resources can improve generalization error or enable learning functions otherwise hard for classical learners.The review presents these as results from quantum learning theory rather than universal benefits.

5 Data access, communication and parallelism

Quantum machine learning with classical data depends on how efficiently data can be encoded into quantum states. QRAM can provide fast access, but its physical resources, error-correction demands, comparison with parallel architectures, data-distribution assumptions, and communication latency constrain claimed advantages.

  • Data access: Quantum machine learning algorithms process quantum data directly or encode classical-memory data into quantum states, making encoding cost central to quantum speedups.Quantum data is ready for analysis, whereas classical data requires an additional encoding procedure.
  • Data access: QRAM encodes N d-dimensional vectors into log(Nd) qubits in O(log(Nd)) time, while requiring O(Nd) physical resources.Its bucket-brigade architecture stores vector entries at the leaves of a tree structure.
  • Implementation caveats: Error-correction requirements depend on query complexity: polynomial-query algorithms may avoid fault-tolerant components under an error model, whereas superpolynomial-query algorithms require them.Grover search is given as an example of a superpolynomial-query algorithm with this requirement.
  • Parallelism: An exponential-resource QRAM should be compared with a parallel architecture having a similar processor count, under which some linear-algebra routines run in logarithmic time.The comparison applies to routines including solving linear systems and singular value decomposition.
  • Data and communication limits: Non-uniformly distributed data can make QRAM inefficient, and communication latency becomes a potential caveat when memory is extremely large.The review notes that these concerns matter because QML targets datasets exceeding current classical-computing capability.

6 Fast linear algebra with quantum mechanics

Quantum linear-algebra methods target matrix inversion and singular-value estimation in learning, but data access, readout, conditioning, and comparison with classical methods constrain their practical advantages.

  • Quantum linear-algebra subroutines support machine-learning applications including matrix inversion, singular-value estimation, recommendation systems, linear regression, and principal component analysis.
  • The QLSA promises matrix inversion in ˜O(log(N)κ^2s^2/ǫ), with κ, s, and ǫ denoting condition number, sparsity, and approximation precision.
  • QLSA applicability is limited by sparsity, logarithmic-time quantum data loading, quantum-state output, and a condition number scaling at most sublinearly with N.
  • The QLSA output cannot generally be read as a classical vector efficiently, because retrieving classical information may require measurements proportional to N.
  • Classical sampling can estimate x^T Ax in time linear in matrix sparsity, while conjugate gradients can solve the full system in linear dimensionality and often sparsity.
  • Quantum algorithms may lose their advantages when compared with classical or parallel methods under the same caveats, and asymptotic scalings require hardware benchmarking for validation.
  • Under standard assumptions, kernel regularized least squares and quantum inversion both scale as ˜O(N^2), while the classical method provides the full solution vector.
  • QSVE estimates singular values with |σ_i−˜σ_i|≤ǫ, but reading all r values requires O(N log N) runs; a low-rank recommendation system can nevertheless run in O(poly(r)poly log(MN)).

7 Quantum methods for sampling

Sampling methods approximate otherwise intractable learning quantities, while quantum approaches aim for quadratic speedups in parameters governing stochastic-process simulation.

  • Exact inference in graphical models can be intractable, motivating sampling methods to approximate the required quantities.
  • MCMC samples from a target distribution through a Markov chain that approaches an ǫ-close distribution after a mixing time τ.
  • For classical MCMC, the mixing time scales as O(1/(δ log(1/Π*))), where δ is the spectral gap and Π* is the minimum distribution value.
  • Quantum stochastic-process algorithms commonly provide quadratic speedups in spectral gap, inverse temperature, precision, or hitting time.

8 Quantum optimisation

Quantum optimisation methods address semidefinite programs and constraint satisfaction, with potential speedups that depend strongly on problem parameters and lack definitive practical evidence.

  • Quantum optimisation tools target two broad classes: semidefinite programming and constraint satisfaction problems.
  • Semidefinite programming: The best known classical SDP solver has runtime O(m(m^2+n^ω+mns)log^O(1)(mnR/ǫ)), involving constraints, dimension, sparsity, trace, and precision.
  • Semidefinite programming: Quantum SDP algorithms are quadratically faster in m and n, with later work improving their dependence on error parameters.
  • Semidefinite programming: Quantum SDP speedups apply only when R, r, s, and 1/ǫ are fairly small compared with mn, and interesting examples satisfying this remain unclear.
  • Constraint satisfaction: QAOA approximates constraint-satisfaction problems using an integer depth parameter p, with better approximations as p increases and shallow circuits for small p.
  • Constraint satisfaction: For some combinatorial problems, QAOA beats random sampling but remains worse than the best classical solvers; a classical algorithm later outperformed its proposed MAX-kXOR scaling.
  • Quantum adiabatic algorithm: QAA can outperform classical simulated annealing when energy barriers are tall and narrow and the relevant energy gap remains sufficiently large.
  • Quantum adiabatic algorithm: AQC can encode NP-hard problems but is not expected to solve them in polynomial time, and QAA lacks worst-case runtime upper bounds.

9 Quantum neural networks

Quantum neural-network research explores quantum training of classical models and fully quantum networks, but nonlinearity, convergence, hardware constraints, and demonstrated advantage remain unresolved.

  • Quantum neural-network research focuses on accelerating classical-model training and building networks whose neurons and training algorithms run quantum mechanically.
  • Restricted Boltzmann machines: RBMs are prominent because their generative-model structure connects strongly to Ising models, while sampling and likelihood computation are computationally hard.
  • Restricted Boltzmann machines: Quantum linear-algebra and sampling methods can reduce RBM training cost, including a quadratic improvement in the number of examples required.
  • Restricted Boltzmann machines: Quantum-annealing implementations generate Gibbs samples for RBM training, but noise, connectivity, and parameter-tuning limitations of early machines constrain applicability.
  • Quantum Boltzmann machines: Quantum Boltzmann machines add off-diagonal quantum terms that may model problems difficult to represent classically, but their advantage for classical tasks is unknown.
  • Quantum artificial neural networks: Quantum ANNs face a structural challenge because quantum mechanics is linear whereas ANNs require nonlinear transformations.
  • Quantum artificial neural networks: Measurement-based proposals model nonlinearities with overhead qubits, but retain classical parameters and lack proof of polynomial-iteration convergence.

10 Learning with noise

Noise can sometimes improve classical learning, and selected quantum learning results suggest noise may enable efficient solutions to problems that are classically hard. The section reviews these classical effects, quantum error models, and emerging quantum–classical separations.

  • Classical learning with noise: Noise can alleviate local optima and improve generalisation in classical learning.Gradient perturbations can help escape local optima, while input or output perturbations can improve generalisation.
  • Quantum noise: Quantum noise is commonly modelled using bit flips and phase flips, while early devices may lack full error correction.This motivates searching for learning problems where noise is beneficial rather than purely destructive.
  • Outlook: The section identifies the relationship among quantum noise, generalisation, and computational hardness as an open research direction.Matching the distribution and structure of quantum noise to useful classical noise could support learning on non-fault-tolerant hardware.
  • Classical learning with noise: Noisy inputs are equivalent, up to noise-variance order, to Tikhonov-regularised training on noiseless inputs.The regularisation constrains the learned function to vary more slowly with its input.
  • Classical learning with noise: Noise can support practical learning procedures, including posterior sampling, better-conditioned Gaussian-process predictions, and more robust GAN classifiers.Gaussian output noise replaces inversion of K with inversion of K + σ2I; label smoothing can retain generator training signal and improve adversarial robustness.
  • Quantum learning under noise: Quantum resources efficiently learn noisy DNF and parity functions in settings where corresponding classical learning is hard or inefficient.Under the uniform distribution, quantum PAC learning of parity functions has only logarithmic overhead over the noiseless runtime; the DNF comparison is established in the statistical query model.

11 Computationally hard problems in machine learning

The review highlights machine-learning problems that are computationally hard or polynomial-time but practically intractable, while cautioning that quantum computers are not expected to solve all such problems efficiently. It focuses on structures that quantum resources might exploit and on the costs of data access.

  • Quantum speedups and hardness: Quantum speedups of efficient classical algorithms can be polynomial or exponential, but exponential speedups for classical data require comparably fast memory access.QRAM could provide the required access for logarithmic-time algorithms, but its construction presents important issues.
  • Quantum speedups and hardness: Exponential advantages can survive data-encoding costs for hard problems such as DNF learning, where the best classical algorithm is superpolynomial.The review presents DNF learnability as an example of a possible exponential separation, although its practical applications are limited.
  • Quantum speedups and hardness: The review does not expect quantum computers to efficiently solve all machine-learning problems believed to be computationally hard, including some NP-hard problems.It instead seeks hard problems with structures exploitable by quantum computation.
  • Tensor factorisation: Low-rank tensor factorisation becomes NP-hard at higher orders, and no standard solution has yet been proposed despite further relaxations.This contrasts with matrix factorisation, which is amenable to efficient computation.
  • Submodular optimisation: Submodular optimisation supports efficient learning algorithms through convex formulations, but some instances have high-order polynomial runtimes such as O(n5).The review presents these problems as candidates where even polynomial quantum speedups could matter practically.
  • Graphical models: Graphical models encode probabilistic dependencies in graphs, enabling operations such as marginalisation and conditioning through connectivity-aware algorithms.Bayesian networks are directed acyclic graphs, whereas Markov random fields are undirected graphs.

12 Conclusions and outlook

The review finds promising quantum approaches across linear algebra, neural networks, sampling, and optimisation, but concludes that realistic exponential advantage remains unestablished. It identifies noise, complexity, QRAM, and hard learning problems as priorities for future work.

  • Conclusions: The current theoretical evidence does not establish an exponential quantum advantage in a realistic learning setting.The authors emphasise that further progress requires significant interaction between quantum-computation and machine-learning communities.
  • Scope: The review’s computational focus facilitates discussion of runtime acceleration but leaves statistical questions such as generalisation performance equally relevant.This is a scope consideration for interpreting the survey’s conclusions.
  • Conclusions: Quantum methods reduce the complexity of some regularisation methods, with linear-algebra approaches promising exponential advantages and other categories mostly providing quadratic advantages.Neural-network, sampling, and optimisation methods may be implementable on first-generation quantum computers, although their theoretical framework remains incomplete.
  • Conclusions: The extent of quantum speedups and their impact on practical problems remains an open question.The review therefore treats existing results as suggesting possibility rather than establishing practical impact.
  • Outlook: Future research should examine noise, generalisation, and hardness tradeoffs; quantum sample and time complexity; large-scale QRAM construction; and efficiently solvable non-polynomial learning problems.These directions are linked to first-generation hardware, statistical learning theory, large datasets, and uncontroversial learning speedups.

Funding statement

The paper lists fellowship, academic, industry, and public-research support for its authors.

  • Support: AI is supported by the Cambridge-Tuebingen Fellowship and the Qualcomm Innovation Fellowship.
  • Support: AR is supported by an EPSRC DTP Scholarship and QinetiQ.
  • Support: CC and MP are supported by EPSRC, while SS is supported by The Royal Society, EPSRC, Innovate UK, Cambridge Quantum Computing, and the National Natural Science Foundation of China.
Loading 1707.08561v3…