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.

arXiv:1912.02728•Quantum Information and Computation•Feb 1, 2021•4 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

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•17 citations

A Continuous - Time Quantum Walk for Attributed Graphs Matching

Tewabe Chekole Workneh

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•1 citation

Continuous-time quantum walks over connected graphs, amplitudes and invariants

Phillip Dukes

We examine the time dependent amplitude $ ϕ_{j}\left( t\right)$ at each vertex $j$ of a continuous-time quantum walk on the cycle $C_{n}$. In many cases the Lissajous curve of the real vs. imaginary parts of each $ ϕ_{j}\left( t\right)$ reveals interesting shapes of the space of time-accessible amplitudes. We find two invariants of continuous-time quantum walks. First, considering the rate at which each amplitude evolves in time we find the quantity $T = \displaystyle\sum_{j=0}^{n-1} \lvert\dfrac{d ϕ_{j}\left( t\right)}{d t}\rvert^{2}$ is time invariant. The value of $T$ for any initial state can be minimized with respect to a global phase factor $e^{i θt}$ to some value $T_{min}$. An operator for $T_{min}$ is defined. For any simply connected graph $g$ the highest possible value of $T_{min}$ with respect to the initial state is found to be $T_{min}^{max}=\left( \frac{λ_{max}}{2}\right)^{2}$ where $λ_{max}$ is the maximum eigenvalue in the Laplace spectrum of $g$. A second invariant is found in the time-dependent probability distribution $P_{j}\left(t\right) = \lvertϕ_{j}\left(t\right)\rvert^{2}$ of any initial state satisfying $T_{min}^{max}$, with these conditions $\displaystyle\sum_{j=0}^{n-1}\left(P_{j}^{max} - P_{j}^{min}\right)^{2} = \dfrac{4}{n}$ for all simply connected graphs of $n$ vertices.

arXiv:1506.03086•Jun 9, 2015•0 citations

Finding Maximum Cliques on the D-Wave 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.

arXiv:1801.08649•Journal of Signal Processing Systems•May 3, 2018•74 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.
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.
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.
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.
We examine the time dependent amplitude $ ϕ_{j}\left( t\right)$ at each vertex jjj of a continuous-time quantum walk on the cycle CnC_{n}Cn​. In many cases the Lissajous curve of the real vs. imaginary parts of each $ ϕ_{j}\left( t\right)$ reveals interesting shapes of the space of time-accessible amplitudes. We find two invariants of continuous-time quantum walks. First, considering the rate at which each amplitude evolves in time we find the quantity T=∑j=0n−1∣dϕj(t)dt∣2T = \displaystyle\sum_{j=0}^{n-1} \lvert\dfrac{d ϕ_{j}\left( t\right)}{d t}\rvert^{2}T=j=0∑n−1​∣dtdϕj​(t)​∣2 is time invariant. The value of TTT for any initial state can be minimized with respect to a global phase factor eiθte^{i θt}eiθt to some value TminT_{min}Tmin​. An operator for TminT_{min}Tmin​ is defined. For any simply connected graph ggg the highest possible value of TminT_{min}Tmin​ with respect to the initial state is found to be Tminmax=(λmax2)2T_{min}^{max}=\left( \frac{λ_{max}}{2}\right)^{2}Tminmax​=(2λmax​​)2 where λmaxλ_{max}λmax​ is the maximum eigenvalue in the Laplace spectrum of ggg. A second invariant is found in the time-dependent probability distribution Pj(t)=∣ϕj(t)∣2P_{j}\left(t\right) = \lvertϕ_{j}\left(t\right)\rvert^{2}Pj​(t)=∣ϕj​(t)∣2 of any initial state satisfying TminmaxT_{min}^{max}Tminmax​, with these conditions ∑j=0n−1(Pjmax−Pjmin)2=4n\displaystyle\sum_{j=0}^{n-1}\left(P_{j}^{max} - P_{j}^{min}\right)^{2} = \dfrac{4}{n}j=0∑n−1​(Pjmax​−Pjmin​)2=n4​ for all simply connected graphs of nnn vertices.
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.