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

A Comparison of Quantum Algorithms for the Maximum Clique Problem

Andrew Haverly

Published Jan 1, 2021• 3 citations
OpenAlex

Abstract

Two of the most promising computational models for quantum computing are the qubit-based model and the continuous variable model, which result in two different computational approaches, namely the qubit gate model and boson sampling. The qubit gate model is a universal form of quantum computation that relies heavily on the principles of superposition and entanglement to solve problems using qubits based on technologies ranging from magnetic fields created from superconducting materials to the spins of valence electrons in atoms. Boson sampling is a non-universal form of quantum computation that uses bosons as continuous-variable values for its computation. Both models show promising prospects for useful quantum advantages over classical computers, but these models are fundamentally different, not only on their technologies but on their applications. Each model excels in different sets of applications.\nA direct comparison for solving a problem using qubit gate models and boson sampling allows one to better understand not only the individual technologies, but how to decide which model is better suited to solving a given problem and how to start development on solving the given problem. This thesis uses the maximum clique problem to examine the application development process in the qubit gate model and boson sampling as well as a comparison of other known algorithms to the maximum clique problem. The maximum clique problem is an NP-Hard problem concerned with finding the largest fully-connected subgraph. The qubit gate model algorithm to the maximum clique problem is a novel algorithm.

Related papers

Quantum programming paradigms: boson sampling vs qubit gates

Sonia López Alarcón, Andrew Haverly

Quantum technology and its application in quantum computing has been gaining relevance and making incredible strides in the achievement of practical implementations of this new form of hardware acceleration. However, in order to really succeed as a computational choice in the many application fields — from science to economy—, the devices need to be programmable and within reach to non-quantum users. There are multiple approaches to solve the quantum computing riddle. This paper looks at two of them, Boson sampling and qubit gate-based quantum accelerators, and compares their implementation and programmability of a common problem: the maximum clique problem.

Photonics for Quantum (PfQ)•Jul 19, 2022•1 citation

Quantum algorithms and the maximum clique problem in graphs

Matheus Augusto Condé Dias

Determining the cardinality of the maximum clique on a simple graph is a NP-hard problem with several applications of interest. The best know classical algorithm for this problem has 𝒪(3𝑛/3) time complexity. Classical computing uses phenomena from classical physics to model, store and process information. Consequently, the entire model of classical computing is bounded superiorly by the limits of classical physics. As an alternative, Quantum Computing has been developed to take advantage of quantum phenomena and provide the constructions of circuits capable of performing certain computations more efficiently. In this paper, two quantum solutions to the maximum clique problem will be proposed and analyzed, based on the Grover Quantum Search algorithms and the Quantum Minimal Search Algorithm, comparing their respective time complexities with the best known classical solution.

•Sep 14, 2022•0 citations

Quantum-Inspired Classical Algorithm for Graph Problems by Gaussian Boson Sampling

Changhun Oh, Bill Fefferman, Liang Jiang +1 more

We present a quantum-inspired classical algorithm that can be used for graph-theoretical problems, such as finding the densest k subgraph and finding the maximum weight clique, which are proposed as applications of a Gaussian boson sampler. The main observation from Gaussian boson samplers is that a given graph’s adjacency matrix to be encoded in a Gaussian boson sampler is non-negative and that computing the output probability of Gaussian boson sampling restricted to a non-negative adjacency matrix is thought to be strictly easier than general cases. We first provide how to program a given graph problem into our efficient classical algorithm. We then numerically compare the performance of ideal and lossy Gaussian boson samplers, our quantum-inspired classical sampler, and the uniform sampler for finding the densest k subgraph and finding the maximum weight clique and show that the advantage from Gaussian boson samplers is not significant in general. We finally discuss the potential advantage of a Gaussian boson sampler over the proposed quantum-inspired classical sampler. Published by the American Physical Society 2024

arXiv:2302.00536•PRX Quantum•May 23, 2024•11 citations

Solving Maximum Clique Problem using a novel Quantum-inspired Evolutionary Algorithm

Pronaya Prosun Das, Mozammel H. A. Khan

Maximum Clique Problem (MCP) is one of the most important NP-hard problems in the area of soft computing and it has many real world applications in numerous fields ranging from coding theory to the determination of the structure of a protein molecule. Different heuristic, Meta heuristic and hybrid solution approaches have been applied to obtain the solution. In this paper, we demonstrate a Quantum-inspired Evolutionary Algorithm (QEA) to solve MCP. We have used one dimensional arrays of Q-bits called Q-bit individuals to produce binary individuals. After production of binary individuals, we have repaired and improved them. Here, Q-gate is the main variation operator applied on Q-bit individuals. Our algorithm was tested on DIMACS benchmark graphs and 40 of them were tested. The results obtained here are extremely encouraging. For almost all of the datasets, we get the optimal results reported on DIMACS benchmark and also compared our results with other related works. For some cases we get better results than other works.

International Conference on Electrical Engineering and Information Communication Technology•May 1, 2015•4 citations

Circuit Synthesis of Maximum Clique Problem using Combinatorial Approach of Classical-Quantum Hybrid Model.

Arpita Sanyal, Amit Saha, Banani Saha +1 more

In the Maximum Clique Problem, the objective is to find a clique whose size is maximum among all the cliques of an arbitrary undirected and unweighted graph. Maximum Clique Problem resembles with minimum vertex cover problem, independent set problem. As it is an NP-hard problem, no polynomial time algorithms can be found. As these problems have several important practical applications such as information retrieval, community detection in network, spatial data mining etc, it is of great interest to try to synthesis the circuit of Maximum Clique Problem. In classical computing any brute-force solution to the Maximum Clique Problem requires an exponential increase of time with the size of the problem (i.e., with time complexity of $O(2^n)$). In this paper, Maximum Clique Problem has been solved using combinatorial approach of Grover's search algorithm. An algorithm has been proposed that auto-generates the circuit for any given undirected and unweighted graph which makes the approach generalized in nature for Maximum Clique Problem. Computational speed up is achieved by using our approach with the help of quantum mechanical effect that is quantum superposition. We have simulated the proposed circuit using IBM's QISkit platform and verified its correctness.

•Mar 10, 2020•0 citations

Quantum speedup in solving the maximal-clique problem

Weng-Long Chang, Qi Yu, Zhaokai Li +3 more

The maximal-clique problem, to find the maximally sized clique in a given graph, is classically an NP-complete computational problem, which has potential applications ranging from electrical engineering, computational chemistry, and bioinformatics to social networks. Here we develop a quantum algorithm to solve the maximal-clique problem for any graph $G$ with $n$ vertices with quadratic speedup over its classical counterparts, where the time and spatial complexities are reduced to, respectively, $O(\sqrt{{2}^{n}})$ and $O({n}^{2})$. With respect to oracle-related quantum algorithms for the NP-complete problems, we identify our algorithm as optimal. To justify the feasibility of the proposed quantum algorithm, we successfully solve a typical clique problem for a graph $G$ with two vertices and one edge by carrying out a nuclear magnetic resonance experiment involving four qubits.

arXiv:1803.11356•Physical Review A•Mar 29, 2018•17 citations
Two of the most promising computational models for quantum computing are the qubit-based model and the continuous variable model, which result in two different computational approaches, namely the qubit gate model and boson sampling. The qubit gate model is a universal form of quantum computation that relies heavily on the principles of superposition and entanglement to solve problems using qubits based on technologies ranging from magnetic fields created from superconducting materials to the spins of valence electrons in atoms. Boson sampling is a non-universal form of quantum computation that uses bosons as continuous-variable values for its computation. Both models show promising prospects for useful quantum advantages over classical computers, but these models are fundamentally different, not only on their technologies but on their applications. Each model excels in different sets of applications.\nA direct comparison for solving a problem using qubit gate models and boson sampling allows one to better understand not only the individual technologies, but how to decide which model is better suited to solving a given problem and how to start development on solving the given problem. This thesis uses the maximum clique problem to examine the application development process in the qubit gate model and boson sampling as well as a comparison of other known algorithms to the maximum clique problem. The maximum clique problem is an NP-Hard problem concerned with finding the largest fully-connected subgraph. The qubit gate model algorithm to the maximum clique problem is a novel algorithm.
Quantum technology and its application in quantum computing has been gaining relevance and making incredible strides in the achievement of practical implementations of this new form of hardware acceleration. However, in order to really succeed as a computational choice in the many application fields — from science to economy—, the devices need to be programmable and within reach to non-quantum users. There are multiple approaches to solve the quantum computing riddle. This paper looks at two of them, Boson sampling and qubit gate-based quantum accelerators, and compares their implementation and programmability of a common problem: the maximum clique problem.
Determining the cardinality of the maximum clique on a simple graph is a NP-hard problem with several applications of interest. The best know classical algorithm for this problem has 𝒪(3𝑛/3) time complexity. Classical computing uses phenomena from classical physics to model, store and process information. Consequently, the entire model of classical computing is bounded superiorly by the limits of classical physics. As an alternative, Quantum Computing has been developed to take advantage of quantum phenomena and provide the constructions of circuits capable of performing certain computations more efficiently. In this paper, two quantum solutions to the maximum clique problem will be proposed and analyzed, based on the Grover Quantum Search algorithms and the Quantum Minimal Search Algorithm, comparing their respective time complexities with the best known classical solution.
We present a quantum-inspired classical algorithm that can be used for graph-theoretical problems, such as finding the densest k subgraph and finding the maximum weight clique, which are proposed as applications of a Gaussian boson sampler. The main observation from Gaussian boson samplers is that a given graph’s adjacency matrix to be encoded in a Gaussian boson sampler is non-negative and that computing the output probability of Gaussian boson sampling restricted to a non-negative adjacency matrix is thought to be strictly easier than general cases. We first provide how to program a given graph problem into our efficient classical algorithm. We then numerically compare the performance of ideal and lossy Gaussian boson samplers, our quantum-inspired classical sampler, and the uniform sampler for finding the densest k subgraph and finding the maximum weight clique and show that the advantage from Gaussian boson samplers is not significant in general. We finally discuss the potential advantage of a Gaussian boson sampler over the proposed quantum-inspired classical sampler. Published by the American Physical Society 2024
Maximum Clique Problem (MCP) is one of the most important NP-hard problems in the area of soft computing and it has many real world applications in numerous fields ranging from coding theory to the determination of the structure of a protein molecule. Different heuristic, Meta heuristic and hybrid solution approaches have been applied to obtain the solution. In this paper, we demonstrate a Quantum-inspired Evolutionary Algorithm (QEA) to solve MCP. We have used one dimensional arrays of Q-bits called Q-bit individuals to produce binary individuals. After production of binary individuals, we have repaired and improved them. Here, Q-gate is the main variation operator applied on Q-bit individuals. Our algorithm was tested on DIMACS benchmark graphs and 40 of them were tested. The results obtained here are extremely encouraging. For almost all of the datasets, we get the optimal results reported on DIMACS benchmark and also compared our results with other related works. For some cases we get better results than other works.
In the Maximum Clique Problem, the objective is to find a clique whose size is maximum among all the cliques of an arbitrary undirected and unweighted graph. Maximum Clique Problem resembles with minimum vertex cover problem, independent set problem. As it is an NP-hard problem, no polynomial time algorithms can be found. As these problems have several important practical applications such as information retrieval, community detection in network, spatial data mining etc, it is of great interest to try to synthesis the circuit of Maximum Clique Problem. In classical computing any brute-force solution to the Maximum Clique Problem requires an exponential increase of time with the size of the problem (i.e., with time complexity of O(2n)O(2^n)O(2n)). In this paper, Maximum Clique Problem has been solved using combinatorial approach of Grover's search algorithm. An algorithm has been proposed that auto-generates the circuit for any given undirected and unweighted graph which makes the approach generalized in nature for Maximum Clique Problem. Computational speed up is achieved by using our approach with the help of quantum mechanical effect that is quantum superposition. We have simulated the proposed circuit using IBM's QISkit platform and verified its correctness.
The maximal-clique problem, to find the maximally sized clique in a given graph, is classically an NP-complete computational problem, which has potential applications ranging from electrical engineering, computational chemistry, and bioinformatics to social networks. Here we develop a quantum algorithm to solve the maximal-clique problem for any graph GGG with nnn vertices with quadratic speedup over its classical counterparts, where the time and spatial complexities are reduced to, respectively, O(2n)O(\sqrt{{2}^{n}})O(2n​) and O(n2)O({n}^{2})O(n2). With respect to oracle-related quantum algorithms for the NP-complete problems, we identify our algorithm as optimal. To justify the feasibility of the proposed quantum algorithm, we successfully solve a typical clique problem for a graph GGG with two vertices and one edge by carrying out a nuclear magnetic resonance experiment involving four qubits.