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})$.

提出了一种利用量子算法实现降维和分类的方法，并对其性能进行了对比，结果表明其在训练数据向量队列和特征空间维数方面都比已知的经典算法具有指数级的加速度；同时，还给出了一种利用海森矩阵链积的量子算法，实现了线性及非线性费舍尔判别分析。