Quantum discriminant analysis for dimensionality reduction and classification
Quantum discriminant analysis for dimensionality reduction and classification
复制标题
DOI：
10.1088/1367-2630/18/7/073011
复制
发表时间：
2016-07-06
影响因子：
3.3
通讯作者：
Duan, Luming
中科院分区：
文献类型：
--
作者：
Cong, Iris;Duan, Luming
我们提出了量子算法，有效地执行判别分析的降维和分类指数大的输入数据集。与经典算法相比，量子算法在训练向量数M和特征空间维数N上都表现出指数级的加速比。我们推广了以前的量子算法求解线性方程组（2009年物理评论快报。103 150502）来有效地实现k个迹归一化的NXN埃尔米特半正定矩阵的埃尔米特链积，时间复杂度为O（log（N））。使用这个结果，我们执行线性以及非线性Fisher判别分析，用于M个向量上的降维，每个向量在N维特征空间中，时间为O（p polylog（MN）/是（3）的元素），其中是的元素表示公差误差，p是所需的主投影方向的数量。我们还提出了一个时间复杂度为O（log（MN）/是（3）的一个元素）的数据分类的量子判别分析算法。
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 (2009 Phys. Rev. Lett. 103 150502) to efficiently implement a Hermitian chain product of k trace-normalized N x 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 polylog(MN)/is an element of(3)), where is an element of 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)/is an element of(3)).