典型文献
Quantum algorithm for neighborhood preserving embedding
文献摘要:
Neighborhood preserving embedding(NPE)is an important linear dimensionality reduction technique that aims at preserving the local manifold structure.NPE contains three steps,i.e.,finding the nearest neighbors of each data point,constructing the weight matrix,and obtaining the transformation matrix.Liang et al.proposed a variational quantum al-gorithm(VQA)for NPE[Phys.Rev.A 101 032323(2020)].The algorithm consists of three quantum sub-algorithms,corresponding to the three steps of NPE,and was expected to have an exponential speedup on the dimensionality n.How-ever,the algorithm has two disadvantages:(i)It is not known how to efficiently obtain the input of the third sub-algorithm from the output of the second one.(ii)Its complexity cannot be rigorously analyzed because the third sub-algorithm in it is a VQA.In this paper,we propose a complete quantum algorithm for NPE,in which we redesign the three sub-algorithms and give a rigorous complexity analysis.It is shown that our algorithm can achieve a polynomial speedup on the number of data points m and an exponential speedup on the dimensionality n under certain conditions over the classical NPE algo-rithm,and achieve a significant speedup compared to Liang et al.'s algorithm even without considering the complexity of the VQA.
文献关键词:
中图分类号:
作者姓名:
Shi-Jie Pan;Lin-Chun Wan;Hai-Ling Liu;Yu-Sen Wu;Su-Juan Qin;Qiao-Yan Wen;Fei Gao
作者机构:
State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,Beijing 100876,China;State Key Laboratory of Cryptology,P.O.Box 5159,Beijing 100878,China
文献出处:
引用格式:
[1]Shi-Jie Pan;Lin-Chun Wan;Hai-Ling Liu;Yu-Sen Wu;Su-Juan Qin;Qiao-Yan Wen;Fei Gao-.Quantum algorithm for neighborhood preserving embedding)[J].中国物理B(英文版),2022(06):216-227
A类:
B类:
Quantum,neighborhood,preserving,embedding,Neighborhood,NPE,important,linear,dimensionality,reduction,technique,that,aims,local,manifold,structure,contains,three,steps,finding,nearest,neighbors,each,data,constructing,weight,matrix,obtaining,transformation,Liang,proposed,variational,quantum,VQA,Phys,Rev,consists,sub,algorithms,corresponding,was,expected,have,exponential,speedup,How,ever,has,two,disadvantages,known,efficiently,input,third,from,output,second,ii,Its,complexity,cannot,rigorously,analyzed,because,In,this,paper,complete,which,redesign,give,analysis,shown,our,achieve,polynomial,number,points,under,certain,conditions,over,classical,significant,compared,even,without,considering
AB值:
0.487913
相似文献
机标中图分类号,由域田数据科技根据网络公开资料自动分析生成,仅供学习研究参考。