A rigorous and robust quantum speed-up in supervised machine learning

Yunchao Liu; Srinivasan Arunachalam; Kristan Temme

Source-linked AI summary

A rigorous and robust quantum speed-up in supervised machine learning

Yunchao Liu, Srinivasan Arunachalam, Kristan Temme

arXiv:2010.02174v2Oct 5, 2020quant-phcs.LG

TL;DR

The paper studies supervised learning where classical polynomial-time learners are limited by the assumed hardness of discrete logarithms. It uses quantum kernel estimation with an SVM and proves high-accuracy learning with robustness to measurement noise.

Problem
Assuming the hardness of DLP, no classical polynomial-time algorithm can learn the constructed concept class, while the learning problem remains efficiently learnable in BQP.
Method
The approach combines support vector machines with quantum kernel estimation and analyzes classifiers whose kernel estimates have additive measurement error.
Results
The SVM-QKE algorithm achieves test accuracy at least 0.99 in polynomial time with probability at least 2/3 over training-sample and noise randomness.
Takeaways & Limitations
The constructed concept class is efficiently learnable in BQP but cannot be learned efficiently classically under the assumed hardness of DLP.

Abstract

from arXiv · show

Over the past few years several quantum machine learning algorithms were proposed that promise quantum speed-ups over their classical counterparts. Most of these learning algorithms either assume quantum access to data -- making it unclear if quantum speed-ups still exist without making these strong assumptions, or are heuristic in nature with no provable advantage over classical algorithms. In this paper, we establish a rigorous quantum speed-up for supervised classification using a general-purpose quantum learning algorithm that only requires classical access to data. Our quantum classifier is a conventional support vector machine that uses a fault-tolerant quantum computer to estimate a kernel function. Data samples are mapped to a quantum feature space and the kernel entries can be estimated as the transition amplitude of a quantum circuit. We construct a family of datasets and show that no classical learner can classify the data inverse-polynomially better than random guessing, assuming the widely-believed hardness of the discrete logarithm problem. Meanwhile, the quantum classifier achieves high accuracy and is robust against additive errors in the kernel entries that arise from finite sampling statistics.

Appendix A: Supervised learning and the discrete log problem

The appendix sets supervised learning in the standard concept-class framework and defines efficient learnability through high test accuracy from polynomially many examples. It then introduces discrete logarithm problems and reductions showing that decision variants remain connected to solving DLP.

A concept class consists of binary-labeling functions over a data space, with an unknown target concept generating uniformly sampled labeled examples.
Efficient learning requires a polynomial-time classifier achieving 99% test accuracy with probability at least 2/3 from polynomially many samples.
DLP asks for x such that g^x ≡ y (mod p), given a prime p, primitive element g, and y in Z∗_p.
A polynomial-time algorithm deciding whether log_g y lies in the lower half of the exponent range on a 1/2 + 1/poly(n) fraction of inputs would yield an efficient DLP algorithm.
The promise problem DLP_c restricts log_g y to separated intervals, and an efficient solver for it would also imply an efficient solver for DLP.

Appendix B: A concept class reducible to discrete log

The paper constructs a concept class whose learning is tied to discrete logarithms: quantum computation can learn it, while classical learning would imply an efficient DLP algorithm. The construction also yields a verifiable challenge separating BQP from efficient classical provers under DLP hardness.

The concept class C is constructed so that learning it is as hard as solving a decision version of the discrete logarithm problem.
Quantum computation learns C efficiently because taking discrete logarithms maps labeled samples into two clusters that can be separated by a simple one-dimensional classifier.
The concept class has efficiently classically generable training samples, despite the resulting learning task being classically hard.
Assuming DLP hardness, no polynomial-time classical learner can achieve an inverse-polynomial advantage over random guessing on this concept class.
A BQP prover passes the classification challenge, whereas no polynomial-time classical prover passes it assuming the classical hardness of DLP.

1. Support vector machines

This section presents support vector machines as polynomial-time maximum-margin classifiers and motivates soft margins when data are not linearly separable. It also formulates the associated convex quadratic optimization and its dual.

An SVM maps polynomial-size labeled training data to a linear classifier by finding parameters defining a separating hyperplane.
SVMs maximize the normalized margin, the minimum distance from training points to the separating hyperplane, supporting generalization analysis.
Soft-margin SVMs introduce slack variables and a penalty term to handle outliers and non-linearly separable training sets.
For p = 2, the soft-margin formulation becomes a convex quadratic program with a Wolfe dual derived by Lagrangian duality.
The primal and dual solutions are linked by KKT conditions, including proportionality between dual multipliers and slack variables when λ is constant.

2. Non-linear classification

Non-linear SVM classification maps data into a higher-dimensional feature space and accesses training data through a kernel matrix. This permits large feature spaces when kernel evaluation is efficient.

Non-linear classification maps d-dimensional data into an n-dimensional feature space with n much greater than d using a preselected feature map.
The SVM dual accesses training data through the kernel matrix of pairwise feature-map inner products.
Exponentially large or infinite-dimensional feature spaces remain usable when the corresponding kernel is computable in polynomial time.
Adding a constant coordinate absorbs the bias parameter into the feature vector and changes the kernel accordingly.
After training, prediction requires evaluating the kernel on a new example and combining it with the learned dual coefficients.

3. Quantum kernel estimation

Quantum kernel estimation maps classical data to quantum states, estimates pairwise kernel values through circuit measurements, and supplies the resulting kernel to a conventional SVM. The approach combines expressive quantum feature maps with finite-sampling noise, motivating a formal noise-robustness analysis.

Quantum feature maps encode classical data vectors as quantum states used to construct the kernel.The kernel is the Hilbert-Schmidt inner product between the corresponding density matrices.
The kernel function is estimated by running U†(x_i)U(x_j) on |0^n⟩ and measuring the probability of the |0^n⟩ outcome.
During training, measured pairwise kernel estimates are assembled into K = 1/2(K_0 + 1_m×m) and passed to the SVM dual program.
The testing phase uses the trained coefficients and quantum kernel estimates to return a binary prediction y ∈ {−1, 1}.
Finite sampling makes each quantum kernel estimate noisy, while quantum feature maps may be more expressive than classical feature maps.The paper therefore identifies noise robustness as important for a provable quantum advantage with QKE.

1. Quantum feature map

The paper constructs quantum feature states from discrete-logarithm-based classical circuits and uses their interval structure to create a classically hard kernel. Approximating the kernel to additive error 0.01 would yield an efficient algorithm for the discrete logarithm problem.

The feature-state circuit family is injective, computable with O(n) multiplications, and preparable on a quantum computer using Õ(n^3) gates.
The feature map sends y ∈ Z*_p and k ∈ {1, 2, . . . , n − 1} to an n-qubit feature state.Here n = ⌈log_2 p⌉ is the number of bits needed to represent p.
After taking discrete logarithms, each feature state becomes a superposition over an interval, so kernel inner products equal intersections of corresponding intervals.
Approximating K_0(y, y′) within 0.01 additive error enables a polynomial-time algorithm for DLP(p, g).
The reduction distinguishes cases where K_0(y, y′) = 0 from cases where K_0(y, y′) ≥ 1/16, thereby deciding a promise version of the discrete logarithm problem.

2. Mapping to high dimensional Euclidean space

The quantum feature-space learning problem is recast as noisy halfspace learning in a 4^n+1-dimensional Euclidean space. The mapped data have a separating hyperplane with a large margin, while kernel estimates introduce independent variance-bounded noise.

Each concept has a separating state whose squared overlaps are Δ for most positive examples and 0 for most negative examples.Both statements hold for a 1 − Δ fraction of the corresponding labeled examples.
The large-margin property gives the SVM a good separating hyperplane despite a small outlier probability Δ = 1/poly(n).
Quantum states are represented by Pauli vectors, making the Hilbert-Schmidt inner product equivalent to a Euclidean inner product in 4^n dimensions.
The mapped classification problem has unit-length data, a separating hyperplane, bounded distance to that hyperplane, and a noisy kernel.
The noisy kernel has independent additive errors e_ij with Var[e_ij] ≤ 1/R, where R is the number of measurement shots.
After removing the bias parameter through an augmented feature transform, the problem is formulated in R^(4^n+1) with a margin of O(Δ).

3. Generalization of the noisy classifier

The analysis combines generalization bounds for soft-margin classifiers with perturbation stability of the dual SVM to prove that noisy kernel estimates preserve classification accuracy. This yields polynomial-time learning with high accuracy despite measurement noise.

Noise robustness: The dual SVM solution is stable under small additive perturbations of the kernel matrix.This follows from strong convexity and perturbation analysis of positive definite quadratic programs.
Noise robustness: Lemma 19 establishes noise robustness when each quantum kernel circuit uses R = O(m4) measurement shots.The noisy classifier remains close to the noiseless classifier under the stated sampling procedure.
Generalization: Generalization analysis requires bounding the noisy classifier through both soft-margin generalization and closeness to the noiseless classifier.The noiseless classifier has a standard generalization bound, while noise robustness transfers this behavior to the noisy classifier.
Generalization: A standard margin bound alone is insufficient because closeness of h′(x) to h(x) does not ensure agreement between sign(h′(x)) and sign(h(x)).The noiseless score may have the correct sign while remaining close to zero.
Generalization: A stronger bound ensures that the noiseless score is bounded away from zero, allowing additive perturbations to preserve the classification sign.The proof combines this stronger margin-based generalization result with noise robustness.
Main guarantee: 0.99 test accuracy is achieved in polynomial time with probability at least 2/3 over training samples and noise.Polynomially many training samples therefore suffice for learning the concept class with high accuracy.

Appendix E: Generalization bound for soft margin SVM

The appendix derives a soft-margin SVM generalization bound by converting the problem to a hard-margin problem in an enlarged space and applying fat-shattering dimension arguments. The resulting bound controls test error using the transformed classifier’s norm and margin.

Hard-margin transformation: The soft-margin SVM is transformed into a hard-margin problem by mapping data and slack variables into a larger space.The enlarged representation incorporates the original hyperplane and its slack variables.
Hard-margin transformation: The transformed norm satisfies ∥˜w∥2 = ∥w∥2 2 + ∥ξ∥2 2, combining classifier norm and slack-variable magnitude.This relation connects soft-margin training loss to the complexity of the enlarged-space classifier.
Fat-shattering analysis: Hard-margin generalization is controlled through the fat-shattering dimension of the associated real-valued function class.The appendix introduces γ-shattering and uses its dimension to obtain generalization bounds.
Generalization bound: The resulting bound controls the probability that the classifier’s score falls sufficiently far onto the wrong side of the decision boundary.The proof relates such score deviations to disagreement with the target labeling rule.
Fat-shattering analysis: The normalized transformed score has a training margin γ0, and the analysis compares it with a reduced margin γ = 0.9γ0.Training examples satisfy a positive transformed margin, which supports the subsequent generalization argument.