Quantum data compression by principal component analysis
Quantum data compression by principal component analysis
复制标题
通过主成分分析进行量子数据压缩
DOI：
10.1007/s11128-019-2364-9
复制
发表时间：
2019
影响因子：
2.5
通讯作者：
Wang Jingbo
中科院分区：
文献类型：
--
作者：
Yu Chao Hua;Gao Fei;Lin Song;Wang Jingbo
数据压缩可以通过降低高维但近似低秩数据集的维数来实现，这实际上可以通过更少数量的参数的变化来描述。它通常作为克服维数灾难和提高效率的预处理步骤，因此在机器学习和数据挖掘中起着重要作用。在本文中，我们提出了一个量子算法，压缩指数大的高维，但近似低秩的数据集在量子并行，降维（DR）的基础上的主成分分析（PCA），最流行的经典DR算法。我们表明，该算法有一个运行时的数据集的大小和维数，这是指数快于经典的PCA算法，当原始数据集被投影到一个多对数低维空间。然后，可以进一步处理压缩的数据集，以实现其他感兴趣的任务，并使用更少的量子资源。作为例子，我们将该算法应用于两个重要的量子机器学习算法，量子支持向量机和量子线性回归预测的数据降维。这项工作表明，量子机器学习可以从维度灾难中释放出来，以解决具有实际意义的问题。
Data compression can be achieved by reducing the dimensionality of high-dimensional but approximately low-rank datasets, which may in fact be described by the variation of a much smaller number of parameters. It often serves as a preprocessing step to surmount the curse of dimensionality and to gain efficiency, and thus it plays an important role in machine learning and data mining. In this paper, we present a quantum algorithm that compresses an exponentially large high-dimensional but approximately low-rank dataset in quantum parallel, by dimensionality reduction (DR) based on principal component analysis (PCA), the most popular classical DR algorithm. We show that the proposed algorithm has a runtime polylogarithmic in the dataset’s size and dimensionality, which is exponentially faster than the classical PCA algorithm, when the original dataset is projected onto a polylogarithmically low-dimensional space. The compressed dataset can then be further processed to implement other tasks of interest, with significantly less quantum resources. As examples, we apply this algorithm to reduce data dimensionality for two important quantum machine learning algorithms, quantum support vector machine and quantum linear regression for prediction. This work demonstrates that quantum machine learning can be released from the curse of dimensionality to solve problems of practical importance.