In this paper
AbstractIntroductionPreliminariesWorked example: graph encoding and phase estimationGraph encoding circuitPhase estimationBuilding the clique oracleCorrectness and complexityComplexityNumerical verificationScaling up: to on QiskitThe MHSP and the dualization of Boolean functionsOracle constructionDualization of positive Boolean functionsComplexityDiscussion and related workRelated workComparison with existing circuit-model algorithmsConclusionAcknowledgmentsReferencesWorksPhysics and Astronomy
A Grover-Amplified Oracle for Maximum Clique on Graph, Minimum Hitting set and Dualizations on Hypergraphs Built on Quantum Phase Estimation
Abstract
In this paper, we use a quantum circuit called the Graph Encoding Operator which, applied to the complement of any graph , 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 , 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 number of qubits with respect to the number of vertices , for representing both graphs and hypergraphs in the encoding operator and, consequently, results in an oracle for both graphs and hypergraphs that uses only qubits even when the hypergraph contains an exponential (on the number of vertices) number of hyperedges.
Introduction
Finding a maximum clique in a graph — the largest subset of pairwise-adjacent vertices — is one of the classical NP-hard problems [16], and it remains hard to approximate within polynomial complexity in the worst case. Its complementary formulation, the maximum independent set problem, is equally hard since they both are related by the standard duality: is a clique in if and only if is an independent set in the complement graph of . Furthermore the minimum vertex cover problem and its generalization to hypergraphs, that is the minimum hitting set problem, are also very well known classical NP-hard problems [16] strictly related to maximum clique and maximum independent set problems.
The Maximum Clique Problem (MCP) has applications in various scientific and engineering disciplines and it is fundamental in fields such as medicine, computational biology, coding theory, economics, financial market analysis, telecommunications, wireless networks, cryptography, cybersecurity, and physics [25, 28, 2, 9, 20]. Furthermore, its structural connections with other combinatorial optimization problems, such as graph coloring and clustering, ensure that advances in solving the MCP translate directly into broader algorithmic breakthroughs. Given its fundamental importance, developing more scalable algorithms for the MCP remains a primary challenge, motivating the exploration of new paradigms in quantum computing.
Quantum approaches to clique-related problems have been proposed using both the gate-based quantum computing and quantum-annealing / QUBO paradigms. This paper will use the Graph Encoding Operator (GEO) of our companion paper [26] — originally designed as a graph isomorphism invariant — to develop a Grover oracle. Such an operator computes the number of edges of the subgraph induced by an arbitrary vertex subset ; a clique is exactly a subset inducing the empty graph in , so the very same circuit run on instead of on and left uncollapsed, already tells us — coherently, in superposition — which subsets are cliques.
By employing a modification of the GEO we were able to devise a Hypergraph Encoding Operator (HEO) capable of counting the number of hyperedges covered, that is, that have a non empty intersection to an arbitrary subset of vertices thus, giving the information on which subset of vertices represent a hitting set, since a hitting set covers all the hyperedges of the graph. As in the graph counterpart this operator could be employed as Grover oracle. Interestingly, both the oracles based on GEO and HEO require only qubits where and are, respectively the number of vertices and the number of (hyper)edges of the (hyper)graph. Therefore, in the case of a graph where the number of edges belongs to , the number of qubits required belongs to . To the best of our knowledge [21] this compares favorably to all existing Grover based quantum algorithms for the clique problem which the best computational space complexity belongs to qubits. Thus our proposal decreases dramatically the space requirements for solving the maximum clique problem using Grover iteration with respect to the existing algorithms which belongs to . Furthermore, to the best of our knowledge, the HEO is the first quantum based oracle suitable for Grover iteration in order to solve the minimum hitting set problem in hypergraphs and, even when the number of hyperedges is exponential in the number of vertices, that is, when , our oracle requires qubits. Moreover, much interestingly, the single HEO can, when measured, approximate the number of hitting sets of the hypergraph; and in turn, finding the number of hitting set of the hypergraph directly solves the problem of dualization of positive boolean function represented by a positive irredundant disjunctive normal form [23].
The paper is organized in the following way. In Section 2, we give some preliminaries and recall the description of the GEO from [26]. In Section 3, we describe the maximum clique/independent set oracle, prove its correctness, describe the space and gate complexities and check the numerical results from our implementation of a full Grover algorithm. In Section 4, we describe the HEO, prove its correctness, analyze the space and gates complexities and show how to obtain an approximation on the number of hitting set of a hypergraph for solving the dualization problem of positive Boolean function. In addition to this, the Quiskit code is provided to build the GEO and HEO oracles. In Section 5, we discuss about related works and compare their space and time computational complexities with our approach. Finally, in the Conclusion section we give some concluding remarks and point at possible future works.
Preliminaries
A graph is a pair where is a set of vertices and is a set of subsets of having exactly two vertices. We often denote an edge as . We will denote and, without loss of generality, we identify the set . A graph is said to be complete if for every pair of distinct vertices we have that . A graph the complement of a graph if and . If is a graph and , the subgraph of induced by is the graph denoted as where and . A clique of is a subset such that is a complete graph. An independent set of is a subset of such that . A vertex cover of is a subset such that for all . The size of a maximum clique in a graph is called the clique number of and is denoted by . The Maximum Clique Problem (MCP) asks to find a clique of maximum size in a graph. The Maximum Independent Set Problem (MISP) asks to find an independent set of maximum size in a graph. The Minimum Vertex Cover Problem (MVCP) asks to find a vertex cover of minimum size in a graph. The decision variant of the MCP (resp. MISP) asks, given an integer , whether there exists a clique (resp. an independent set) in a graph such that . For the MVCP, the decision counterpart asks given an integer , whether there exists a vertex cover in the graph such that .
A hypergraph is a generalization of a graph, where is a set of vertices and is a set of non-empty subsets of called hyperedges. The hypergraphs we will deal with have the property that so giving the set of hyperedges will implicitly define the vertex set, and consequently we identify with its set of hyperedges. Given a then denotes the set of hyperedges containing , that is . Given , we denote by the set . We say that covers . If then is a hitting set of . Note that if is a vertex of then . The problem of finding a minimum hitting set of a hypergraph (MHSP) is NP-hard by restriction to the MVCP in graphs [16]. Its decision counterpart asks, given a natural number , whether there exists a hitting set in such that .
We will also make use of the following notation. We will consider , satisfying , sometimes as a number and sometimes as its -bit binary representation; with we will denote the subset of whose characteristic vector is . For example, if and then .
We recall the definitions and the central theorem from [26] that this paper builds on. We will build our oracles by using the (multi-controlled) phase gate :
Lemma 1. We have that and .
Definition 1 (cf. Def. 4.3 of [26]). Let be a graph and . For , let be the operator applying the phase gate on qubit , controlled by qubit , acting as the identity elsewhere. We define
as the Graph Encoding Operator (GEO) of .
Lemma 2 (cf. Lemma 4.2 of [26]). If is a vector of the computational basis whose binary representation is then
and thus any computational basis state is an eigenvector of .
From Lemma 2 we immediately derive the following Lemma:
Lemma 3 (cf. Proposition 4.4 of [26]). Any computational basis state is an eigenvector of with the corresponding eigenvalue .
From these observations we recall the following theorem.
Theorem 1 (Theorem 4.5 of [26]). Let be the quantum phase estimation circuit built from having one register of qubits for the of , a phase register of qubits for the phase estimation and . Then
In other words, Theorem 1 states that, for every such that , i.e., for every , the phase estimation register ends up in the basis state encoding , the number of edges of the subgraph of induced by . Note that if is not a power of two we can save one qubit in the phase estimation register, that is, we can use qubits.
Now, is an independent set of a graph if and only if and therefore, we can leverage the phase register to build a Grover oracle: all we need is a circuit that tells us whether for some fixed integer . We will see that this can be done using additional qubits. Clearly if is an independent set of cardinality greater than or equal then is a vertex cover of cardinality less than or equal to . Furthermore, if we search for an independent set of cardinality greater than or equal in the complement graph of we effectively have got an oracle for the decision version of the MCP of .
Worked example: graph encoding and phase estimation
Throughout this section we illustrate every construction on a single running example. As we mentioned before, the method always involves two related graphs: the target graph , whose maximum clique we seek, and its complement , the one actually encoded into the circuit (a subset is a clique of if and only if it induces no edges of ). For this example, we use the graph with the following edge set (see Figure 1):

Figure 1. A graph isomorphic to its complement.
In this instance, its complement happens to be isomorphic to itself, so a single drawing suffices for both. Consequently, in the example that follows, we can reverse their roles—treating as the original graph and as its complement—while continuing to base our analysis on .
Graph encoding circuit
Figure 2 shows the GEO of the graph of Figure 1, following the convention of [26]: each column corresponds to an edge , with , and contains a phase gate applied to qubit and controlled by qubit .

Figure 2. The GEO for the worked example.
Phase estimation
Feeding the GEO into the phase-estimation construction of Theorem 1 would require estimation qubits; however since is not a power of 2 by the remark following Theorem 1 we can use . Therefore, we set the value . Since , if we denote then the controlled powers of needed by the estimation qubits register are simply , , , where , and denote the same five-edge pattern of Figure 2, repeated with the standard gates , , and in place of . Figure 3 shows the full block.
If we fed to the instead of a single eigenvector a superposition of all eigenvectors and were the three meters of Figure 3 actually to be read out, the resulting probability distribution over would be exactly the quantum spectrum of in the sense of [26]: the phase register reads with probability , where is the number of subgraphs of , with , having edges (Definition 3.2 of [26]). For our worked example, exhaustively classifying all subsets of gives the spectrum of Table 1.
As an oracle, however, the phase register in Figure 3 is never actually measured because doing so would collapse the superposition over and destroy the very interference Grover amplification relies on.

Figure 3. Internal structure of the block for the worked example ( estimation qubits, ). Qubit holds the least significant bit of the estimated phase. The final measurements are shown only to discuss the quantum spectrum (Table 1); they are not part of the oracle.
Building the clique oracle
We are now in position to build the Grover oracle. As we did in the earlier worked example, and to simplify the discussion, we swap the roles of the graphs: we treat as the original graph and as its complement, while keeping as the basis of our analysis. For those state vectors of the GEO register for which in the phase register all qubits are zero then we know that is an independent set of which, in turns, corresponds to a clique of . All it remains to do is to check that is greater or equal than . This can be done by using a new register, called weight register, containing qubits. The weight register is pre-loaded with the value of represented in two’s complement. Then a set of circuits controlled by the qubits of the GEO register are added to the circuit. In this way the most significant qubit (MSB) of the weight register will be if and only if the state vector of the GEO register satisfies . Each controlled block is a completely standard reversible ripple-carry incrementer, built from a cascade of multi-controlled NOT gates of decreasing arity (Figure 5).

Figure 5. Elementary decomposition of one controlled block from Figure 4 (control , target weight register): a sort of ripple-carry increment built from a (multi)-controlled NOT gate.
Now we are able to complete our oracle. In what follows, we will describe only the computational part of the oracle circuit, leaving it to the reader to derive the corresponding uncomputation phase—which simply requires reversing the sequence of gates—necessary to ensure the correctness of Grover’s iteration.
We have the phase register, the GEO register, the weight register and the flag. The complete circuit is reported in Figure 6. The phase register ends up to contain the phase of the eigenvector of the GEO register, that is as stated in Theorem 1, it contains . If and the MSB of the weight register are zero then we get the phase flip required in the Grover iteration.

Figure 6. The complete detailed construction of the oracle where .

Figure 4. The circuitry we use to check if the state vector of the GEO register satisfies . We use one controlled increment per GEO qubit, all acting on the same qubits of the weight register pre-loaded with in two’s complement. The MSB is zero if and only if $\lvert S(x)\rvert-k \ge 0
Correctness and complexity
With reference to the schematic circuit of Figure 7 now we review the behavior of the circuit. After the block the state of the circuit is, by Theorem 1, the following:

Figure 7. Schematic circuit of the oracle of Figure 6.
then, after the weight block, we obtain that is
at this point if is an independent set of –and thus a clique of – of cardinality at least , we have that and that is, the MSB of the weight register is zero. By using this information we can realize the phase flip. In fact if
we have that is
that is, we obtained the phase flip required for the Grover’s oracle.
Complexity
Recall that we denote and . As seen in the previous section the GEO register uses qubits, the phase register qubits and the weight register uses qubits. Therefore, since we have qubits in total.
As for the exponentiation of the GEO in the circuit we have the following. We note that the matrix expansion of the GEO is a diagonal matrix whose elements are either or for some . Then the matrix is a diagonal matrix whose element are . Therefore we have that either or . This means that . In other words, for , we need the exact same circuit as , but with a phase angle of .
A single call to (forward or inverse) invokes the GEO a total of times (Section 4.3 of [26]) and each GEO contains controlled phase gates; the weight circuit costs reversible additions each of which contains multi-controlled gate. The require gates. Hence each oracle call costs elementary gates, and the full Grover search costs
gates in the worst case, i.e. the usual quadratic speed-up over the classical exhaustive search — Max-Clique remains NP-hard, and no super-polynomial speed-up is claimed or expected. As in [26], we emphasize that this is a gate-count analysis and does not include the (separately hard) engineering cost of implementing the required phase-gate precision on real hardware.
Numerical verification
We verified the oracle construction by implementing the full Grover algorithm and verified it on the worked example of § 2.1, checking every non-ancilla basis state after the complete compute–mark–uncompute sequence.
We used first the graph of Figure 1 which contains exactly one clique of cardinality 3. With threshold , the oracle marked exactly this one state out of 32, matching an exhaustive classical check; all 32/32 phases matched the expected pattern and all ancilla registers (weight, estimation) returned exactly to their initial states. Table 2 reports the resulting Grover amplification after a single iteration, compared against the closed-form textbook probability with .
| Metric | Value |
| Probability before amplification | 0.0313 |
| Probability after 1 iteration (simulated) | 0.2583 |
| Probability after 1 iteration (closed form) | 0.2583 |
| Amplification factor |
Table 2. Grover amplification results for the worked example, simulated exactly and cross-checked against the standard closed-form Grover probability formula.
The agreement between the simulated and closed-form probabilities (differing only in the third decimal place, attributable to floating-point rounding) confirms that the compute–mark–uncompute construction behaves as a textbook Grover oracle with no hidden side effects from the uncomputation steps.
Scaling up: to on Qiskit
As a further, fully independent check — using a different simulation engine and shot-based sampling rather than exact linear algebra — we implemented the complete Grover algorithm circuit in Qiskit and ran it on the AerSimulator across six graphs of increasing size, , each with a single, maximum clique. According to what said in the previous sections the simulator acted on the complement of those graphs to find the independent set of size . Table 3 describes each graph and the resulting qubit count and reports the probability of measuring the maximum clique after the theoretically optimal iterations, using a fixed budget of 1024 shots for all .
| Qubits | ||||||
| 5 | 5 | 3 | 12 | 4 | 0.9990 | |
| 6 | 5 | 4 | 13 | 6 | 0.9963 | |
| 7 | 12 | 4 | 15 | 8 | 0.9956 | |
| 8 | 15 | 5 | 16 | 12 | 1.0000 | |
| 9 | 18 | 6 | 19 | 17 | 0.9995 | |
| 10 | 21 | 7 | 20 | 25 | 0.9990 |
Table 3. The six worked graphs. With we denoted the set of edges of the complete graph with vertex set . Column Qubits is the total circuit size (graph + weight + estimation ancilla). is the theoretically optimal number of Grover iterations when there is only one solution to the problem. The column is the probability of measuring the maximum clique, shot-based Qiskit/Aer execution, at the optimal , using 1024 shots per instance. For , values were cross-checked against exact state-vector computation and agreed to within expected sampling noise.
In every one of the six cases the success probability reaches 99.5–100% at , confirming convergence with no sign of degradation as grows.
The MHSP and the dualization of Boolean functions
In this section, we are going to use the tools from the previous section in order to tackle the MHSP in hypergraphs. We will give a quantum circuit which is analogous to the graph encoding operator of [26] and was used in previous Sections.1 This operator, if applied to any computational basis state , gives us a state vector in which the phase of the element encodes the number of hyperedges covered by . The circuit for the HEO will have qubits. Its construction is given by Algorithm 1. Here is its description. At each qubit we add the uncontrolled phase gate . Then we add the multi-controlled phase gates defined as follows.
Definition 2. Let be a hypergraph, , and . Given with , the multi-controlled phase gate called applies to qubit , the phase gate controlled by all qubits when they are in state and by the qubit when it is in state .
As an example, if then is the phase gate applied to controlled by in state , while is the phase gate applied to controlled by and in state and in state (see Figure 8 for an example of and ). Note that is a controlled phase gate applied to qubit controlled by the single qubit .

Figure 8. Two examples of multi-controlled phase gate with : left , right .
Now, for every hyperedge such that , , for every with and for every such that we add the multi-controlled phase gate to the circuit.
Algorithm 1 Quantum Circuit Construction for Hyperedge covering Encode
Require: Hypergraph , phase angle parameter
Ensure: Quantum circuit acting on qubits
Initialize an empty quantum circuit with qubits ▷ Step 1: Apply uncontrolled phase gates to each qubit
for each qubit do
▷ Number of hyperedges incident to
Apply to qubit in circuit
end for
▷ Step 2: Apply multi-controlled phase gates for hyperedges of size
for each hyperedge with do
Order the vertices in as
for to do
for each target qubit do
▷ Apply gate to qubit :
Apply to target qubit , controlled by:
Qubits in state
Qubit in state
end for
end for
end for
return Circuit
Example 1. Let where , , , and (see Figure 9 for a bipartite representation of ). We use with in order to avoid negative angles in the phase, so that in this example . Then , , , and . So the algorithm will add a phase gate to each qubit with an angle (see Figure 10). Next, we add the multi-controlled phase gate in which . In this example, there are 3 multi-controlled phase gates involving more than 2 qubits.

Figure 9. The hypergraph of Example 1, represented as a bipartite graph. The top row is the vertex set, and in the bottom row there are the hyperedges.

Figure 10. The circuit encoding the hypergraph of Example 1, in which .
Lemma 4. Let be a hypergraph and , . If is a computational basis state then
if and only if
and for all , and
otherwise.
Proof. Let be the binary expansion of . By definition, applies the phase gate to qubit if and only if qubits and . Now, by contradiction, if then and the phase gate is not triggered. If, on other hand, but there exists a such that then and the gate will not be triggered. This proves point (1). As for the point (2), if since by definition then we should have that , that is, . But by Lemma 1, the phase gate applied to a qubit in state has no effect.
Lemma 5. Let be a hypergraph and , . If is a computational basis state such that then there are exactly multi-controlled gates that will be triggered by .
Proof. Let that satisfies point (1) of Lemma 4. Then, by point (2) of Lemma 4, for each the multi-controlled gate will be triggered. Thus the Lemma follows.
Theorem 2. Let be a hypergraph and be HEO in output to Algorithm 1. If is any computational basis vector then and .
Proof. Denote by the binary expansion of . To determine the phase , we sum the contributions from Step 1 and Step 2 of the algorithm. In Step 1, every qubit is acted upon by an uncontrolled phase gate . By Lemma 1, qubit acquires this phase if and only if (i.e., ). Summing over all vertices in gives:
However, at this point, each hyperedge covered by is counted times in the phase , which implies that a hyperedge is counted more than once if . Now, in Step 2 of the algorithm, consider a hyperedge with , ordered as and consider all the multi-controlled gates generated by Algorithm 1 when the hyperedge is selected at line 6. If , none of these gates is triggered. Otherwise, by Lemma 4 and Lemma 5, there are precisely of such gates that are triggered. If we repeat this for every hyperedge in which , that is for all hyperedges , we have that
So we encode in the phase of the number of hyperedges covered by .
Example 2 (continued from Example 1). Consider the hypergraph of Example 1 and let so that . The unconditional phase gate of Step 1 adds to a phase , which is exactly the number of edges of the bipartite graph of Figure 9. Now only the gates , , , , , , and are triggered. In the end, the total phase of is as all the hyperedges of are covered by .
Since, by definition, a hitting set intersects with all hyperedges of the hypergraph, if for an the number of hyperedges covered by is equal to the number of hyperedges of the hypergraph, then is a hitting set. So if we apply at the end of the HEO circuit a global phase , we have that is a hitting set if and only if (see Figure 11).

Figure 11. Schematic circuit of the HEO. Note that we add at the end of the circuit a global phase . In this way, if we measure the register, we obtain , which is zero if and only if is a hitting set of .
Oracle construction
We can use the HEO and the Quantum Phase Estimation algorithm to obtain, in the phase register, the value of . The oracle’s circuit will use the HEO register in the same way as the GEO is used in the clique oracle (see § 3). Since in the MHSP we want to check whether a subset of vertices is a hitting set of cardinality less than or equal to , we pre-load the weight register with and instead of using a controlled add-one circuit we will use a subtract-one circuit controlled by the qubits of the HEO register. In this way, if then the MSB of the weight register is set to one, thus signalling that the set has cardinality greater than . Finally, using the phase register and MSB of the weight register we can make the phase flip required for the Grover’s oracle. In fact, with reference to Figure 12

Figure 12. Schematic circuit of the MHSP oracle. The only differences with the clique oracle (Figure 7) are that the weight register is pre-loaded with and instead of add one controlled circuit we used the controlled subtract-one circuit.
Then, after the weight block (labeled as ), we obtain that is
At this point, if is a hitting set of of cardinality at most , we have that the MSB of the weight register is zero. Therefore if
we have that is
That is, we obtained the phase flip required for Grover’s oracle.
Dualization of positive Boolean functions
We can also, by measuring the register, estimate the number of hitting sets of a hypergraph, and this is already an interesting result in itself. In fact, in the dualization problem of positive boolean functions (see [23]) represented in a positive irredundant disjunctive normal form (PIDNF), we have that just counting the number of hitting sets of the corresponding hypergraph solves the dualization problem [23]. In fact, by ([23] Lemma 4), a PIDNF having Boolean variables is self-dual if and only if, in the corresponding hypergraph, the number of hitting sets is equal to . We can obtain an approximation of the number of hitting sets of the hypergraph by setting the circuit and giving as input instead of the superposition of all eigenvectors . If we measure the frequencies in the phase register as we did for the corresponding of Figure 3, we can obtain an approximation of the number of hitting sets of by measuring the frequencies of phase when . For the hypergraph of Example 1, we may obtain a table similar to the quantum spectrum of a graph of Table 1. In this case, we measure the number of subsets that cover exactly hyperedges.
| Probability % | ||
| 0 | 37.50 | 12 |
| 1 | 28.13 | 9 |
| 2 | 18.75 | 6 |
| 3 | 6.25 | 2 |
| 4 | 6.25 | 2 |
| 5 | 3.13 | 1 |
Table 1. Quantum spectrum of for the worked example: probability of each outcome of the phase register in Figure 3, and the corresponding raw subgraphs count that is the number of subsets which induced subgraph has exactly edges, following the convention of [26].
| Probability % | #(subsets of ) | |
| 0 | 3.13 | 1 |
| 1 | 0 | 0 |
| 2 | 6.25 | 2 |
| 3 | 12.50 | 4 |
| 4 | 28.13 | 9 |
| 5 | 50.00 | 16 |
Table 4. The probability of each outcome of the phase register for the hypergraph of Figure 9 and the corresponding raw vertex subset count. Since the hypergraph of the example is self-dual, we have that the number of hitting sets, that is, the number of subsets of which cover all the five hyperedges of the hypergraph is exactly .
Complexity
The HEO circuit requires qubits and each hyperedge requires multi-controlled phase gates. Therefore, the total number of gates are . As in the case of clique oracle, the will require additional qubits and the weight register qubits. Thus the complete oracle requires qubits. This means that even if , that is, the hypergraph contains an exponential number of hyperedges, the number of qubits required is . As for the clique oracle, if is the HEO in output from Algorithm 1, the exponentiation can be made by simply using the same algorithm but passing to it the phase parameter , since the matrix expansion of is a diagonal matrix whose elements are of the form for some . Since the oracle for the HEO is called times, the total gate cost of the oracle is which is polynomial in the dimension of the hypergraph.
Discussion and related work
Related work
Quantum approaches to the MCP and its complementary formulations have been studied mainly within two frameworks: adiabatic quantum computing or QUBO formulations (see, e.g., [7, 4, 27, 15]) and gate-based quantum circuits. Within the gate-based model, besides variational algorithms such as QAOA and VQE [6, 17], continuous-time quantum walks [19, 18], and photonic implementations [32], the main line of research relies on building an explicit oracle circuit and amplifying valid solutions through Grover’s search [11] or quantum minimum-finding routines [10]. A comprehensive overview of both classical and quantum methods for the MCP can be found in the recent survey by Marino et al. [21]. Here we focus our review on gate-based algorithms that construct Grover oracles, before discussing extensions to hypergraphs.
One of the earliest explicit Grover-oracle constructions for the MCP was proposed by Bojić [3], where vertex subsets are encoded in a register of qubits and pairwise adjacency is verified through a cascade of multi-controlled operations. Following a similar paradigm, Chang et al. [5] presented a circuit implementation with a detailed query-complexity analysis, comparing its asymptotic speedup against classical branch-and-bound methods on the decision version of the problem. Later, Metwalli, Le Gall and Van Meter [1] addressed the fixed-size -clique and triangle-finding problems by preparing Dicke states so as to restrict the uniform superposition exclusively to subsets of cardinality , with an experimental evaluation of circuit depth and noise on NISQ devices.
Several subsequent works focused on automating the generation of the oracle circuit and analyzing its exact gate and ancilla requirements. Sanyal et al. [31] developed a framework that constructs, for any input adjacency matrix and target size , an oracle composed of multi-controlled Toffoli (MCT) edge-detector and clique-detector blocks, finding the maximum clique by iteratively decreasing from . A later extension [30] reduced the MCT decomposition overhead by employing higher-dimensional qudits for intermediate steps. Along similar lines, Dias and Zateska [8] and Haverly and López [13, 14] independently formulated Grover oracles for the MCP and derived explicit bounds on the number of qubits and elementary gates required.
A common feature of these algorithms is that, in order to find the clique number from the decision oracle, Grover’s search must be executed repeatedly for different values of the threshold . Depending on whether is scanned linearly or via binary search, this requires or separate runs and measurements. To avoid these restarts, Han, Zheng, Chen and Wang [12] recently proposed a two-stage algorithm in which a classical pre-processing step based on Turán’s theorem bounds the feasible range of , and a dynamic quantum register updates the size of the largest clique found during the quantum search itself. This reduces the overall number of measurements to while maintaining Grover iterations. Nevertheless, like the previous circuit-model approaches, the underlying oracle in [12] still verifies edges explicitly through pairwise MCT gates, which requires qubits in total.
When moving from graphs to hypergraphs, and specifically to the Minimum Hitting Set Problem (MHSP) and the dualization of positive Boolean functions [23], existing quantum approaches have relied almost exclusively on QUBO and higher-order unconstrained binary optimization (HUBO) models for quantum annealers. In that setting, representing hyperedges of cardinality produces higher-order penalty terms that must be reduced to quadratic interactions by introducing auxiliary variables, which rapidly increases the number of physical qubits needed for minor embedding. On the other hand, if one attempts to generalize standard MCT-based gate-model oracles directly to a hypergraph with hyperedges, verifying whether a subset intersects every hyperedge typically requires allocating one ancilla qubit per hyperedge before applying a multi-controlled operation over all flags. While this requires ancilla qubits in general, in the context of positive Boolean function dualization the number of hyperedges can be exponential in the number of vertices, i.e., [23], making any oracle that scales linearly with in space unfeasible.
Comparison with existing circuit-model algorithms
In contrast to prior MCP circuits that allocate dedicated ancilla qubits to check pairwise vertex adjacency, the approach presented in this work builds the Grover oracle from the GEO introduced in [26]. By running the phase estimation circuit on the complement graph , the number of edges induced by each subset is accumulated directly in the phase of the computational basis state and read out coherently into the phase register, while the cardinality condition is verified using a two’s-complement weight register without additional comparator ancillas. The same principle extends to hypergraphs through the HEO of Algorithm 1, where the overcounting of hyperedges intersecting in multiple vertices is canceled directly in phase before applying .
In Table 5 we summarize the computational complexity of our GEO and HEO oracles alongside existing Grover-based algorithms for the MCP, using the evaluation metrics of [12].
Table 5. Comparison with existing Grover-based circuit constructions for the MCP and extension to the MHSP on hypergraphs (figures for the first five rows as reported in [12]; † figures for finding the optimum or minimum hitting set size via binary search over ). Here , is the number of edges in the complement graph , is the number of hyperedges, and denotes the number of valid solutions for threshold .
The main difference in Table 5 lies in the space complexity. All previous gate-model constructions for the MCP require qubits due to the ancilla registers needed to store intermediate edge checks. By contrast, our GEO oracle requires qubits for the vertex register, qubits for the phase register, qubits for the weight register, and one flag qubit, yielding a total of qubits. For hypergraphs, since the phase register only needs to represent values up to , the HEO oracle requires qubits. As noted in § 4, this implies that even when the hypergraph has an exponential number of hyperedges, , the total number of qubits remains bounded by , avoiding the exponential space blow-up of ancilla-per-hyperedge encodings.
This reduction in qubit count is traded against circuit depth and phase-gate operations. However, as shown in § 3.1.1, because the matrix representations of both and are diagonal in the computational basis, the controlled powers and required by Quantum Phase Estimation do not need to repeat the base circuit times; each power is implemented by the exact same circuit with a rescaled phase angle . Consequently, a single call to the oracle invokes the encoding operator only times, resulting in gates for the MCP and gates for the MHSP. Notice also that for the MCP the gate cost depends on , the number of edges of the complement graph, rather than being fixed at . In practice, empirical studies on classical exact solvers (such as CliSAT [29]) indicate that the hardest benchmark instances for maximum clique typically occur at high graph densities of 80% to 95% [22, 21]. In this dense regime for , the complement is sparse (), which is precisely when the GEO circuit requires the fewest controlled-phase gates.
Regarding the number of measurements needed to solve the optimization version of the problem, using a classical binary search over the threshold requires executions of the algorithm. This improves upon the sequential restarts of [5, 13, 31], matching the binary-search strategy of [8], although it requires more measurements than the dynamic-register approach of Han et al. [12]. Combining the dynamic threshold register of [12] with our -qubit QPE core is a natural direction for further improvement.
Finally, as pointed out in § 3.1.1 and in [26], relying on Quantum Phase Estimation introduces a hardware precision requirement that must be taken into account. Distinguishing edges or hyperedges exactly requires a base rotation angle . In the case of graphs, since , the smallest phase angle scales inverse-polynomially as , which falls within standard fault-tolerant gate-synthesis regimes. In the case of hypergraphs with an exponential number of hyperedges (), the angle scales as and hyperedges of size require -controlled phase gates. In that regime, our construction effectively shifts the exponential complexity from the number of qubits to the precision of the phase rotations and circuit depth.
Conclusion
In this paper, we have shown how the GEO, originally introduced as a quantum phase estimation invariant for graph isomorphism [26], can be used to build an ancilla-efficient Grover oracle for the Maximum Clique Problem, and generalized into a HEO to address the MHSP and the dualization of positive Boolean functions. By counting induced edges (or covered hyperedges) in the phase of the basis states and checking vertex subset cardinalities through a two’s-complement weight register, both constructions avoid the need for explicit edge or hyperedge ancilla registers.
For graphs of vertices, the resulting MCP oracle requires qubits, reducing the space complexity of existing gate-model Grover algorithms to linear while requiring gates per oracle call. Our numerical experiments in Qiskit on graphs from to confirm that the compute–mark–uncompute sequence amplifies the target clique states as predicted by the theoretical bounds. For hypergraphs with vertices and hyperedges, the HEO uses inclusion–exclusion phase cancellation to count covered hyperedges in superposition, yielding an MHSP oracle that requires qubits. This remains even when the hypergraph has an exponential number of hyperedges, . Moreover, measuring the phase register of under a uniform superposition provides an approximation of the total number of hitting sets, which directly addresses the dualization problem for positive Boolean functions in PIDNF [23].
Several lines of future work follow naturally from these results. First, it would be interesting to integrate the dynamic threshold register of Han et al. [12] with the GEO and HEO circuits so as to reduce the number of measurements for finding the optimum from to while keeping the qubit bound. Second, the phase-encoding mechanism can be extended to vertex-weighted and hyperedge-weighted variants of both problems by encoding integer weights into the phase angles [24]. Finally, combining the readout of the phase register with Quantum Amplitude Estimation (QAE) could provide a quadratic speed-up in estimating the number of hitting sets for positive Boolean function dualization.
Acknowledgments
This publication continues work supported by the I+D+i grant PID2021-122215NB-C32 (MICI-U/AEI/10.13039/501100011033 and ERDF/EU), the UCLM group research grant 2022-GRIN34113 (co-financed with ERDF Funds), the Region of Madrid project FORTE-CM (S2018/TCS-4314, co-funded by EIE/EU), and QSIMOV Quantum Computing S.L. (project 220426UCTR).
References
- [1]Sara Ayman Metwalli, François Le Gall, and Rodney Van Meter. Finding small and large \(k\)-clique instances on a quantum computer. IEEE Transactions on Quantum Engineering, 1:1–11, 2020.DOI
- [2]Vladimir Boginski, Sergiy Butenko, and Panos M Pardalos. Statistical analysis of financial networks. Computational statistics & data analysis, 48(2):431–443, 2005.DOI
- [3]Ana Bojić. Quantum algorithm for finding a maximum clique in an undirected graph. Journal of Information and Organizational Sciences, 36:91–98, 2012.
- [4]Cristian S. Calude, Michael J. Dinneen, and Richard Hua. Qubo formulations for the graph isomorphism problem and related problems. Theoretical Computer Science, 701:54–69, 2017.DOI
- [5]Weng-Long Chang, Qi Yu, Zhaokai Li, Jian Chen, Xinhua Peng, and Mang Feng. Quantum speedup in solving the maximal-clique problem. Physical Review A, 97:032344, 2018.DOI
- [6]Turbasu Chatterjee, Shah Ishmam Mohtasim, and Akash Kundu. On the variational perspectives to the graph isomorphism problem. 11 2021.
- [7]Andrew M. Childs, Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. Finding cliques by quantum adiabatic evolution, 2000. arXiv:quant-ph/0012104.DOI
- [8]Matheus Giovanni Dias and Leyza Baldo Zateska. Grover’s quantum algorithm and the maximum clique problem. In Proceedings of the 2021 Workshop de Pesquisa em Computação dos Campos Gerais (WPCCG), pages 45–52, Ponta Grossa, Brazil, 2021. UTFPR.
- [9]Ahmed Douik, Hayssam Dahrouj, Tareq Y Al-Naffouri, and Mohamed-Slim Alouini. A tutorial on clique problems in communications and signal processing. Proceedings of the IEEE, 108(4):583–608, 2020.arxiv.org/abs/1808.07102
- [10]Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum. arXiv preprint quant-ph/9607014, 1996.arxiv.org/abs/quant-ph/9607014
- [11]Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC ’96), pages 212–219. ACM, 1996.arxiv.org/abs/quant-ph/9605043
- [12]Wenmin Han, Shiqi Zheng, Peian Chen, and Yukun Wang. Efficient maximum clique detection via grover’s algorithm with real-time global size tracking, 2025. arXiv:2509.01261.arxiv.org/abs/2509.01261
- [13]Andrew Haverly and Sonia López. Implementation of grover’s algorithm to solve the maximum clique problem. In 2021 IEEE Computer Society Annual Symposium on VLSI (ISVLSI), pages 441–446. IEEE, 2021.DOI
- [14]Andrew R. Haverly. A comparison of quantum algorithms for the maximum clique problem. Master’s thesis, Rochester Institute of Technology, 2021. Thesis, comparing qubit gate-model and boson-sampling implementations.
- [15]Richard Hua and Michael J. Dinneen. Improved qubo formulation of the graph isomorphism problem. SN Computer Science, 1(19), 2020.DOI
- [16]Richard M. Karp. Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA, 1972.
- [17]A. Krpan, Janez Povh, and D. Pucher. Quantum computing and the stable set problem. Optimization Methods and Software, 40:837–870, 2025.
- [18]Xiaoyu Li, X. Chen, S. Hu, J. Xu, and Zhihao Liu. A parameter-independent algorithm of finding maximum clique with Seidel continuous-time quantum walks. iScience, 27:108953, 2024.DOI
- [19]Xiaoyu Li, Meng Wu, Hanwu Chen, and Zhihao Liu. Algorithm for finding the maximum clique based on continuous time quantum walk. Quantum Information and Computation, 21:59–79, 2021.
- [20]Yajun Lu, Zhuqi Miao, Parisa Sahraeian, and Balabhaskar Balasundaram. On atomic cliques in temporal graphs: Y. Iu et al. Optimization Letters, 17(4):813–828, 2023.
- [21]Raffaele Marino, Lorenzo Buffoni, and Bogdan Zavalnij. A short review on the maximum clique problem algorithms with classical, ai, and quantum methods. Communications Physics, 9(1):239, jul 2026.DOI
- [22]Ciaran McCreesh, William Pettersson, and Patrick Prosser. Understanding the empirical hardness of random optimisation problems. In Principles and Practice of Constraint Programming (CP 2019), pages 333–349. Springer, 2019.DOI
- [23]Mauro Mezzini, Fernando Cuartero Gomez, Jose Javier Paulet Gonzalez, Hernan Indibil de la Cruz Calvo, Vicente Pascual, and Fernando L. Pelayo. Polynomial quantum computing algorithms for solving the dualization problem for positive boolean functions. Quantum Machine Intelligence, 6(2):71, oct 2024.DOI
- [24]P. W. Mills, R. P. Rundle, J. H. Samson, Simon J. Devitt, Todd Tilma, V. M. Dwyer, and Mark J. Everitt. Quantum invariants and the graph isomorphism problem. Phys. Rev. A, 100:052317, 2019.DOI
- [25]Yasuharu Okamoto. Finding a maximum common subgraph from molecular structural formulas through the maximum clique approach combined with the ising model. ACS omega, 5(22):13064, 2020.DOI
- [26]Fernando L. Pelayo, Vicente Pascual Fidalgo, Hernan I. de la Cruz Calvo, Luis F. Llana Diaz, Jose J. Paulet Gonzalez, Mauro Mezzini, and Fernando Cuartero Gomez. Towards graph isomorphism characterisation through quantum phase estimation. ACM Transactions on Quantum Computing, 2024. Under review; companion paper.
- [27]Elijah Pelofske, Georg Hahn, and Hristo N. Djidjev. Solving large maximum clique problems on a quantum annealer. In Quantum Technology and Optimization Problems (QTOP 2019), volume 11413 of Lecture Notes in Computer Science, pages 123–135. Springer, 2019.
- [28]Kati Rozman, An Ghysels, Bogdan Zavalnij, Tanja Kunej, Urban Bren, Dušanka Janežič, and Janez Konc. Enhanced molecular docking: Novel algorithm for identifying highest weight k-cliques in weighted general and protein-ligand graphs. Journal of molecular structure, 1304:137639, 2024.
- [29]Pablo San Segundo, Fabio Furini, David Álvarez, and Panos M. Pardalos. CliSAT: A new exact algorithm for hard maximum clique problems. European Journal of Operational Research, 307:1008–1025, 2023.DOI
- [30]Arpita Sanyal (Bhaduri), Amit Saha, Banani Saha, and Amlan Chakrabarti. Robust quantum circuit for clique problem with intermediate qudits, 2022. arXiv:2211.07947; published in Procedia Computer Science (2023).
- [31]Arpita Sanyal (Bhaduri), Amit Saha, Debasri Saha, Banani Saha, and Amlan Chakrabarti. Circuit design for clique problem and its implementation on quantum computer. IET Quantum Communication, 3(1):30–49, 2022. Preprint: arXiv:2004.10596.
- [32]Xiao-Feng Yin et al. Solving independent set problems with photonic quantum circuits. Proceedings of the National Academy of Sciences (PNAS), 120:e2212323120, 2023.