Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

iScience

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

Xi Li, Xiao Chen, Shouwei Hu, Juan Xu, Zhihao Liu

Published Jan 19, 2024• 4 citations
Publisher

Abstract

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.

DOI
10.1016/j.isci.2024.108953

Related papers

Algorithms for finding the maximum clique based on continuous time quantum walks

Xi Li, Mingyou Wu, Hanwu Chen +1 more

In this work, the application of continuous time quantum walks (CTQW) to the Maximum Clique (MC) problem was studied. Performing CTQW on graphs can generate distinct periodic probability amplitudes for different vertices. We found that the intensities of the probability amplitudes at some frequencies imply the clique structure of special kinds of graphs. Recursive algorithms with time complexity O(N^6) in classical computers were proposed to determine the maximum clique. We have experimented on random graphs where each edge exists with different probabilities. Although counter examples were not found for random graphs, whether these algorithms are universal is beyond the scope of this work.

Quantum Information and Computation•Feb 1, 2021•2 citations

Algorithm for Finding the Maximum Clique Based on Continuous Time Quantum Walk

Xi Li, Mingyou Wu, Hanwu Chen

In this work, we consider the application of continuous time quantum walking(CTQW) to the Maximum Clique(MC) Problem. Performing CTQW on graphs will generate distinct periodic probability amplitude for different vertices. We will show that the intensity of the probability amplitude at frequency indeed implies the clique structure of some special kinds of graph. And recursive algorithms with time complexity $O(N^5)$ in classical computers for finding the maximum clique are proposed. We have experimented on random graphs where each edge exists with probabilities 0.3, 0.5 and 0.7. Although counter examples are not found for random graphs, whether these algorithms are universal is not known to us.

arXiv:1912.02728•Dec 5, 2019•3 citations

Correlation between the continuous-time quantum walk and cliques in graphs and its application

Mingyou Wu, Xi Li, Zhihao Liu +1 more

The continuous-time quantum walk (CTQW) provides a new approach to problems in graph theory. In this paper, the correlation between the CTQW and cliques in graphs is studied, and an approximate algorithm for the maximum clique problem (MCP) based on the CTQW is given. Via both numerical and theoretical analyses, it is found that the maximum clique is related to the transmission characteristics of the CTQW on some special graphs. For general graphs, the correlation is difficult to describe analytically. Therefore, the transmission characteristics of the CTQW are applied as a vertex selection criterion to a classical MCP algorithm and it is compared with the original algorithm. Numerous simulation on general graphs shows that the new algorithm is more efficient. Furthermore, an approximate MCP algorithm based on the CTQW is introduced, which only requires a very small number of searches with a high approximation ratio.

International Journal of Quantum Information•Apr 22, 2021•1 citation

Finding Maximum Cliques on a Quantum Annealer

Guillaume Chapuis, Hristo N. Djidjev, Georg Hahn +1 more

This paper assesses the performance of the D-Wave 2X (DW) quantum annealer for finding a maximum clique in a graph, one of the most fundamental and important NP-hard problems. Because the size of the largest graphs DW can directly solve is quite small (usually around 45 vertices), we also consider decomposition algorithms intended for larger graphs and analyze their performance. For smaller graphs that fit DW, we provide formulations of the maximum clique problem as a quadratic unconstrained binary optimization (QUBO) problem, which is one of the two input types (together with the Ising model) acceptable by the machine, and compare several quantum implementations to current classical algorithms such as simulated annealing, Gurobi, and third-party clique finding heuristics. We further estimate the contributions of the quantum phase of the quantum annealer and the classical post-processing phase typically used to enhance each solution returned by DW. We demonstrate that on random graphs that fit DW, no quantum speedup can be observed compared with the classical algorithms. On the other hand, for instances specifically designed to fit well the DW qubit interconnection network, we observe substantial speed-ups in computing time over classical approaches.

ACM International Conference on Computing Frontiers (CF)•May 15, 2017•31 citations

A Continuous - Time Quantum Walk for Attributed Graphs Matching

Tewabe Chekole

Diverse facets Of the Theory of Quantum Walks on Graph are reviewed Till now .In specific, Quantum network routing, Quantum Walk Search Algorithm, Element distinctness associated to the eigenvalues of Graphs and the use of these relation /connection in the study of Quantum walks is furthermore described. Different Researchers had contribution and put their benchmark idea Pertaining with this research concept. I furthermore try to investigate recent Application of Quantum walks, In specific the problem pertained with Graph matching i.e Matching nodes(vertices) of the Graphs. In this research paper,I consider how Continuous-time quantum walk (CTQW) can be directed to Graph-matching problems. The matching problem is abstracted using weighted(attributed) Graphs that connects vertices's of one Graph to other and Try to compute the distance b/n those Graphs Node's Beside that finding the matched nodes and the Cost related to Matching. eventually measuring the distance between two Graphs which might have different size then by using k-nearest neighbor (k-NN) method try to classifying those graph based on closest training examples in the feature space.

arXiv:1801.10339•Jan 31, 2018•0 citations

Implementation of Grover’s Algorithm to Solve the Maximum Clique Problem

Andrew Haverly, Sonia Martín López

The maximum clique of an undirected graph is the largest subgraph in which an edge exists between every vertex. The maximum clique problem presents itself in various fields and finding a tractable algorithm to solve the problem is important. This paper introduces an oracle to solve the maximum clique problem using Grover’s quantum algorithm. This approach potentially solves the maximum clique problem in $O\left( {\left| V \right|\sqrt {{2^{\left| V \right|}}} } \right)$ time complexity rather than the current classical time complexity of O(2|V|) of the best known algorithm, where |V| is the number of vertices in the graph. The full circuit implementation is presented using the open-source Qiskit environment [1]. The paper also analyzes the growth of the hardware resources requirements with the number of vertices in the targeted graph.

IEEE Computer Society Annual Symposium on VLSI•Jul 1, 2021•16 citations
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.
In this work, the application of continuous time quantum walks (CTQW) to the Maximum Clique (MC) problem was studied. Performing CTQW on graphs can generate distinct periodic probability amplitudes for different vertices. We found that the intensities of the probability amplitudes at some frequencies imply the clique structure of special kinds of graphs. Recursive algorithms with time complexity O(N^6) in classical computers were proposed to determine the maximum clique. We have experimented on random graphs where each edge exists with different probabilities. Although counter examples were not found for random graphs, whether these algorithms are universal is beyond the scope of this work.
In this work, we consider the application of continuous time quantum walking(CTQW) to the Maximum Clique(MC) Problem. Performing CTQW on graphs will generate distinct periodic probability amplitude for different vertices. We will show that the intensity of the probability amplitude at frequency indeed implies the clique structure of some special kinds of graph. And recursive algorithms with time complexity O(N5)O(N^5)O(N5) in classical computers for finding the maximum clique are proposed. We have experimented on random graphs where each edge exists with probabilities 0.3, 0.5 and 0.7. Although counter examples are not found for random graphs, whether these algorithms are universal is not known to us.
The continuous-time quantum walk (CTQW) provides a new approach to problems in graph theory. In this paper, the correlation between the CTQW and cliques in graphs is studied, and an approximate algorithm for the maximum clique problem (MCP) based on the CTQW is given. Via both numerical and theoretical analyses, it is found that the maximum clique is related to the transmission characteristics of the CTQW on some special graphs. For general graphs, the correlation is difficult to describe analytically. Therefore, the transmission characteristics of the CTQW are applied as a vertex selection criterion to a classical MCP algorithm and it is compared with the original algorithm. Numerous simulation on general graphs shows that the new algorithm is more efficient. Furthermore, an approximate MCP algorithm based on the CTQW is introduced, which only requires a very small number of searches with a high approximation ratio.
This paper assesses the performance of the D-Wave 2X (DW) quantum annealer for finding a maximum clique in a graph, one of the most fundamental and important NP-hard problems. Because the size of the largest graphs DW can directly solve is quite small (usually around 45 vertices), we also consider decomposition algorithms intended for larger graphs and analyze their performance. For smaller graphs that fit DW, we provide formulations of the maximum clique problem as a quadratic unconstrained binary optimization (QUBO) problem, which is one of the two input types (together with the Ising model) acceptable by the machine, and compare several quantum implementations to current classical algorithms such as simulated annealing, Gurobi, and third-party clique finding heuristics. We further estimate the contributions of the quantum phase of the quantum annealer and the classical post-processing phase typically used to enhance each solution returned by DW. We demonstrate that on random graphs that fit DW, no quantum speedup can be observed compared with the classical algorithms. On the other hand, for instances specifically designed to fit well the DW qubit interconnection network, we observe substantial speed-ups in computing time over classical approaches.
Diverse facets Of the Theory of Quantum Walks on Graph are reviewed Till now .In specific, Quantum network routing, Quantum Walk Search Algorithm, Element distinctness associated to the eigenvalues of Graphs and the use of these relation /connection in the study of Quantum walks is furthermore described. Different Researchers had contribution and put their benchmark idea Pertaining with this research concept. I furthermore try to investigate recent Application of Quantum walks, In specific the problem pertained with Graph matching i.e Matching nodes(vertices) of the Graphs. In this research paper,I consider how Continuous-time quantum walk (CTQW) can be directed to Graph-matching problems. The matching problem is abstracted using weighted(attributed) Graphs that connects vertices's of one Graph to other and Try to compute the distance b/n those Graphs Node's Beside that finding the matched nodes and the Cost related to Matching. eventually measuring the distance between two Graphs which might have different size then by using k-nearest neighbor (k-NN) method try to classifying those graph based on closest training examples in the feature space.
The maximum clique of an undirected graph is the largest subgraph in which an edge exists between every vertex. The maximum clique problem presents itself in various fields and finding a tractable algorithm to solve the problem is important. This paper introduces an oracle to solve the maximum clique problem using Grover’s quantum algorithm. This approach potentially solves the maximum clique problem in O(∣V∣2∣V∣)O\left( {\left| V \right|\sqrt {{2^{\left| V \right|}}} } \right)O(∣V∣2∣V∣​) time complexity rather than the current classical time complexity of O(2|V|) of the best known algorithm, where |V| is the number of vertices in the graph. The full circuit implementation is presented using the open-source Qiskit environment [1]. The paper also analyzes the growth of the hardware resources requirements with the number of vertices in the targeted graph.