PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Discriminant Analysis for Dimensionality Reduction and Classification

Iris Cong, Luming Duan

arXiv:1510.00113v2quant-ph

TL;DR

Classical discriminant-analysis methods can scale poorly with the number of training vectors and feature dimensions, while prior quantum work had not accelerated LDA or its classifier. The paper develops quantum discriminant-analysis algorithms for dimensionality reduction and classification, with runtimes polylogarithmic or logarithmic in those data sizes. The authors also note that their error dependence is worse than that of classical algorithms.

  • Problem

    Classical LDA and discriminant-analysis classification can scale poorly with training-set size and feature dimension, and prior quantum algorithms had not addressed these tasks.

    Source: §I · p. 2

  • Method

    The paper uses a generalized quantum matrix-chain procedure to implement LDA dimensionality reduction and QDA classification.

    Source: §I · p. 2, Finding the principal eigenvectors · p. 5

  • Results

    The quantum LDA algorithm is polylogarithmic in M and N regardless of training-vector sparseness, and the quantum classifier is logarithmic in both.

    Source: §I · p. 2

  • Takeaways & Limitations

    The authors report that discriminant-analysis classifiers can offer model stability and simpler generalization to multiclass classification than SVMs.

    Source: §V · p. 9

    The authors acknowledge that the method’s error dependence is polynomial in 1/epsilon, rather than logarithmic as in classical algorithms.

    Source: §V · p. 9

Abstract

from arXiv · show

We present quantum algorithms to efficiently perform discriminant analysis for dimensionality reduction and classification over an exponentially large input data set. Compared with the best-known classical algorithms, the quantum algorithms show an exponential speedup in both the number of training vectors $M$ and the feature space dimension $N$. We generalize the previous quantum algorithm for solving systems of linear equations [Phys. Rev. Lett. 103, 150502 (2009)] to efficiently implement a Hermitian chain product of $k$ trace-normalized $N \times N$ Hermitian positive-semidefinite matrices with time complexity of $O(\log (N))$. Using this result, we perform linear as well as nonlinear Fisher discriminant analysis for dimensionality reduction over $M$ vectors, each in an $N$-dimensional feature space, in time $O(p \text{polylog} (MN)/\epsilon ^{3})$, where $\epsilon $ denotes the tolerance error, and $p$ is the number of principal projection directions desired. We also present a quantum discriminant analysis algorithm for data classification with time complexity $O(\log (MN)/\epsilon^{3})$.

I. INTRODUCTION

The paper motivates discriminant analysis for high-dimensional data and presents quantum algorithms for dimensionality reduction and classification with runtimes polylogarithmic in the data count and feature dimension. Its LDA approach chooses projections by balancing between-class and within-class variance.

Dimensionality Reduction

  • LDA selects projection directions that maximize between-class variance while minimizing within-class variance, unlike PCA’s focus on overall variance.When overall variance aligns with within-class variance and is orthogonal to between-class variance, PCA can project different classes to overlapping data.Source: §I · p. 1, Dimensionality Reduction · p. 2

I. INTRODUCTION

  • Quantum LDA dimensionality reduction is polylogarithmic in M and N, regardless of training-vector sparseness.The introduction contrasts this with classical LDA runtime O(Ms), where s is maximum feature-vector sparseness.Source: §I · pp. 1–2
  • Quantum discriminant-analysis classification is logarithmic in M and N, where classical algorithms require polynomial time in both.The introduction contrasts the approach with a prior quantum SVM classifier, noting no earlier quantum discriminant-analysis classifier.Source: §I · p. 2

Dimensionality Reduction

  • The LDA objective assumes approximately multivariate Gaussian classes with similar covariances and maximizes the ratio of between-class to within-class projected variance.For a p-dimensional projection subspace, the basis vectors correspond to the p largest eigenvalues of S_W^-1 S_B.Source: Dimensionality Reduction · pp. 2–3

Classification

The classification section describes discriminant functions based on class means, covariances, and prior probabilities, then outlines quantum access assumptions for constructing the scatter operators. With equal class covariances, the general QDA case reduces to LDA classification.

Classification

  • A class’s discriminant function uses its covariance matrix, mean, and prior probability; vectors are assigned to the class with the largest function value.The prior can be approximated by the fraction of training vectors in that class, M_c/M.Source: Classification · p. 3
  • QDA handles class-specific covariance matrices, while approximately equal class covariances yield the LDA special case.The paper presents a quantum algorithm for the general QDA case that also applies to LDA classification.Source: Classification · p. 3

Assumptions and Initialization

  • The quantum input assumptions include QRAM access to normalized training-vector differences from class means and quantum representations of class centroids.The text notes that these oracles may be realizable when vector components are stored as floating-point numbers in QRAM and sub-norms can be estimated efficiently.Source: Assumptions and Initialization · p. 4
  • Given the assumed oracles, the operators S_B and S_W can be constructed in O(log(MN)) time.The paper says the oracles construct density matrices proportional to the between-class and within-class scatter matrices.Source: Assumptions and Initialization · p. 4

LDA Approach

The LDA eigenvector task is recast as a Hermitian eigenvalue problem so quantum phase estimation can be applied. This requires constructing a density matrix involving the scatter matrices.

LDA Approach

  • The target is the eigenvector problem for S_W^-1 S_B, which would be simpler if that operator were Hermitian positive semidefinite.The paper reduces it to an eigenvalue problem for a Hermitian density matrix using a change of variables involving S_B.Source: LDA Approach · p. 5
  • The change of variables converts the generalized LDA eigenvector task into an eigenvalue problem suitable for the quantum approach.The paper states that S_B is Hermitian positive semidefinite and defines the transformed vector in terms of S_B.Source: LDA Approach · p. 5
  • Quantum phase estimation on the transformed eigenvalue problem requires constructing the density matrix S_B^1/2.The paper introduces a more general theorem for constructing this matrix.Source: LDA Approach · p. 5

Implementing the Hermitian chain product

The paper gives a quantum implementation for Hermitian chain products and uses it to obtain the principal projection directions for LDA. Those directions support dimensionality reduction along high between-class and low within-class variance.

Implementing the Hermitian chain product

  • The Hermitian operator formed from a chain of normalized positive-semidefinite matrices can be implemented with the stated complexity bound.The theorem assumes matrices constructible in O(log(N)) time and functions with convergent Taylor series.Source: Implementing the Hermitian chain product · p. 5
  • The chain-product result provides an exponential speedup over classical multiplication of non-sparse N × N matrices, whose optimal known time is O(N^2.3737).Source: Implementing the Hermitian chain product · p. 5

Finding the principal eigenvectors

  • LDA applies the chain algorithm to S_W^-1/2 S_B^1/2, restricting phase estimation to eigenvalues in [1/κ_eff, 1].The passage typically takes κ_eff = O(1/ε).Source: Finding the principal eigenvectors · pp. 5–6
  • Sampling yields the p principal eigenvectors when their eigenvalues are polynomially small; transforming them gives directions for projection onto maximal between-class and minimal within-class variance.The resulting directions can be used for dimensionality reduction or subsequent classification.Source: Finding the principal eigenvectors · p. 6

Algorithmic Complexity for Dimensionality Reduction

The quantum LDA algorithm has polylogarithmic complexity in the training-set size and feature dimension, regardless of training-vector sparseness. Its complexity analysis also specifies an effective condition number and an eigenvector-finding cost.

Nonlinear/Kernel Fisher Discriminant Analysis

Kernel FDA maps input vectors nonlinearly into a higher-dimensional feature space, where a linear discriminant becomes nonlinear in the original space. The quantum classifier evaluates class discriminants and selects the class with the maximum value.

Nonlinear/Kernel Fisher Discriminant Analysis

  • Kernel FDA maps vectors into a higher-dimensional feature space, making its linear discriminant nonlinear in the original space.When that space is too large, classical matrix operations can become computationally infeasible.Source: Nonlinear/Kernel Fisher Discriminant… · p. 7
  • Quantum LDA can perform analysis directly in a feature space whose dimension is polynomial in the original input dimension, allowing a wider range of mappings φ.The algorithm's performance is affected only by a constant factor under that dimension condition.Source: Nonlinear/Kernel Fisher Discriminant… · p. 7

Algorithm

  • The QDA classifier assumes quantum access to class means and training vectors, as well as the number of training vectors in each class.Source: Algorithm · p. 7
  • The classifier evaluates inner products for each class, adds the class prior, and assigns the input to the class with the maximum discriminant.The described quantum algorithm is for QDA and can also be applied to LDA classification.Source: Algorithm · p. 8

Algorithmic Complexity for Classification

The quantum QDA classifier has logarithmic complexity in the number of training vectors and feature dimension, regardless of training-vector sparseness. Its runtime analysis includes classwise inversion, inner-product evaluation, and selection of the maximum discriminant.

V. DISCUSSION

The paper presents quantum algorithms for LDA and QDA classification, with exponential speedup in the data and feature dimensions. It notes that their error dependence is worse than classical algorithms, while discriminant classifiers offer stability and multiclass advantages over SVMs.

V. DISCUSSION

  • Quantum LDA has polynomial rather than logarithmic dependence on 1/ε, which the authors consider acceptable for dimensionality reduction.They argue that users seeking extreme precision are unlikely to want significant dimensionality reduction.Source: §V · p. 9
  • The quantum algorithms provide exponential speedup for LDA dimensionality reduction and LDA and QDA classification.The authors argue that speedup in the number of training vectors and feature dimension is more significant than the poorer error dependence for dimensionality reduction.Source: §V · p. 9
  • Discriminant classifiers typically match SVM accuracy, have better model stability against training-data errors, and generalize more simply to multiclass classification.The authors contrast this with SVMs being more suited to binary classification.Source: §V · p. 9

APPENDIX A: PROOF OF THEOREM 1

The proof adapts HHL's phase-estimation procedure to construct an operator from an identity-proportional input rather than invert a matrix on a specific vector. It applies a controlled rotation and postselection, then repeats the construction across the matrix chain.

APPENDIX A: PROOF OF THEOREM 1

  • The proof adapts HHL by starting from an identity-proportional density operator instead of a specific vector input, to construct an operator for the matrix-chain expression.It also replaces the pure initial state in HHL with its density-operator form.Source: Appendix A · p. 9
  • Phase estimation on ρ0 uses time O(κ1/ε), where κ1 is A1’s condition number, and requires O(κ1^2/ε^3) copies of A1.The stated copy count is for phase estimation to error ε.Source: Appendix A · p. 9
  • A controlled rotation conditioned on the eigenvalue register implements f1, yielding a density operator proportional to f1(A1)I(f1(A1))†.The rotation is assumed efficiently implementable when f1 has a convergent Taylor series.Source: Appendix A · pp. 9–10
  • Measuring the ancilla in |1⟩⟨1| postselects the desired state, with success probability determined by the chosen normalization constant C.The appendix states that the resulting operator is proportional to ρ1 = f1(A1)I(f1(A1))†.Source: Appendix A · p. 10
  • Repeating the procedure with Aj and fj on ρj−1 constructs the Hermitian operator for the full chain, with each step requiring O(κj^2/ε^3) copies of Aj.Amplitude amplification on A1 only can reduce the complexity slightly; for density matrices in quantum RAM, X = O(log(N)).Source: Appendix A · p. 10

APPENDIX B: PERFORMING THE CONTROLLED ROTATION OF (29)

The appendix implements the controlled rotation by approximating its angle through Taylor expansions. It first computes f(λ), then applies a Maclaurin approximation to arcsin(Cf(λ)) and uses the resulting angle to rotate the ancilla.

APPENDIX B: PERFORMING THE CONTROLLED ROTATION OF (29)

  • For arbitrary f with a convergent Taylor series, the controlled rotation uses angle θ(λ) = sin−1(Cf(λ)).The appendix presents this as a method for rotations that HHL did not decompose into controlled gates, even for f(x) = 1/x.Source: Appendix B · p. 10
  • The procedure approximates θ(λ) by first constructing a register for f(λ), then approximating sin−1(Cf(λ)) with its Maclaurin series.The choice of C places Cf(λ) within the arcsine series’ radius of convergence.Source: Appendix B · pp. 10–11
  • The binary expansion of θ(λ) specifies a sequence of ancilla rotations controlled by its coefficient qubits, implementing the desired rotation efficiently.Each two-qubit controlled-U operation can be implemented with two controlled-NOT gates and single-qubit unitaries.Source: Appendix B · p. 11
  • The procedure prepares an auxiliary register for λ−x0 and three working registers: the first holds its current power, the second holds that value times f(k)(x0)/k!, and the third is the right-hand-side running total.The first and second working registers are initialized to 1, and the third to 0.Source: Appendix B · p. 11
  • After computing f(λ), the procedure repeats the register computation for Cf(λ) with sin−1 to obtain θ(λ).The stated steps yield the value of f(λ) in the third working register before this second approximation.Source: Appendix B · p. 11
Loading 1510.00113v2…