基于最大方差展开的量子非线性降维  

Quantum nonlinear dimensionality reduction based on maximum variance unfolding

作　　者：张新 郭躬德[2] 吁超华 林崧[4] ZHANG Xin;GUO GongDe;YU ChaoHua;LIN Song(College of Mathematics and Statistics,Fujian Normal University,Fuzhou 350117,China;Digital Fujian Internet-of-Things Laboratory of Environmental Monitoring,Fujian Normal University,Fuzhou 350117,China;School of Information Management,Jiangxi University of Finance and Economics,Nanchang 330032,China;College of Computer and Cyber Security,Fujian Normal University,Fuzhou 350117,China)

机构地区：[1]福建师范大学数学与统计学院,福州350117 [2]福建师范大学数字福建环境监测物联网实验室,福州350117 [3]江西财经大学信息管理学院,南昌330032 [4]福建师范大学计算机与网络空间安全学院,福州350117

出　　处：《中国科学：物理学、力学、天文学》2024年第12期52-62,共11页Scientia Sinica Physica,Mechanica & Astronomica

基　　金：国家自然科学基金(编号:62171131,61976053,62006105);中国博士后科学基金(编号:2023M731429);福建省自然科学基金(编号:2022J01186,2023J01533);江西省自然科学基金(编号:20202BABL212004)资助项目。

摘　　要：最大方差展开算法是在流形局部等距的基础上提出的一种非线性降维算法.然而,在处理大规模数据集时它需要大量的计算成本.为此,本文提出了一种高效的量子最大方差展开算法.首先,提出了一个量子矩阵平方根算法,它可以指数加速地实现矩阵开平方,从而有效地获得拉普拉斯矩阵的密度算子.然后,在此基础上给出了完整的量子降维算法,利用哈密顿模拟和相位估计将原始高维数据映射到低维数据空间.最后,时间复杂度分析表明,本文所提量子降维算法相较于经典算法在维度上实现了指数加速,在样本数量上实现了多项式加速.Maximum variance unfolding is a nonlinear dimensionality reduction algorithm based on the local equidistance of manifolds.However,it is quite computationally expensive,especially when dealing with large-scale datasets.Therefore,an efficient quantum maximum variance unfolding algorithm is proposed herein.First,we propose a quantum matrix square root algorithm with exponential speedup,which can be used to obtain the square root of the involved matrix.As a result,we can efficiently obtain the density operator of the Laplacian matrix.Then,a complete quantum dimensionality reduction algorithm is proposed to map the original high-dimensional data onto a low-dimensional data space using Hamiltonian simulation and phase estimation.Finally,our research reveals that compared with its classical counterpart,the proposed quantum dimensionality reduction algorithm achieves an exponential speedup in terms of dimension and a polynomial speedup in terms of number of samples.

关 键 词：量子机器学习 量子降维算法 最大方差展开 量子哈密顿模拟 拉普拉斯矩阵 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程] O413[自动化与计算机技术—控制科学与工程]