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

arXiv:2611.10640

A Grover-Amplified Oracle for Maximum Clique on Graph, Minimum Hitting set and Dualizations on Hypergraphs Built on Quantum Phase Estimation

Francisco Piñero, Fernando L. Pelayo, Hernán I. de la Cruz, Jose J. Paulet, Mauro Mezzini, Fernando Cuartero

Published Nov 7, 2026• 0 citations
arXivHTMLPDF

Abstract

In this paper, we use a quantum circuit called the Graph Encoding Operator which, applied to the complement $\bar G$ of any graph $G$, yields an oracle for the maximum clique problem suitable for amplification via Grover's algorithm. Analogously, we devise a Hypergraph Encoding Operator which, when applied to a hypergraph $\mathcal H$, yields an oracle for the minimum hitting set suitable for amplification via Grover's algorithm. Interestingly, the latter oracle provides, when measured, an approximation of the number of hitting sets of the hypergraph, thus solving the dualization problem for positive Boolean functions represented in a positive irredundant disjunctive normal form. We give the full construction of both operators, prove their correctness, analyze their complexity, and provide an implementation on a quantum simulator. We discuss the resulting complexity, contrast them with existing quantum computer algorithms based on Grover search and we will show that our algorithms outperform, to the best of our knowledge, all of the previous algorithms on space computational complexity by requiring only $O(N)$ number of qubits with respect to the number of vertices $N$, for representing both graphs and hypergraphs in the encoding operator and, consequently, results in an oracle for both graphs and hypergraphs that uses only $O(N)$ qubits even when the hypergraph contains an exponential (on the number of vertices) number of hyperedges.

DOI
10.48550/arxiv.2611.10640

Related papers

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

Efficient quantum detection of maximum clique via hybrid heuristic and global information encoding

Wenmin Han, Shiqi Zheng, Peian Chen +1 more

Abstract The maximum clique problem (MCP) is to find the largest complete subgraph in an undirected graph, that is, the subgraph in which there are edges between every two different vertices. It is an NP-Hard problem with wide applications, including bioinformatics, social networks, data mining, and other fields. This paper proposes an enhanced quantum solution method that introduces a pre-detection phase based on a hybrid heuristic algorithm and a vertex pruning strategy, encoding the prior constraints on clique size into quantum registers as global information. It encodes the prior constraints on clique size into quantum registers as global information. In contrast, state-of-the-art Grover-based methods for n-vertex graphs require O ( n 2 n ) iterations and O ( n ) measurements. By leveraging a global information encoding mechanism, the proposed method compresses the number of iterations to O ( 2 n ) and only needs a constant number of measurements to identify all maximum cliques. We validate algorithmic correctness through simulations on IBM’s Qiskit platform and benchmark qubit/gate efficiency against existing Grover-based MCP solvers.

arXiv:2509.01261•Journal of Physics A Mathematical and Theoretical•May 13, 2026•1 citation

Linear-depth quantum oracles for clique problems from edge colorings and graph states, with linear non-Clifford cost and a provably bounded-error k-clique search

Payman Kazemikhah, Ali Hadizadeh Moghadam, Hossein Aghababa

Quantum algorithms for clique problems are usually analyzed in the query model, where the graph is accessed through an oracle of unit cost. When the oracle must itself be compiled into gates, published $k$-clique circuits have depth quadratic in the number $n$ of vertices, and every oracle that counts edges spends at least one non-Clifford gate per edge. We first show that scheduling the commuting edge gates by a proper edge coloring yields adjacency-type oracles, including an exact $k$-clique oracle, whose depth and width are linear in $n$, within a logarithmic factor of a depth--width lower bound. Our central result is a $k$-clique oracle in which the graph enters only through the Clifford gate that prepares a graph state, so that its non-Clifford cost is linear in $n$ for every graph. We analyze this oracle exactly: on a candidate vertex set it acts as a reflection whose overlap is $-1$ for cliques and, as we prove, at most $5/8$ in modulus otherwise, a tight bound that tends to $1/2$ as the candidate set grows. A two-qubit phase-estimation filter turns the reflection into a one-sided bounded-error phase oracle, and amplitude amplification then finds a $k$-clique with $O(\sqrt{\binom nk})$ oracle calls, each of depth $O(Δ+\log n)$ for maximum degree $Δ$. The guarantee holds for two or more estimation registers; exact simulations on $312$ induced subgraphs of two brain networks confirm it and show that the cheaper single-register variant performs nearly as well.

arXiv:2308.16827•Aug 31, 2023•1 citation

Quantum Computing for Graph Partitioning with Optimal Speedup

Jincheng Zhang

Graph partitioning is a fundamental problem in computer science with applications in diverse fields like network design, compiler optimization, and data analysis. Traditional algorithms for graph partitioning often suffer from computational complexity, particularly when dealing with large graphs. This paper explores the potential of utilizing quantum computing to accelerate graph partitioning. Specifically, we investigate the application of Grover's algorithm, a quantum search algorithm, to the problem. Our core claim is that by leveraging the superposition and interference capabilities inherent in quantum mechanics, a quantum solution can achieve a provable speedup compared to classical approaches. We present a theoretical framework outlining the algorithm's operation and derive the expected speedup. The key mathematical formulation involves representing the graph partitioning problem as an unstructured search problem amenable to Grover's algorithm. We define the problem as minimizing the cut size, represented by the objective function: *f(S) = Σi∈S Σj∈Sc d(i, j)* where *S* is a subset of vertices, *Sc* is the complement of *S* in the graph, and *d(i, j)* is the shortest path distance between vertices *i* and *j*. The algorithm then constructs a quantum oracle that maps the problem state to a superposition of all possible partitions. Grover's algorithm is then applied to amplify the amplitude of the solution state, resulting in a high probability of finding an optimal or near-optimal partition. The speedup is directly proportional to the square root of the number of iterations performed by Grover's algorithm, which is influenced by the problem size and the quality of the oracle. We analyze the complexity of the quantum algorithm and compare it to the complexity of the best-known classical algorithms, demonstrating a potential for significant speedup. Further research will focus on optimizing the oracle construction and exploring other quantum algorithms suitable for graph partitioning.

•Sep 5, 2026•0 citations

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 Algorithms of Bio-molecular Solutions for the Clique Problem on a Quantum Computer

Weng-Long Chang, Ren, Ting-Ting, Mang Feng +4 more

In this paper, it is demonstrated that the DNA-based algorithm [Ho et al. 2005] for solving an instance of the clique problem to any a graph G = (V, E) with n vertices and p edges and its complementary graph G1 = (V, E1) with n vertices and m = (((n*(n-1))/2)-p) edges can be implemented by Hadamard gates, NOT gates, CNOT gates, CCNOT gates, Grover's operators, and quantum measurements on a quantum computer. It is also demonstrated that if Grovers algorithm is employed to accomplish the readout step in the DNA-based algorithm, the quantum implementation of the DNA-based algorithm is equivalent to the oracle work (in the language of Grover's algorithm), that is, the target state labeling preceding Grover,s searching steps. It is shown that one oracle work can be completed with O((2 * n) * (n + 1) * (n + 2) / 3) NOT gates, one CNOT gate and O((4 * m) + (((2 * n) * (n + 1) * (n + 14)) / 6)) CCNOT gates. This is to say that for the quantum implementation of the DNA-based algorithm [Ho et al. 2005] a faster labeling of the target state is attained, which also implies a speedy solution to an instance of the clique problem.

arXiv:0905.2028•May 13, 2009•0 citations
In this paper, we use a quantum circuit called the Graph Encoding Operator which, applied to the complement Gˉ\bar GGˉ of any graph GGG, yields an oracle for the maximum clique problem suitable for amplification via Grover's algorithm. Analogously, we devise a Hypergraph Encoding Operator which, when applied to a hypergraph H\mathcal HH, yields an oracle for the minimum hitting set suitable for amplification via Grover's algorithm. Interestingly, the latter oracle provides, when measured, an approximation of the number of hitting sets of the hypergraph, thus solving the dualization problem for positive Boolean functions represented in a positive irredundant disjunctive normal form. We give the full construction of both operators, prove their correctness, analyze their complexity, and provide an implementation on a quantum simulator. We discuss the resulting complexity, contrast them with existing quantum computer algorithms based on Grover search and we will show that our algorithms outperform, to the best of our knowledge, all of the previous algorithms on space computational complexity by requiring only O(N)O(N)O(N) number of qubits with respect to the number of vertices NNN, for representing both graphs and hypergraphs in the encoding operator and, consequently, results in an oracle for both graphs and hypergraphs that uses only O(N)O(N)O(N) qubits even when the hypergraph contains an exponential (on the number of vertices) number of hyperedges.
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.
Abstract The maximum clique problem (MCP) is to find the largest complete subgraph in an undirected graph, that is, the subgraph in which there are edges between every two different vertices. It is an NP-Hard problem with wide applications, including bioinformatics, social networks, data mining, and other fields. This paper proposes an enhanced quantum solution method that introduces a pre-detection phase based on a hybrid heuristic algorithm and a vertex pruning strategy, encoding the prior constraints on clique size into quantum registers as global information. It encodes the prior constraints on clique size into quantum registers as global information. In contrast, state-of-the-art Grover-based methods for n-vertex graphs require O ( n 2 n ) iterations and O ( n ) measurements. By leveraging a global information encoding mechanism, the proposed method compresses the number of iterations to O ( 2 n ) and only needs a constant number of measurements to identify all maximum cliques. We validate algorithmic correctness through simulations on IBM’s Qiskit platform and benchmark qubit/gate efficiency against existing Grover-based MCP solvers.
Quantum algorithms for clique problems are usually analyzed in the query model, where the graph is accessed through an oracle of unit cost. When the oracle must itself be compiled into gates, published kkk-clique circuits have depth quadratic in the number nnn of vertices, and every oracle that counts edges spends at least one non-Clifford gate per edge. We first show that scheduling the commuting edge gates by a proper edge coloring yields adjacency-type oracles, including an exact kkk-clique oracle, whose depth and width are linear in nnn, within a logarithmic factor of a depth--width lower bound. Our central result is a kkk-clique oracle in which the graph enters only through the Clifford gate that prepares a graph state, so that its non-Clifford cost is linear in nnn for every graph. We analyze this oracle exactly: on a candidate vertex set it acts as a reflection whose overlap is −1-1−1 for cliques and, as we prove, at most 5/85/85/8 in modulus otherwise, a tight bound that tends to 1/21/21/2 as the candidate set grows. A two-qubit phase-estimation filter turns the reflection into a one-sided bounded-error phase oracle, and amplitude amplification then finds a kkk-clique with O((nk))O(\sqrt{\binom nk})O((kn​)​) oracle calls, each of depth O(Δ+log⁡n)O(Δ+\log n)O(Δ+logn) for maximum degree ΔΔΔ. The guarantee holds for two or more estimation registers; exact simulations on 312312312 induced subgraphs of two brain networks confirm it and show that the cheaper single-register variant performs nearly as well.
Graph partitioning is a fundamental problem in computer science with applications in diverse fields like network design, compiler optimization, and data analysis. Traditional algorithms for graph partitioning often suffer from computational complexity, particularly when dealing with large graphs. This paper explores the potential of utilizing quantum computing to accelerate graph partitioning. Specifically, we investigate the application of Grover's algorithm, a quantum search algorithm, to the problem. Our core claim is that by leveraging the superposition and interference capabilities inherent in quantum mechanics, a quantum solution can achieve a provable speedup compared to classical approaches. We present a theoretical framework outlining the algorithm's operation and derive the expected speedup. The key mathematical formulation involves representing the graph partitioning problem as an unstructured search problem amenable to Grover's algorithm. We define the problem as minimizing the cut size, represented by the objective function: *f(S) = Σi∈S Σj∈Sc d(i, j)* where *S* is a subset of vertices, *Sc* is the complement of *S* in the graph, and *d(i, j)* is the shortest path distance between vertices *i* and *j*. The algorithm then constructs a quantum oracle that maps the problem state to a superposition of all possible partitions. Grover's algorithm is then applied to amplify the amplitude of the solution state, resulting in a high probability of finding an optimal or near-optimal partition. The speedup is directly proportional to the square root of the number of iterations performed by Grover's algorithm, which is influenced by the problem size and the quality of the oracle. We analyze the complexity of the quantum algorithm and compare it to the complexity of the best-known classical algorithms, demonstrating a potential for significant speedup. Further research will focus on optimizing the oracle construction and exploring other quantum algorithms suitable for graph partitioning.
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.
In this paper, it is demonstrated that the DNA-based algorithm [Ho et al. 2005] for solving an instance of the clique problem to any a graph G = (V, E) with n vertices and p edges and its complementary graph G1 = (V, E1) with n vertices and m = (((n*(n-1))/2)-p) edges can be implemented by Hadamard gates, NOT gates, CNOT gates, CCNOT gates, Grover's operators, and quantum measurements on a quantum computer. It is also demonstrated that if Grovers algorithm is employed to accomplish the readout step in the DNA-based algorithm, the quantum implementation of the DNA-based algorithm is equivalent to the oracle work (in the language of Grover's algorithm), that is, the target state labeling preceding Grover,s searching steps. It is shown that one oracle work can be completed with O((2 * n) * (n + 1) * (n + 2) / 3) NOT gates, one CNOT gate and O((4 * m) + (((2 * n) * (n + 1) * (n + 14)) / 6)) CCNOT gates. This is to say that for the quantum implementation of the DNA-based algorithm [Ho et al. 2005] a faster labeling of the target state is attained, which also implies a speedy solution to an instance of the clique problem.