中国物理B ›› 2025, Vol. 34 ›› Issue (12): 120302-120302.doi: 10.1088/1674-1056/addeb8

• • 上一篇    下一篇

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. 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
  • 收稿日期:2025-04-11 修回日期:2025-05-21 接受日期:2025-05-30 发布日期:2025-12-10
  • 通讯作者: Fei Gao E-mail:gaof@bupt.edu.cn
  • 基金资助:
    Project supported by the National Natural Science Foundation of China (Grant Nos. 62372048, 62371069, 62272056, and U25B2014).

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. 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
  • Received:2025-04-11 Revised:2025-05-21 Accepted:2025-05-30 Published:2025-12-10
  • Contact: Fei Gao E-mail:gaof@bupt.edu.cn
  • Supported by:
    Project supported by the National Natural Science Foundation of China (Grant Nos. 62372048, 62371069, 62272056, and U25B2014).

PDF (PC)

7

赞

摘要： 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.

关键词: quantum machine learning, block-encoding, dimensionality reduction, marginal Fisher analysis, graph construction

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.

Key words: quantum machine learning, block-encoding, dimensionality reduction, marginal Fisher analysis, graph construction

中图分类号:  (Quantum algorithms, protocols, and simulations)

  • 03.67.Ac
03.67.Lx (Quantum computation architectures and implementations)