Please wait a minute...
Chin. Phys. B, 2022, Vol. 31(6): 060304    DOI: 10.1088/1674-1056/ac523a
GENERAL Prev   Next  

Quantum algorithm for neighborhood preserving embedding

Shi-Jie Pan(潘世杰)1,2, Lin-Chun Wan(万林春)1, Hai-Ling Liu(刘海玲)1, Yu-Sen Wu(吴宇森)1, Su-Juan Qin(秦素娟)1, Qiao-Yan Wen(温巧燕)1, and Fei Gao(高飞)1,†
1 State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China;
2 State Key Laboratory of Cryptology, P. O. Box 5159, Beijing 100878, China
Abstract  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 algorithm (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. However, 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 algorithm, and achieve a significant speedup compared to Liang et al.'s algorithm even without considering the complexity of the VQA.
Keywords:  quantum algorithm      quantum machine learning      amplitude amplification  
Received:  15 November 2021      Revised:  29 January 2022      Accepted manuscript online:  07 February 2022
PACS:  03.67.Ac (Quantum algorithms, protocols, and simulations)  
  03.67.Lx (Quantum computation architectures and implementations)  
Fund: Project supported by the Fundamental Research Funds for the Central Universities (Grant No. 2019XD-A01) and the National Natural Science Foundation of China (Grant Nos. 61972048 and 61976024).
Corresponding Authors:  Fei Gao     E-mail:

Cite this article: 

Shi-Jie Pan(潘世杰), Lin-Chun Wan(万林春), Hai-Ling Liu(刘海玲), Yu-Sen Wu(吴宇森), Su-Juan Qin(秦素娟), Qiao-Yan Wen(温巧燕), and Fei Gao(高飞) Quantum algorithm for neighborhood preserving embedding 2022 Chin. Phys. B 31 060304

[1] Shor P W 1994 Proceedings of the 35th Annual Symposium on Foundations of Computer Science, November 20-22, 1994, Washington, USA, p. 124
[2] Grover L K 1996 Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, May 22-24, 1996, Philadelphia, USA, p. 212
[3] Harrow A W, Hassidim A and Lloyd S 2009 Phys. Rev. Lett. 103 150502
[4] Wan L C, Yu C H, Pan S J, Gao F, Wen Q Y and Qin S J 2018 Phys. Rev. A 97 062322
[5] Zhao L M, Zhao Z K, Rebentrost P and Fitzsimons J 2021 Quantum Machine Intelligence 3 21
[6] Lloyd S, Mohseni M and Rebentrost P 2013 arXiv: 1307.0411v2 [quant-ph]
[7] Rebentrost P, Mohseni M and Lloyd S 2014 Phys. Rev. Lett. 113 130503
[8] Cong I and Duan L 2016 New J. Phys. 18 073011
[9] Ye Z K, Li L Z, Situ H Z and Wang Y Y 2020 Sci. China Inform. Sci. 63 189501
[10] Wiebe N, Braun D and Lloyd S 2012 Phys. Rev. Lett. 109 050505
[11] Schuld M, Sinayskiy I and Petruccione F 2016 Phys. Rev. A 94 022342
[12] Wang G 2017 Phys. Rev. A 96 012335
[13] Yu C H, Gao F and Wen Q Y 2021 IEEE T. Knowl. Data En. 33 858
[14] Yu C H, Gao F, Liu C, Huynh D, Reynolds M and Wang J 2019 Phys. Rev. A 99 022301
[15] Yu C H, Gao F, Wang Q L and Wen Q Y 2016 Phys. Rev. A 94 042311
[16] Liu N and Rebentrost P 2018 Phys. Rev. A 97 042315
[17] Bishop C M 2006 Pattern Recognition and Machine Learning (Information Science and Statistics), (1st edn.), (New York: Springer) pp. 24-28
[18] Hotelling H 1936 Biometrika 28 321
[19] Fisher R A 1936 Ann. Eugenics 7 179
[20] He X, Cai D, Yan S and Zhang H J 2005 Tenth IEEE International Conference on Computer Vision, Octobor 17-21, 2005, Beijing, China, p. 1208
[21] Roweis S T and Saul L K 2000 Science 290 2323
[22] Lloyd S, Mohseni M and Rebentrost P 2014 Nat. Phys. 10 631
[23] Yu C H, Gao F, Lin S and Wang J 2019 Quantum Inf. Process. 18 249
[24] Duan B, Yuan J, Xu J and Li D 2019 Phys. Rev. A 99 032311
[25] Pan S J, Wan L C, Liu H L, Wang Q L, Qin S J, Wen Q Y and Gao F 2020 Phys. Rev. A 102 052402
[26] Li Y, Zhou R G, Xu R, Hu W and Fan P 2020 Quantum Sci. Technol. 6 014001
[27] Meng F X, Yu X T, Xiang R Q and Zhang Z C 2019 IEEE Access 7 4825
[28] Pan S J, Gao F, Wan L C, Qin S J and Wen Q Y 2021 Journal of Computer Research and Development 58 1835 (in Chinese)
[29] Liang J M, Shen S Q, Li M and Li L 2020 Phys. Rev. A 101 032323
[30] Cerezo M, Arrasmith A, Babbush R, Benjamin S C, Endo S, Fujii K, McClean J R, Mitarai K, Yuan X, Cincio L and Coles P J 2021 Nat. Rev. Phys. 3 625
[31] Liu H L, Wu Y S, Wan L C, Pan S J, Qin S J, Gao F and Wen Q Y 2021 Phys. Rev. A 104 022418
[32] Kerenidis I and Prakash A 2017 8th Innovations in Theoretical Computer Science Conference, January 9-11, 2017, Berkeley, USA, p. 49
[33] Wossnig L, Zhao Z and Prakash A 2018 Phys. Rev. Lett. 120 050502
[34] Chen J and Ma Z 2011 International Journal of Pattern Recognition and Artificial Intelligence 25 985
[35] Cai D, He X and Han J 2007 2007 IEEE 11th International Conference on Computer Vision, October 14-21, 2007, Rio de Janeiro, Brazil, p. 1
[36] Cai D, He X and Han J 2007 Proceedings of the 15th ACM International Conference on Multimedia, September 24-29, Augsburg, Germany, p. 403
[37] Pedregosa F, Varoquaux G, Gramfort A, Michel V, Thirion B, Grisel O, Blondel M, Prettenhofer P, Weiss R, Dubourg V, Vanderplas J, Passos A, Cournapeau D, Brucher M, Perrot M and Duchesnay E 2011 J. Mach. Learn. Res. 12 2825
[38] Brassard G, Hoyer P, Mosca M and Tapp A 2002 Contemporary Mathematics 305 53
[39] Kerenidis I, Landman J, Luongo A and Prakash A 2019 33rd Conference on Neural Information Processing Systems, December, 8-14, 2019, Vancouver, Canada, p. 4134
[40] Vedral V, Barenco A and Ekert A 1996 Phys. Rev. A 54 147
[41] Zhou S, Loke T, Izaac J and Wang J 2017 Quantum Inf. Process. 16 82
[42] Cao Y, Papageorgiou A, Petras I, Traub J and Kais S 2013 New J. Phys. 15 013021
[43] Erdös P 1961 Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei 6 215
[44] Kerenidis I and Landman J 2021 Phys. Rev. A 103 042415
[45] Kerenidis I and Prakash A 2020 ACM Transactions on Quantum Computing 1 5:1
[46] Yin Q, Xiang G Y, Li C F and Guo G C 2018 Chin. Phys. Lett. 35 070302
[47] Gilyén A, Su Y, Low G H and Wiebe N 2019 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, June 23-26, Arizona, USA, p. 193
[48] Low G H and Chuang I L 2019 Quantum 3 163
[49] Chakraborty S, Gilyen A and Jeffery S 2019 46$th International Col loquium on Automata, Languages and Programming, July 9-12, 2019, Patras, Greece, p. 33:1
[50] Ghojogh B, Ghodsi A, Karray F and Crowley M 2020 arXiv: 2011.10925v1 [stat.ML]
[51] Durr C and Hoyer P 1996 arXiv: 9607014v2 [quant-ph]
[52] Li S, Liang J, Shen S and Li M 2021 Commun. Theor. Phys. 73 105102
[53] Tang E 2019 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, June 23-26, Arizona, USA, p. 217
[54] Chia N H, Gilyén A, Li T Y, Lin H H, Tang E and Wang C H 2020 Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, June 22-26, New York, USA, p. 387
[55] Chen Y L and De Wolf R 2021 arXiv: 2110.13086 [quant-ph]
[56] Yoder T J, Low G H and Chuang I L 2014 Phys. Rev. Lett. 113 210501
[57] Rebentrost P, Steffens A, Marvian I and Lloyd S 2018 Phys. Rev. A 97 012327
[1] Variational quantum simulation of thermal statistical states on a superconducting quantum processer
Xue-Yi Guo(郭学仪), Shang-Shu Li(李尚书), Xiao Xiao(效骁), Zhong-Cheng Xiang(相忠诚), Zi-Yong Ge(葛自勇), He-Kang Li(李贺康), Peng-Tao Song(宋鹏涛), Yi Peng(彭益), Zhan Wang(王战), Kai Xu(许凯), Pan Zhang(张潘), Lei Wang(王磊), Dong-Ning Zheng(郑东宁), and Heng Fan(范桁). Chin. Phys. B, 2023, 32(1): 010307.
[2] Quantum partial least squares regression algorithm for multiple correlation problem
Yan-Yan Hou(侯艳艳), Jian Li(李剑), Xiu-Bo Chen(陈秀波), and Yuan Tian(田源). Chin. Phys. B, 2022, 31(3): 030304.
[3] Variational quantum eigensolvers by variance minimization
Dan-Bo Zhang(张旦波), Bin-Lin Chen(陈彬琳), Zhan-Hao Yuan(原展豪), and Tao Yin(殷涛). Chin. Phys. B, 2022, 31(12): 120301.
[4] Selected topics of quantum computing for nuclear physics
Dan-Bo Zhang(张旦波), Hongxi Xing(邢宏喜), Hui Yan(颜辉), Enke Wang(王恩科), and Shi-Liang Zhu(朱诗亮). Chin. Phys. B, 2021, 30(2): 020306.
[5] Experimental implementation of a continuous-time quantum random walk on a solid-state quantum information processor
Maimaitiyiming Tusun(麦麦提依明·吐孙), Yang Wu(伍旸), Wenquan Liu(刘文权), Xing Rong(荣星), Jiangfeng Du(杜江峰). Chin. Phys. B, 2019, 28(11): 110302.
[6] Demonstration of quantum permutation parity determine algorithm in a superconducting qutrit
Kunzhe Dai(戴坤哲), Peng Zhao(赵鹏), Mengmeng Li(李蒙蒙), Xinsheng Tan(谭新生), Haifeng Yu(于海峰), Yang Yu(于扬). Chin. Phys. B, 2018, 27(6): 060305.
[7] Coherent attacks on a practical quantum oblivious transfer protocol
Guang-Ping He(何广平). Chin. Phys. B, 2018, 27(10): 100308.
[8] Realization of quantum Fourier transform over ZN
Fu Xiang-Qun (付向群), Bao Wan-Su (鲍皖苏), Li Fa-Da (李发达), Zhang Yu-Chao (张宇超). Chin. Phys. B, 2014, 23(2): 020306.
[9] Application of quantum algorithms to direct measurement of concurrence of a two-qubit pure state
Wang Hong-Fu(王洪福) and Zhang Shou(张寿). Chin. Phys. B, 2009, 18(7): 2642-2648.
[10] A hybrid quantum encoding algorithm of vector quantization for image compression
Pang Chao-Yang (庞朝阳), Zhou Zheng-Wei(周正威), and Guo Guang-Can(郭光灿). Chin. Phys. B, 2006, 15(12): 3039-3043.
No Suggested Reading articles found!