|
|
|
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.
|
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: gaof@bupt.edu.cn
|
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 |
| No Suggested Reading articles found! |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
Altmetric
|
|
blogs
Facebook pages
Wikipedia page
Google+ users
|
Online attention
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
View more on Altmetrics
|
|
|
