A parameter-independent algorithm of finding maximum clique with Seidel continuous-time quantum walks

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.

Graphical abstract

Highlights

• •

  Present a parameter-independent quantum-based algorithm for finding maximum clique

• •

  Demonstrated the correlation of clique structure and Seidel quantum walk

• •

  Give several inequalities for four type of graph on amplitudes of CTQW

• •

  Compared the algorithm with CTQW to the simulated quantum evolution algorithm

Abstract

Physics; Quantum physics