PaperlayerView exact revision on arXiv

Source-linked AI summary

A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance

Yunfei Wang, Junyu Liu

arXiv:2401.11351v2quant-phcs.AIcs.LGstat.ML

TL;DR

Quantum machine learning spans promising applications but faces challenges from noise, trainability, and quantum-to-classical output. This review surveys NISQ and fault-tolerant approaches alongside statistical learning theory, and concludes that both current and future devices hold promise while practical progress depends on available quantum resources.

  • Problem

    Quantum machine-learning approaches face noise-related constraints and trainability challenges, including barren plateaus that can demand exponentially more resources.

    Source: §2.3 · p. 18, §2.3.1 · p. 19

  • Method

    The review synthesizes NISQ and fault-tolerant quantum machine-learning approaches, including variational circuits, classical shadows, and statistical learning theory.

    Source: §4 · p. 31, §5 · p. 40

  • Results

    The review concludes that both current NISQ devices and future fault-tolerant quantum computers hold promise for machine learning and data analysis.

    Source: §5 · p. 40

  • Takeaways & Limitations

    The near-term direction is to make the best use of limited quantum resources, with techniques developed in that period potentially valuable in the fault-tolerant era.

    Source: §5 · p. 41

    For certain operators, a small QNTK and slow convergence result when circuit depth L is not comparable to the Hilbert-space dimension N.

    Source: §2.2 · p. 17

Abstract

from arXiv · show

Quantum machine learning, which involves running machine learning algorithms on quantum devices, has garnered significant attention in both academic and business circles. In this paper, we offer a comprehensive and unbiased review of the various concepts that have emerged in the field of quantum machine learning. This includes techniques used in Noisy Intermediate-Scale Quantum (NISQ) technologies and approaches for algorithms compatible with fault-tolerant quantum computing hardware. Our review covers fundamental concepts, algorithms, and the statistical learning theory pertinent to quantum machine learning.

1. Introduction

The introduction frames quantum machine learning as a broad, still-developing field spanning quantum algorithms, machine learning, and quantum physics. This review focuses on machine-learning algorithms run on quantum devices, from NISQ methods to fault-tolerant approaches and statistical learning theory.

1. Introduction

  • Quantum computing may accelerate some machine-learning tasks, but the cited HHL complexity comparison depends on sparsity, fault tolerance, small condition numbers, and fast classical–quantum interfaces.The introduction notes that large-scale explicit realizations of HHL are not known at present.Source: §1 · p. 3
  • The review focuses on quantum algorithms designed for machine-learning purposes, while noting that the wider field also includes quantum tomography and machine learning applied to quantum physics.The introduction says there is no precise definition of quantum machine learning.Source: §1 · pp. 2–3
  • NISQ devices offer a setting for exploring machine learning despite noise, while constructing quantum error correction remains challenging.The introduction also looks ahead to fault-tolerant quantum computing and algorithms such as HHL and principal component analysis.Source: §1 · p. 4
  • Potential quantum speedups depend on the task: comparable average prediction accuracy may be achievable classically for classical information, while low worst-case error can yield an exponential complexity gap.The introduction also identifies the output problem as a challenge for variational quantum algorithms and connects it to classical shadows.Source: §1 · p. 5
  • The review covers NISQ developments, including variational algorithms, quantum neural tangent kernels, and barren plateaus, then surveys FTQC algorithms and quantum random access memory.Its later coverage includes shadow tomography, classical shadows, and applications involving quantum data and simulators.Source: §1 · pp. 5–6
  • The review excludes QML algorithms whose advantages rely on sampling-related statements, along with quantum error correction, quantum memory, and quantum data-center designs.Source: §1 · p. 6

2. Noisy intermediate-scale quantum (NISQ) era

The NISQ section distinguishes a hardware-defined era from the subjective notion of “near-term” and describes how noise constrains available algorithms. Most NISQ algorithms use hybrid quantum-classical variational circuits.

2. Noisy intermediate-scale quantum (NISQ) era

  • NISQ is a hardware-oriented term: noisy gates constrain circuits to shallow depths, with gates operating on qubits represented as nodes in a predefined graph.The passage attributes the term to John Preskill in 2018 [110].Source: §2 · p. 6
  • “Near-term” refers to algorithms designed for devices expected in the next few years, but the time span is subjective and does not itself imply absence of quantum error correction.Source: §2 · p. 6
  • Near-term algorithms may become infeasible if hardware progress fails to meet their experimental requirements.Source: §2 · p. 7
  • Most existing NISQ algorithms use hybrid quantum-classical variational methods, iteratively adjusting a parameterized quantum circuit while assigning some computation to classical hardware.Source: §2 · p. 7

2.1. Variational quantum algorithm (VQA)

The review presents variational quantum algorithms as four-part hybrid methods, then discusses choices for their objective, circuit, measurements, and classical optimization. It emphasizes NISQ hardware constraints and reports no established quantum advantage for NISQ VQAs.

2.1. Variational quantum algorithm (VQA)

  • No quantum advantage has yet been established for NISQ VQAs, which comprise an objective function, parameterized quantum circuit, measurement scheme, and classical optimizer.Source: §2.1 · p. 7

2.1.1. Objective function

  • VQA objectives can use Hamiltonian expectation values or alternatives such as fidelity-based costs, but cost-function choice affects convergence and can be tied to barren plateaus.The operator must be decomposable into terms measurable by the quantum processor.Source: §2.1.1 · pp. 8–9

2.1.2. Parameterized quantum circuits (PQC)

  • Parameterized circuits prepare states from classical parameters; problem-inspired ansätze encode system structure, while hardware-efficient ansätze use shallow gate layers suited to device constraints.Problem-inspired circuits can be difficult to realize on current hardware, which is constrained by coherence time, gate fidelity, and available gates.Source: §2.1.2 · pp. 9–12

2.1.3. Measurements

  • Measurement schemes estimate objective expectations; classical shadows use repeated random unitary transformations and computational-basis measurements to predict M expectation values from a shadow of size on the order of log M.Directly rotating into an observable’s diagonal basis can be computationally expensive on NISQ devices.Source: §2.1.3 · pp. 12–13

2.1.4. Optimization

  • Classical optimizers update circuit parameters, but limited coherence time constrains deep analytical-gradient circuits and measurement sampling can bottleneck runtime.The review discusses evolutionary algorithms, reinforcement learning, sequential minimal optimization, stochastic gradient descent, and gradient-free approaches.Source: §2.1.4 · pp. 13–15

2.2. Quantum neural tangent kernel

The section develops the QNTK as a first-principles account of variational-circuit training dynamics. It uses kernel behavior to distinguish convergence regimes, identify depth-related constraints, and estimate gradient-descent speed.

2.2. Quantum neural tangent kernel

  • For a constant QNTK, the continuous-time residual decays exponentially and model outputs converge to supervised targets.The QNTK also relates updates of model outputs to updates of residual training error.Source: §2.2 · pp. 15–16
  • A fluctuating QNTK corresponds to representation learning and prevents a closed-form residual trajectory, while a nearly constant kernel permits perturbative convergence analysis.The figure contrasts a constant-QNTK closed-form case with a nonlinear but nearly constant case.Source: §2.2 · p. 16, Figure 3 · p. 16
  • Under the k-design assumption, average QNTK scales with layer count while relative fluctuations shrink for L ≫ 1, yielding a nearly frozen kernel in deep quantum neural networks.The average QNTK is proportional to L, while its standard deviation is proportional to √L.Source: §2.2 · pp. 16–17
  • For certain operators such as Pauli matrices, K becomes proportional to L/N, so depth not comparable to Hilbert-space dimension N gives a small QNTK and slow convergence.The review describes this regime as undermining model practicality, akin to barren plateaus.Source: §2.2 · p. 17
  • Even outside the frozen limit, QNTK can approximately gauge gradient-descent speed, compare variational ansatzes, estimate runtime and iterations, and inform hardware design.The review suggests selecting the ansatz with the largest QNTK when estimating which runs fastest.Source: §2.2 · p. 17

2.3. Quantum landscapes and barren plateaus

This section surveys how barren plateaus, hardware noise, and laziness shape the trainability and resource demands of quantum machine learning. It describes proposed ways to address these challenges while noting that noise may sometimes help and laziness need not prevent efficient gradient descent.

2.3. Quantum landscapes and barren plateaus

  • Barren plateaus make quantum loss landscapes exponentially flat with problem size, requiring exponentially many shots to traverse narrow gorges and potentially undermining quantum speedup.The section frames barren plateaus as a no-go condition highlighting when variational quantum algorithms may underperform.Source: §2.3 · pp. 17–18
  • Deep hardware-efficient QNNs can develop barren plateaus from high expressivity and weak inductive bias; sharper priors via initialization, pretraining, or parameter correlation are proposed responses [8] [27] [60].For quantum tensor network circuits, classical optimization can be exponentially more efficient than quantum optimization.Source: §2.3 · p. 18
  • Global-observable losses can produce barren plateaus even in shallow circuits with sharp priors, whereas local observables avoid this issue.The passage attributes the global-observable problem to the exponential precision needed to compare objects in exponentially large Hilbert spaces.Source: §2.3 · p. 18
  • Excessive entanglement between visible qubits and hidden layers can induce barren plateaus as visible states concentrate near maximally mixed; taming entanglement is a proposed remedy [106].The passage links the concentration to information being stored in non-local correlations across qubits.Source: §2.3 · pp. 18–19

2.3.1. Influence of background noise

  • Hardware noise can compromise near-term QML assumptions: it affects deeper circuits, data preparation, quantum kernels, and QNN trainability, while its impact on classical simulability remains underexplored [27] [39] [53] [27].Noise-induced barren plateaus exponentially suppress relevant features as circuit depth increases, deforming inductive bias and reducing effective feature-space dimension.Source: §2.3.1 · p. 19
  • Noise responses include reducing error rates, partial error correction, shallow QNNs, mitigation, and noise-resilient designs, though mitigation may not fully resolve trainability issues [27] [24] [38] [42] [80] [35] [115].Shallow designs include QCNNs; noise-resilient designs can keep minima positions unchanged despite noise.Source: §2.3.1 · p. 19
  • A toy-model study found noisy performance exceeded noiseless counterparts, suggesting that below a threshold noise may help some QML programs [88].This qualifies the section’s discussion of error correction: eliminating all noise may not be necessary for certain applications.Source: §2.3.1 · pp. 19–20

2.3.2. Laziness

  • Laziness means exponentially suppressed variational-angle updates, distinct from the small loss changes defining barren plateaus; with sufficiently many trainable angles, gradient dynamics can remain efficient, though precision is vulnerable to noise [87].The account relates the distinction to overparametrization theory and the quantum neural tangent kernel; laziness also occurs in wide classical networks.Source: §2.3.2 · p. 20

3. Fault tolerant quantum computation (FTQC) algorithms

The section surveys fault-tolerant quantum algorithms, including Shor’s factoring algorithm and quantum simulation, and considers unresolved questions about practical quantum speedups. It also examines QRAM and alternatives for loading classical data into quantum algorithms, including QRAM designs and their hardware and scalability challenges.

3.1. Quantum phase estimation and quantum principle component analysis

  • O(log^2 d) computational and query complexity is stated for quantum PCA, versus O(d^2) classical PCA; its advantage requires physical quantum data.Quantum PCA uses density-matrix exponentiation and phase estimation to obtain eigenvalues and eigenvectors; the reported advantage is measured in queries to access the density matrix.Source: §3.1 · p. 23

3.2. Classical algorithm framework for dequantizating QML models

  • Tang dequantized the Kerenidis–Prakash recommendation system with a polynomially slower classical algorithm, highlighting the role of state-preparation assumptions.The corresponding sampling assumptions can let classical algorithms match quantum algorithms; the initial quantum proposal had shown exponential speedup over the best-known classical algorithms, though its provable exponential nature was uncertain.Source: §3.2 · p. 24
  • Classical frameworks [32] reproduce quantum SVT, PCA, and clustering bounds with suitable sampling assumptions and polynomial slowdowns, but those assumptions may fail for quantum-physics data [67].The SQ model in presumes polynomial-time access to density-matrix entries at exponentially precise accuracy, which may itself require exponentially many queries [37].Source: §3.2 · pp. 24–25

3.3. Harrow-Hassidim-Lloyd algorithm

  • O((log N)^2) quantum steps to output |x⟩ versus O(N log N) classical steps to find x is the stated HHL comparison.HHL approximately solves a linear system, but the comparison depends on meeting practical input, matrix, conditioning, and output requirements.Source: §3.3 · p. 26
  • HHL’s speedup depends on efficient preparation of a reasonably uniform |b⟩, efficient e^-iAt operations, a well-conditioned invertible A, and manageable output extraction.Measuring a particular entry x_i generally requires roughly N repetitions, which can erase the speedup.Source: §3.3 · pp. 26–27

3.3.1. Large scale machine learning models in fault tolerant era

  • Carleman linearization [90] can approximate nonlinear dissipative ODEs with truncated linear systems that HHL can solve, potentially supporting gradient-descent dynamics when dissipation is strong.Training is described as highly dissipative early on, while the ODE approach may not suit later stages except near a local minimum; classical algorithms may then continue computation.Source: §3.3.1 · pp. 27–28
  • Late-training parameter sparsity may aid quantum data input through pruning and output extraction through sparse-state downloads or polynomial-scaling classical shadows, but full error correction remains necessary.QRAM is described as promising but still developmental; the section also identifies matrix multiplication for neural-network backpropagation as a potential target for quantum linear algebra or analog photonic parallelism [14].Source: §3.3.1 · p. 28

3.4. Quantum random access memory

  • Classical data must be loaded into a quantum computer before processing, a challenge termed the input problem.The supplied passage introduces the input and output problems but does not describe a QRAM mechanism.Source: §3.4 · p. 28
  • Large classical-data inputs can make loading a bottleneck for HHL, least-squares fitting, and quantum support vector machines; QRAM may help, but its costs can be prohibitive at scale.The section also notes that retrieving processed data can cause a substantial operational slowdown.Source: §3.4 · p. 29
  • A quantum data-lookup oracle uses a unitary query on quantum-state inputs and outputs to retrieve classical data, bridging classical information and quantum algorithms [54].Classically, an index i returns vector element x_i; in the quantum version, the address and query result are encoded in quantum states.Source: §3.4 · p. 29
  • QRAM uses log d qubits to summarize a vector and performs O(d) operations over O(log d) parallel steps.The section describes fanout QRAM, which flips router qubits according to address qubits, and bucket-brigade QRAM, which routes address qubits sequentially to establish a path.Source: §3.4 · pp. 29–30
  • Locality constrains QRAM query speed at scale, but some 2D or 3D designs were estimated to support up to 1020 qubits before reaching that constraint [129].The paper suggests this might suffice for machine-learning training programs, while noting that large-scale hardware evidence remains absent and promised exponential speedups remain uncertain.Source: §3.4 · pp. 30–31
  • Quantum state-preparation subroutines that encode classical information offer a way for some quantum machine-learning programs to avoid QRAM.The section notes that QRAM remains debated because it may save time while consuming substantial hardware.Source: §3.4 · pp. 30–31

4. Statistical learning theory

This section reviews quantum statistical learning approaches to extracting classical information from quantum states, including shadow-based methods for machine learning and Hamiltonian-property learning, and quantum-data methods for state analysis and dynamics reconstruction. It also covers reported scaling results and separations, potential near-term applications, and technical challenges.

4. Statistical learning theory

  • Classical shadows convert quantum outputs into classical data through random measurements, averaging, and inversion, and can support classical algorithms with only polynomial differences from fault-tolerant QML programs in average error.The review highlights their relevance when readout is required, including for quantum data and quantum simulators.Source: §4 · p. 31, §4.2 · pp. 37–38

4.1. Shadow tomography

  • State tomography needs approximately O(D2) copies for a D-dimensional mixed state, while shadow tomography targets expectation values for M observables and can run in poly(log D, log M) time.The state-tomography copy count remains exponentially large in qubit number; for 100 qubits, the passage estimates around 2^200 copies.Source: §4.1 · pp. 32–33

Theorem 4.1. Shadow Tomography Theorem

  • With n^O(1) copies of an n-qubit state or program, shadow tomography can characterize behavior on every polynomial-size circuit or estimate acceptance probabilities on every n-bit input.The theorem’s protocol estimates all measurement acceptance probabilities to additive error ±ε; its copy-complexity expression is incomplete in the supplied passage.Source: Theorem 4.1. Shadow Tomography Theorem · p. 33
  • The theorem’s gentle-measurement approach has a promise-gap limitation: without a gap, measurements near the acceptance threshold may damage the state, preventing the method from resolving outcomes with few copies.With a promise gap, the passage gives O(log M/ε2) copies for deciding each measurement’s side of the threshold.Source: Theorem 4.1. Shadow Tomography Theorem · p. 34

Theorem 4.2. Quantum OR Bound

  • The Quantum OR Bound decides a promised alternative with high probability using O(log M/ε2) copies, and combining it with postselection learning helps find informative measurements for shadow tomography.The passage notes that the result does not settle the optimal bound: a lower bound of O(log M/ε2) is known, while later work improved the log M dependence.Source: Theorem 4.2. Quantum OR Bound · p. 35

4.2. Classical shadow formalism and random measurements

  • For L low-weight Pauli observables, randomized measurements require an expected number of measurements logarithmic in L, with the sample bound also depending on observable norms and target accuracy.Randomly selecting Pauli bases and applying a union bound supports predicting many observables from the same measurements.Source: §4.2 · pp. 37–38

4.2.1. Machine learning with classical shadow

  • Classical shadows enable a classical kernel method to learn ground-state properties from Hamiltonian inputs and shadow measurements, then approximate ground states for Hamiltonians not observed during training.The described method uses a Fourier-type kernel to convolve the classical shadows collected during learning.Source: §4.2.1 · pp. 38–39
  • For small average-case prediction error, classical-shadow training data scales quasi-polynomially with the number of inputs, enabling predictions for Hamiltonians outside the training set [68].The approach uses classical shadows to connect quantum training data with classical predictions of ground-state properties and observable expectation values.Source: §4.2.1 · p. 39
  • [66] found no significant average-error sample-complexity separation between classical and QRAM-based quantum training, but showed exponential separation for worst-case prediction; [67] found quantum agents need exponentially fewer queries to characterize a state ρ.The [66] comparison uses quantum-device-generated data, classical shadows, and classical machine learning versus a hypothetical quantum protocol with coherent QRAM access.Source: §4.2.1 · p. 39

4.3. Quantum machine learning for quantum data and quantum simulators

  • Quantum principal component analysis can extract eigenvalues and corresponding eigenvectors from multiple copies of an N × N density matrix, contrasting with classical tomography’s O(N^2) measurements and classical PCA’s O(N^2) operations.The quantum method’s stated time-complexity expression is incomplete in the supplied passage.Source: §4.3 · p. 40
  • A trusted quantum simulator can be adjusted using approximate Bayesian inference to learn unknown system dynamics, significantly reducing measurements and offering exponential improvement [48].The simulator may be specialized for a class of systems or a general-purpose quantum computer.Source: §4.3 · p. 40
  • The universal quantum emulator reconstructs quantum dynamics, while quantum Boltzmann training reconstructs states in time logarithmic in Hilbert-space dimension, faster than classical tomography [96, 18].Source: §4.3 · p. 40
  • Quantum system characterization and quantum-PCA input-state methods face technical challenges but require no QRAM and may support near-term speedups in device characterization.Source: §4.3 · p. 40

5. Conclusion and discussion

The review sees promise for machine learning and data analysis in both NISQ devices and future fault-tolerant computers, amid rapid progress and ongoing challenges. It identifies near-term hardware and algorithm priorities and describes distinct post-NISQ eras for future QML work.

5. Conclusion and discussion

  • Both current NISQ devices and future fault-tolerant computers hold promise for machine learning and data analysis, while the field continues to face theoretical, practical, and experimental challenges.The review also notes notable progress in applications, experimental validations, and theoretical findings.Source: §5 · p. 40
  • NISQ-era priorities include larger, lower-error hardware capable of deeper circuits and algorithms designed for realistic device capabilities, alongside noise suppression, mitigation, and correction.Demonstrating practical quantum advantage is a goal; hardware and algorithm design must be combined for a successful demonstration.Source: §5 · p. 41
  • The review distinguishes a partial-error-corrected era with a few hundred physical qubits and some logical qubits from a fault-tolerant era with many error-corrected qubits.It describes potential roles for quantum steps in classical machine learning and for shadow methods in analyzing QML speedups.Source: §5 · p. 41

Related papers

Loading 2401.11351v2…