Quantum dimensionality reduction by linear discriminant analysis

The dimensionality reduction is generally used as the data preprocessing stage of many machine learning tasks and has become an essential branch of information processing. Due to the exponential growth of data, how constructing reasonable and efficient dimensionality reduction algorithms has been an open challenge recently. In this paper, we propose a quantum linear discriminant analysis algorithm for dimensionality reduction. In the proposed algorithm, the idea of quantum solving linear equations is utilized to obtain the shadow principal components and an intermediate state. After that, the special unitary operations are designed to assist in completing the dimensionality reduction. The theoretical analysis shows the proposed algorithm has exponential acceleration on the number of vectors and a quadratic speedup on the dimensionality of the original data space. Since this algorithm solves the restriction that the between-class scatter matrix must be reversible, it makes the algorithm more applicable. Moreover, instead of getting the quantum state in the projection direction, the algorithm obtains the corresponding quantum state of dimensionality reduction data so that the outputs can be directly applied to other quantum machine learning algorithms. To illustrate it, a simple example, quantum K-nearest Neighbor classification, is provided.