|
|
|
Quantum algorithm for marginal Fisher analysis |
| Jing Li(李静)1,2,3, Yanqi Song(宋燕琪)4, Sujuan Qin(秦素娟)1, Wenmin Li(李文敏)1, and Fei Gao(高飞)1,† |
1 State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China;
2 National Engineering Research Center of Disaster Backup and Recovery, Beijing University of Posts and Telecommunications, Beijing 100876, China;
3 School of Cyberspace Security, Beijing University of Posts and Telecommunications, Beijing 100876, China;
4 China Academy of Information and Communications Technology, Beijing 100191, China |
|
|
|
|
Abstract Marginal Fisher analysis (MFA) stands out as a prominent dimensionality reduction algorithm, striving to minimize within-class scatter while maximizing the separability between marginal data points. However, MFA and its variants require substantial computational resources when dealing with large-scale data. To address this, we propose quantum algorithms for MFA (called QMFA). QMFA is composed of two core processes: the first is the efficient construction of the weight matrices for the intrinsic and penalty graphs, and the second is solving the generalized eigenvalue problem (GEP) using the block-encoding technique. Compared to classical MFA, the proposed QMFA achieves a polynomial acceleration in the number of samples and exponential acceleration in the dimensionality. Additionally, we investigate quantum algorithms for different variants of MFA. Specifically, for enhanced MFA and multiple MFA, we address the construction of the related weight matrix, which differs from that in standard MFA. For kernel MFA, we solve the GEP associated with the corresponding kernel matrix. The proposed quantum algorithms achieve a speedup equivalent to that of QMFA.
|
Received: 11 April 2025
Revised: 21 May 2025
Accepted manuscript online: 30 May 2025
|
|
PACS:
|
03.67.Ac
|
(Quantum algorithms, protocols, and simulations)
|
| |
03.67.Lx
|
(Quantum computation architectures and implementations)
|
|
| Fund: Project supported by the National Natural Science Foundation of China (Grant Nos. 62372048, 62371069, 62272056, and U25B2014). |
Corresponding Authors:
Fei Gao
E-mail: gaof@bupt.edu.cn
|
Cite this article:
Jing Li(李静), Yanqi Song(宋燕琪), Sujuan Qin(秦素娟), Wenmin Li(李文敏), and Fei Gao(高飞) Quantum algorithm for marginal Fisher analysis 2025 Chin. Phys. B 34 120302
|
[1] Jordan M I and Mitchell T M 2015 Science 349 255
[2] Shor P W 1994 Proceedings 35th Annual Symposium on Foundations of Computer Science, 1994, Santa Fe, NM, USA, IEEE, pp. 124–134
[3] Grover L K 1997 Phys. Rev. Lett. 79 325
[4] Harrow A W, Hassidim A and Lloyd S 2009 Phys. Rev. Lett. 103 150502
[5] Rebentrost P, Mohseni M and Lloyd S 2014 2009 Phys. Rev. Lett. 113 130503
[6] Wiebe N, Kapoor A and Svore K M 2015 Quantum Inform. Comput. 15 316
[7] Song Y, Wu Y, Wu S, Li D, Wen Q, Qin S and Gao F 2024 Sci. China- Phys. Mech. Astron. 67 250311
[8] Kerenidis I and Landman J 2021 Phys. Rev. A 103 042415
[9] Li Y M, Liu H L, Pan S J, Qin S J, Gao F, Sun D X and Wen Q Y 2023 Phys. Rev. A 107 022421
[10] Ni X H, Cai B B, Liu H L, Qin S J, Gao F and Wen Q Y 2024 Adv. Quantum Technol. 7 2300419
[11] Li L, Li J, Song Y, Qin S, Wen Q and Gao F 2025 Sci. China-Phys. Mech. Astron. 68 1
[12] Wu S Y, Song Y Q, Li R Z, Qin S J, Wen Q Y and Gao F 2025 Adv. Quantum Technol. 2400484
[13] Zhang H, Wang S, Liu X, Shen Y and Wang Y 2024 Chin. Phys. B 33 020310
[14] Li J A, Dong D, Wei Z, Liu Y, Pan Y, Nori F and Zhang X 2020 Nat. Hum. Behav. 4 294
[15] Kwak Y, YunWJ, Jung S, Kim J K and Kim J 2021 International Conference on Information and Communication Technology Convergence, 2021, Jeju Island, Korea, IEEE, pp. 416–420
[16] Jin Y X, Xu H Z, Wang Z A, Zhuang W F, Huang K X, Shi Y H, Ma W G, Li T M, Chen C T, Xu K, et al. 2024 Chin. Phys. B 33 050301
[17] Ayesha S, Hanif M K and Talib R 2020 Inf. Fusion 59 44
[18] Liang X, Lin Y E, Zhang S and Fang X 2023 Appl. Intell. 53 12873
[19] Liu L, Chen J, Liu T, Chen C P and Yang B 2024 IEEE T. Cybern. 55 5
[20] Tharwat A, Gaber T, Ibrahim A and Hassanien A E 2017 AI Commun. 30 169
[21] He X and Niyogi P 2003 Advances in Neural Information Processing Systems 16 153
[22] Yan S, Xu D, Zhang B, Zhang H J, Yang Q and Lin S 2006 IEEE Trans. Pattern Anal. Mach. Intell. 29 40
[23] Xu D, Yan S, Tao D, Lin S and Zhang H J 2007 IEEE Trans. Image Process. 16 2811
[24] Huang P and Chen C 2009 International Conference on Artificial Intelligence and Computational Intelligence, 2009, Shanghai, China, IEEE, pp. 403–407
[25] Huang Z, Zhu H, Zhou J T and Peng X 2018 IEEE Trans. Ind. Electron. 66 9798
[26] Jiang L, Xuan J and Shi T 2013 Mech. Syst. Signal Proc. 41 113
[27] Wang Z and Sun X 2012 J. Comput. 7 2298
[28] Lloyd S, Mohseni M and Rebentrost P 2014 Nat. Phys. 10 631
[29] Yu C H, Gao F, Lin S and Wang J 2019 Quantum Inf. Process. 18 249
[30] Cong I and Duan L 2016 New J. Phys. 18 073011
[31] He X, Zhang A and Zhao S 2022 Quantum Inf. Process. 21 86
[32] Li Y M, Liu H L, Pan S J, Qin S J, Gao F and Wen Q Y 2023 Phys. Rev. A 108 042418
[33] Wiebe N, Kapoor A and Svore K M 2014 arXiv: 1412.3489[quant-ph]
[34] Kerenidis I, Landman J, Luongo A and Prakash A 2019 33rd Conference on Neural Information Processing Systems, 2019, Vancouver, Canada, pp. 4134–4144
[35] Dürr C and Høyer P 1996 arXiv: quant-ph/9607014
[36] Dürr C, Heiligman M, Høyer P and Mhalla M 2006 SIAM J. Comput. 35 1310
[37] Chakraborty S, Gilyén A and Jeffery S 2019 46th International Colloquium on Automata, Languages, and Programming, 2019, Dagstuhl, Germany, pp. 33:1–33:14
[38] Low G H and Chuang I L 2019 Quantum 3 163
[39] Wan L C, Yu C H, Pan S J, Qin S J, Gao F and Wen Q Y 2021 Phys. Rev. A 104 062414
[40] Gao S and Yang Y G 2023 Chin. Phys. B 32 100309
[41] Gilyén A, Su Y, Low G H and Wiebe N 2019 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019, Phoenix, AZ, USA, pp. 193–204
[42] Kerenidis I and Prakash A 2016 arXiv: 1603.08675[quant-ph]
[43] Nguyen Q T, Kiani B T and Lloyd S 2022 Quantum 6 876
[44] Chakraborty S, Morolia A and Peduri A 2023 Quantum 7 988
[45] Shao C and Liu J P 2022 Proc. R. Soc. A 478 20210797
[46] Buhrman H, Cleve R, Watrous J and De Wolf R 2001 Phys. Rev. Lett. 87 167902
[47] Li Y M, Liu H L, Pan S J, Qin S J, Gao F and Wen Q Y 2023 Quantum Inf. Process. 22 163
[48] Li Y, Zhou R G, Xu R, Hu W and Fan P 2020 Quantum Sci. Technol. 6 014001
[49] https://www.ibm.com/quantum/qiskit
[50] Hearst M A, Dumais S T, Osuna E, Platt J and Scholkopf B 1998 IEEE Intell. Syst. Appl. 13 18
[51] https://scikit-learn.org/stable/modules/generated/sklearn.datasets.load digits
[52] Bharti K, Cervera-Lierta A, Kyaw T H, Haug T, Alperin-Lea S, Anand A, Degroote M, Heimonen H, Kottmann J S, Menke T, et al. 2022 Rev. Mod. Phys. 94 015004
[53] Jerbi S, Fiderer L J, Poulsen Nautrup H, Kübler J M, Briegel H J and Dunjko V 2023 Nat. Commun. 14 517
[54] Schuld M, Bocharov A, Svore K M and Wiebe N 2020 Phys. Rev. A 101 032308 |
| 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
|
|
|
