A parameter-independent algorithm of finding maximum clique with Seidel continuous-time quantum walks
Xi Li,
Xiao Chen,
Shouwei Hu,
Juan Xu,
Zhihao Liu
Affiliations
Xi Li
School of Computer Science and Engineering, Southeast University, No.2, Sipailou District, Nanjing, Jiangsu 210096, China; Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education, No.2, Southeast University Road, Jiangning District, Nanjing, Jiangsu 211189, China
Xiao Chen
School of Computer Science and Engineering, Southeast University, No.2, Sipailou District, Nanjing, Jiangsu 210096, China; Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education, No.2, Southeast University Road, Jiangning District, Nanjing, Jiangsu 211189, China
Shouwei Hu
School of Computer Science and Engineering, Southeast University, No.2, Sipailou District, Nanjing, Jiangsu 210096, China; Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education, No.2, Southeast University Road, Jiangning District, Nanjing, Jiangsu 211189, China
Juan Xu
College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, No.29, Junjun Dadao, Jiangning District, Nanjing, Jiangsu 210016, China; Collaborative Innovation Center of Novel Software Technology and Industrialization, No.29, Junjun Dadao, Jiangning District, Nanjing, Jiangsu 210023, China
Zhihao Liu
School of Computer Science and Engineering, Southeast University, No.2, Sipailou District, Nanjing, Jiangsu 210096, China; Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education, No.2, Southeast University Road, Jiangning District, Nanjing, Jiangsu 211189, China; Corresponding author
Summary: The maximum clique (MC) problem holds significance in network analysis. Quantum-based algorithms have recently emerged as promising approaches for this problem. However, these algorithms heavily depend on parameters of quantum system and vary significantly for different graphs. In order to tackle this issue, we initially demonstrate that continuous-time quantum walks (CTQW) driven by the Seidel matrix offer valuable insights into the clique structure of graphs, outperforming the CTQW driven by adjacency matrix. Specifically, we conduct an in-depth analysis for CTQW of 4 types of graphs, meticulously calculating the amplitudes associated with different vertices. Our findings consistently reveal that vertices belonging to MC exhibit the highest intensity at the largest frequency component of the probability amplitude for these types of graphs. Considering the varying intensities, we propose a parameter-independent algorithm for determining the MC. We compare our algorithm with a typical quantum-based algorithm, the results indicate that our algorithm exhibits greater stability.
