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