betaFeedback

WorksPhysics 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 Gˉ\bar G of any graph GG, 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 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)O(N) number of qubits with respect to the number of vertices NN, 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) qubits even when the hypergraph contains an exponential (on the number of vertices) number of hyperedges.

Introduction

Finding a maximum clique in a graph G=(V,E)G=(V,E) — 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: SS is a clique in GG if and only if SS is an independent set in the complement graph Gˉ\bar{G} of GG. 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 SS; a clique is exactly a subset inducing the empty graph in G‾\overline{G}, so the very same circuit run on G‾\overline{G} instead of on GG 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 N+⌈log⁡2M⌉+⌈log⁡2N⌉+3N + \lceil\log_2 M\rceil+ \lceil\log_2 N\rceil+ 3 qubits where NN and MM 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 O(N2)O(N^2), the number of qubits required belongs to O(N)O(N). 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 O(M)O(M) 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 Ω(N2)\Omega(N^2). 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 MM of hyperedges is exponential in the number of vertices, that is, when M∈O(2N)M \in O(2^N), our oracle requires O(N+log⁡22N)=O(N)O(N + \log_2 2^N) = O(N) 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 G=(V(G),E(G))G = (V(G), E(G)) where V(G)V(G) is a set of vertices and E(G)E(G) is a set of subsets of V(G)V(G) having exactly two vertices. We often denote an edge {u,v}\{u,v\} as uvuv. We will denote N=∣V(G)∣N = |V(G)| and, without loss of generality, we identify the set V(G)={0,1,…,N−1}V(G) = \{0,1,\ldots,N - 1\}. A graph GG is said to be complete if for every pair of distinct vertices u,v∈V(G)u,v \in V(G) we have that uv∈E(G)uv \in E(G). A graph G‾\overline{G} the complement of a graph GG if V(G‾)=V(G)V(\overline{G}) = V(G) and E(G‾)={uv∣u,v∈V(G)∧uv∉E(G)∧u≠v}E(\overline{G}) = \{uv|u,v \in V(G) \land uv \notin E(G) \land u \ne v\}. If GG is a graph and S⊆V(G)S \subseteq V(G), the subgraph of GG induced by SS is the graph denoted as GSG_S where V(GS)=SV(G_S) = S and E(GS)={uv∈E(G)∣u∈S∧v∈S}E(G_S) = \{uv \in E(G)|u \in S \land v \in S\}. A clique of GG is a subset S⊆V(G)S \subseteq V(G) such that GSG_S is a complete graph. An independent set SS of GG is a subset of V(G)V(G) such that E(GS)=∅E(G_S) = \emptyset. A vertex cover of GG is a subset S⊆V(G)S \subseteq V(G) such that S∩{u,v}≠∅S \cap\{u,v\} \ne\emptyset for all uv∈E(G)uv \in E(G). The size of a maximum clique in a graph GG is called the clique number of GG and is denoted by ω(G)\omega(G). 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 kk, whether there exists a clique (resp. an independent set) SS in a graph such that ∣S∣≥k|S| \ge k. For the MVCP, the decision counterpart asks given an integer kk, whether there exists a vertex cover SS in the graph such that ∣S∣≤k|S| \le k.

A hypergraph H=(V(H),E(H))\mathcal{H} = (V(\mathcal{H}), E(\mathcal{H})) is a generalization of a graph, where V(H)V(\mathcal{H}) is a set of vertices and E(H)E(\mathcal{H}) is a set of non-empty subsets of V(H)V(\mathcal{H}) called hyperedges. The hypergraphs we will deal with have the property that V(H)=⋃E∈E(H)EV(\mathcal{H}) = \bigcup_{\mathcal{E} \in E(\mathcal{H})} \mathcal{E} so giving the set of hyperedges will implicitly define the vertex set, and consequently we identify H\mathcal{H} with its set of hyperedges. Given a v∈V(H)v \in V(\mathcal{H}) then NH(v)N_{\mathcal{H}}(v) denotes the set of hyperedges containing vv, that is NH(v)={E∈E(H)∣v∈E}N_{\mathcal{H}}(v) = \{\mathcal{E} \in E(\mathcal{H})|v \in\mathcal{E}\}. Given S⊆V(H)S \subseteq V(\mathcal{H}), we denote by ESE_S the set ES={E∈E(H)∣E∩S≠∅}E_S = \{\mathcal{E} \in E(\mathcal{H})|\mathcal{E} \cap S \ne\emptyset\}. We say that SS covers ESE_S. If ES=E(H)E_S = E(\mathcal{H}) then SS is a hitting set of H\mathcal{H}. Note that if vv is a vertex of H\mathcal{H} then E{v}=NH(v)E_{\{v\}} = N_{\mathcal{H}}(v). The problem of finding a minimum hitting set of a hypergraph H\mathcal{H} (MHSP) is NP-hard by restriction to the MVCP in graphs [16]. Its decision counterpart asks, given a natural number kk, whether there exists a hitting set SS in H\mathcal{H} such that ∣S∣≤k|S| \le k.

We will also make use of the following notation. We will consider xx, satisfying 0≤x<2N0 \le x < 2^N, sometimes as a number and sometimes as its NN-bit binary representation; with S(x)S(x) we will denote the subset of {0,1,…,N−1}\{0,1,\ldots,N-1\} whose characteristic vector is xx. For example, if N=5N = 5 and x=13=(0,1,1,0,1)x = 13 = (0,1,1,0,1) then S(x)={1,2,4}S(x) = \{1,2,4\}.

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 P(θ)P(\theta):

P(θ)=[100eiθ](1)P(\theta) = \begin{bmatrix} 1 & 0 \\ 0 & e^{i\theta} \end{bmatrix} \tag*{(1)}

Lemma 1. We have that P(θ)∣0⟩=∣0⟩P(\theta)|0\rangle= |0\rangle and P(θ)∣1⟩=eiθ∣1⟩P(\theta)|1\rangle= e^{i\theta}|1\rangle.

Definition 1 (cf. Def. 4.3 of [26]). Let GG be a graph and θ∈(0,2π]\theta\in(0,2\pi]. For uv∈E(G)uv \in E(G), let AuvθA_{uv}^{\theta} be the operator applying the phase gate P(θ)P(\theta) on qubit uu, controlled by qubit vv, acting as the identity elsewhere. We define

UGθ=∏uv∈E(G)AuvθU_G^\theta= \prod_{uv \in E(G)} A_{uv}^{\theta}

as the Graph Encoding Operator (GEO) of GG.

Lemma 2 (cf. Lemma 4.2 of [26]). If ∣x⟩|x\rangle is a vector of the computational basis whose binary representation is ∣x⟩=∣x0x1...xN−1⟩|x\rangle= |x_0x_1...x_{N-1}\rangle then

Auvθ∣x⟩={eiθ∣x⟩if xu=xv=1∣x⟩otherwiseA_{uv}^{\theta}|x\rangle= \begin{cases} e^{i\theta}|x\rangle& \text{if } x_u = x_v = 1 \\ |x\rangle& \text{otherwise} \end{cases}

and thus any computational basis state ∣x⟩|x\rangle is an eigenvector of AuvθA_{uv}^{\theta}.

From Lemma 2 we immediately derive the following Lemma:

Lemma 3 (cf. Proposition 4.4 of [26]). Any computational basis state ∣x⟩|x\rangle is an eigenvector of UGGU^\mathit{G}_G with the corresponding eigenvalue eiθ∣E(GS(x))∣e^{i\theta|E(G_{S(x)})|}.

From these observations we recall the following theorem.

Theorem 1 (Theorem 4.5 of [26]). Let QPEGQPE_G be the quantum phase estimation circuit built from UGGU^\mathit{G}_G having one register of NN qubits for the GEOGEO of GG, a phase register of m=⌈log⁡2∣E(G)∣⌉+1m=\lceil\log_2|E(G)|\rceil+1 qubits for the phase estimation and θ=2π/2m\theta=2\pi/2^m. Then

QPEG(∣0⟩⊗m⊗∣x⟩)=∣E(GS(x))⟩⊗∣x⟩QPE_G\left(|0\rangle^{\otimes m}\otimes|x\rangle\right)=|E(G_{S(x)})\rangle\otimes|x\rangle

In other words, Theorem 1 states that, for every xx such that 0≤x<2N0\leq x<2^N, i.e., for every S(x)⊆V(G)S(x)\subseteq V(G), the phase estimation register ends up in the basis state encoding ∣E(GS(x))∣|E(G_{S(x)})|, the number of edges of the subgraph of GG induced by S(x)S(x). Note that if ∣E(G)∣|E(G)| is not a power of two we can save one qubit in the phase estimation register, that is, we can use m=⌈log⁡2∣E(G)∣⌉m=\lceil\log_2|E(G)|\rceil qubits.

Now, SS is an independent set of a graph GG if and only if ∣E(GS)∣=0|E(G_S)|=0 and therefore, we can leverage the phase register to build a Grover oracle: all we need is a circuit that tells us whether ∣S∣≥k|S|\geq k for some fixed integer kk. We will see that this can be done using ⌈log⁡2N⌉+1\lceil\log_2 N\rceil+1 additional qubits. Clearly if SS is an independent set of cardinality greater than or equal kk then V(G)∖SV(G)\setminus S is a vertex cover of cardinality less than or equal to N−kN-k. Furthermore, if we search for an independent set of cardinality greater than or equal kk in the complement graph G‾\overline{G} of GG we effectively have got an oracle for the decision version of the MCP of GG.

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 GG, whose maximum clique we seek, and its complement G‾\overline{G}, the one actually encoded into the circuit (a subset S⊆V(G)S\subseteq V(G) is a clique of GG if and only if it induces no edges of G‾\overline{G}). For this example, we use the graph with the following edge set (see Figure 1):

A graph G isomorphic to its complement

Figure 1. A graph GG isomorphic to its complement.

E(G)={{0,1},{1,2},{1,3},{2,3},{3,4}}E(G)=\{\{0,1\},\{1,2\},\{1,3\},\{2,3\},\{3,4\}\}

In this instance, its complement G‾\overline{G} happens to be isomorphic to GG itself, so a single drawing suffices for both. Consequently, in the example that follows, we can reverse their roles—treating G‾\overline{G} as the original graph and GG as its complement—while continuing to base our analysis on GG.

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 uvuv, with u<vu < v, and contains a phase gate P(θ)P(\theta) applied to qubit uu and controlled by qubit vv.

Graph encoding circuit showing phase gates $P(\theta)$ on qubits $q_0$ through $q_4$

Figure 2. The GEO UGθU_{G}^{\theta} for the worked example.

Phase estimation

Feeding the GEO into the phase-estimation construction of Theorem 1 would require m=⌈log⁡2∣E(G)∣⌉+1=4m = \lceil\log_{2} |E(G)| \rceil+ 1 = 4 estimation qubits; however since ∣E(G)∣=5|E(G)| = 5 is not a power of 2 by the remark following Theorem 1 we can use m=⌈log⁡2∣E(G)∣⌉=3m = \lceil\log_{2} |E(G)| \rceil= 3. Therefore, we set the value θ=2π/23=π/4\theta= 2\pi/2^{3} = \pi/4. Since P(θ)k=P(kθ)P(\theta)^{k} = P(k\theta), if we denote B=UGθB = U_{G}^{\theta} then the controlled powers of BB needed by the estimation qubits register are simply B20=BTB^{2^{0}} = B_{T}, B21=BSB^{2^{1}} = B_{S}, B22=BZB^{2^{2}} = B_{Z}, where BTB_{T}, BSB_{S} and BZB_{Z} denote the same five-edge pattern of Figure 2, repeated with the standard gates TT, SS, and ZZ in place of P(θ)P(\theta). Figure 3 shows the full block.

If we fed to the QPEGQPE_{G} instead of a single eigenvector ∣x⟩|x\rangle a superposition of all eigenvectors 2−N/2∑x=02N−1∣x⟩2^{-N/2}\sum_{x=0}^{2^{N}-1}|x\rangle and were the three meters of Figure 3 actually to be read out, the resulting probability distribution over e1e2e3e_{1}e_{2}e_{3} would be exactly the quantum spectrum of GG in the sense of [26]: the phase register reads ∣E(GS)∣∈{0,…,5}|E(G_S)| \in\{0,\ldots,5\} with probability 2−NTG[∣E(GS)∣]2^{-N}T_G[|E(G_S)|], where TG[∣E(GS)∣]T_G[|E(G_S)|] is the number of subgraphs GSG_S of GG, with S⊆V(G)S \subseteq V(G), having ∣E(GS)∣|E(G_S)| edges (Definition 3.2 of [26]). For our worked example, exhaustively classifying all 25=322^5 = 32 subsets of V(G)V(G) 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 SS and destroy the very interference Grover amplification relies on.

Quantum phase estimation block with controlled gates $B_T$, $B_S$, and $B_Z$, inverse quantum Fourier transform, and measurements

Figure 3. Internal structure of the QPEGQPE_{G} block for the worked example (m=3m = 3 estimation qubits, θ=π/4\theta= \pi/4). Qubit e1e_{1} 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 G‾\overline{G} as the original graph and GG as its complement, while keeping GG as the basis of our analysis. For those state vectors ∣x⟩|x\rangle of the GEO register for which in the phase register all qubits are zero then we know that S(x)S(x) is an independent set of GG which, in turns, corresponds to a clique of G‾\overline{G}. All it remains to do is to check that ∣S(x)∣|S(x)| is greater or equal than kk. This can be done by using a new register, called weight register, containing n=⌈log⁡2(N)⌉+1n = \lceil\log_2(N) \rceil+ 1 qubits. The weight register is pre-loaded with the value of ∣−k⟩|-k\rangle represented in two’s complement. Then a set of +1+1 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 ∣0⟩|0\rangle if and only if the state vector ∣x⟩|x\rangle of the GEO register satisfies ∣S(x)∣−k≥0|S(x)| - k \ge0. Each controlled +1+1 block is a completely standard reversible ripple-carry incrementer, built from a cascade of multi-controlled NOT gates of decreasing arity (Figure 5).

Elementary decomposition of one controlled $+1$ block, with control $q_i$ and target weight register, built from a multi-controlled NOT gate

Figure 5. Elementary decomposition of one controlled +1+1 block from Figure 4 (control qiq_i, 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 ∣x⟩|x\rangle of the GEO register, that is as stated in Theorem 1, it contains ∣E(GS(x))∣|E(G_{S(x)})|. If ∣E(GS(x))∣|E(G_{S(x)})| and the MSB of the weight register are zero then we get the phase flip required in the Grover iteration.

Complete detailed construction of the oracle

Figure 6. The complete detailed construction of the oracle where B=UGθB = U_{G}^{\theta}.

Circuitry for checking whether the state vector $\lvert x\rangle$ of the GEO register satisfies $\lvert S(x)\rvert-k \ge 0$; GEO register $\lvert x\rangle$, weight register pre-loaded with $\lvert-k\rangle$, controlled $+1$ blocks, and MSB

Figure 4. The circuitry we use to check if the state vector ∣x⟩\lvert x\rangle of the GEO register satisfies ∣S(x)∣−k≥0\lvert S(x)\rvert-k \ge0. We use one controlled increment per GEO qubit, all acting on the same qubits of the weight register pre-loaded with −k-k 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 QPEGQPE_G block the state of the circuit is, by Theorem 1, the following:

Schematic circuit of the oracle of Figure 6

Figure 7. Schematic circuit of the oracle of Figure 6.

∣φ1⟩=∣E(GS(x))∣⊗∣x⟩⊗∣−k⟩⊗∣−⟩(2)\lvert\varphi_1 \rangle= \lvert E(G_{S(x)}) \rvert\otimes\lvert x \rangle\otimes\lvert-k \rangle\otimes\lvert- \rangle \tag*{(2)}

then, after the weight block, we obtain that ∣φ2⟩\lvert\varphi_2 \rangle is

∣φ2⟩=∣E(GS(x))∣⊗∣x⟩⊗∣∣S(x)∣−k⟩⊗∣−⟩(3)\lvert\varphi_2 \rangle= \lvert E(G_{S(x)}) \rvert\otimes\lvert x \rangle\otimes\lvert\lvert S(x) \rvert- k \rangle\otimes\lvert- \rangle \tag*{(3)}

at this point if S(x)S(x) is an independent set of GG –and thus a clique of Gˉ\bar{G}– of cardinality at least kk, we have that ∣E(GS(x))∣=0\lvert E(G_{S(x)}) \rvert= 0 and ∣S(x)∣−k≥0\lvert S(x) \rvert- k \ge0 that is, the MSB of the weight register is zero. By using this information we can realize the phase flip. In fact if

f(x)={1if S(x) is a clique of cardinality ∣S(x)∣≥k0otherwisef(x) = \begin{cases} 1 & \text{if } S(x) \text{ is a clique of cardinality } \lvert S(x) \rvert\ge k \\ 0 & \text{otherwise} \end{cases}

we have that ∣φ3⟩\lvert\varphi_3 \rangle is

∣φ3⟩=−1f(x)∣E(GS(x))∣⊗∣x⟩⊗∣∣S(x)∣−k⟩⊗∣−⟩(4)\lvert\varphi_3 \rangle= -1^{f(x)} \lvert E(G_{S(x)}) \rvert\otimes\lvert x \rangle\otimes\lvert\lvert S(x) \rvert- k \rangle\otimes\lvert- \rangle \tag*{(4)}

that is, we obtained the phase flip required for the Grover’s oracle.

Complexity

Recall that we denote N=∣V(G)∣N = \lvert V(G) \rvert and M=∣E(G)∣M = \lvert E(G) \rvert. As seen in the previous section the GEO register uses NN qubits, the phase register ⌈log⁡2M⌉+1\lceil\log_2 M \rceil+ 1 qubits and the weight register uses ⌈log⁡2N⌉+1\lceil\log_2 N \rceil+ 1 qubits. Therefore, since M=O(N2)M = O(N^2) we have O(N+log⁡N+log⁡N2)=O(N)O(N + \log N + \log N^2) = O(N) qubits in total.

As for the exponentiation of the GEO in the QPEGQPE_G circuit we have the following. We note that the matrix expansion of the GEO B=UGθB = U_G^\theta is a diagonal matrix diag⁡(B)=(d1,d2,…,d2N)\operatorname{diag}(B) = (d_1, d_2, \ldots, d_{2^N}) whose elements are either dh=1d_h = 1 or dh=eiaθd_h = e^{ia\theta} for some a≠0a \ne0. Then the matrix BjB^j is a diagonal matrix whose element are diag⁡(Bj)=(d1j,d2j,…,d2Nj)\operatorname{diag}(B^j) = (d_1^j, d_2^j, \ldots, d_{2^N}^j). Therefore we have that either dhj=1d_h^j = 1 or dhj=(eiaθ)j=eia(jθ)d_h^j = (e^{ia\theta})^j = e^{ia(j\theta)}. This means that Bj=UGjθB^j = U_G^{j\theta}. In other words, for BjB^j, we need the exact same circuit as BB, but with a phase angle of jθj\theta.

A single call to QPEGQPE_G (forward or inverse) invokes the GEO a total of O(log⁡2M)O(\log_2 M) times (Section 4.3 of [26]) and each GEO contains O(M)O(M) controlled phase gates; the weight circuit costs O(N)O(N) reversible additions each of which contains log⁡2N+1\log_2 N + 1 multi-controlled XX gate. The QFT†QFT^\dagger require O(m2)=O(log⁡22M)O(m^2) = O(\log_2^2 M) gates. Hence each oracle call costs O(Nlog⁡N+Mlog⁡M)O(N \log N + M \log M) elementary gates, and the full Grover search costs

O(2N/2(Nlog⁡N+Mlog⁡M))O\left(2^{N/2}(N \log N + M \log M)\right)

gates in the worst case, i.e. the usual quadratic speed-up over the O(2N)O(2^N) 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 k=3k = 3, 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 sin⁡2((2⋅1+1)θ)\sin^2((2 \cdot1 + 1)\theta) with θ=arcsin⁡1/32\theta= \arcsin\sqrt{1/32}.

MetricValue
Probability before amplification0.0313
Probability after 1 iteration (simulated)0.2583
Probability after 1 iteration (closed form)0.2583
Amplification factor×8.27\times8.27

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: N=5N = 5 to N=10N = 10 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, N=5,…,10N = 5, \ldots, 10, each with a single, maximum clique. According to what said in the previous sections the simulator acted on the complement G‾\overline{G} of those graphs to find the independent set of size ≥k\ge k. Table 3 describes each graph and the resulting qubit count and reports the probability of measuring the maximum clique after the theoretically optimal rr iterations, using a fixed budget of 1024 shots for all NN.

NNE(G)E(G)∣E(G‾)∣|E(\overline{G})|kkQubitsroptr_{\mathrm{opt}}p(clique)p(\mathrm{clique})
5CQ({0,1,2})∪{{0,3},{2,4}}CQ(\{0,1,2\}) \cup\{\{0,3\},\{2,4\}\}531240.9990
6CQ({0,1,…,3})∪{{0,4},{1,4},{2,5},{3,5}}CQ(\{0,1,\ldots,3\}) \cup\{\{0,4\},\{1,4\},\{2,5\},\{3,5\}\}541360.9963
7CQ({0,1,…,3})∪{{0,4},{1,5},{2,6}}CQ(\{0,1,\ldots,3\}) \cup\{\{0,4\},\{1,5\},\{2,6\}\}1241580.9956
8CQ({0,1,…,4})∪{{0,5},{1,6},{2,7}}CQ(\{0,1,\ldots,4\}) \cup\{\{0,5\},\{1,6\},\{2,7\}\}15516121.0000
9CQ({0,1,…,5})∪{{0,6},{1,7},{2,8}}CQ(\{0,1,\ldots,5\}) \cup\{\{0,6\},\{1,7\},\{2,8\}\}18619170.9995
10CQ({0,1,…,6})∪{{0,7},{1,8},{2,9}}CQ(\{0,1,\ldots,6\}) \cup\{\{0,7\},\{1,8\},\{2,9\}\}21720250.9990

Table 3. The six worked graphs. With CQ(S)CQ(S) we denoted the set of edges of the complete graph with vertex set SS. Column Qubits is the total circuit size (graph + weight + estimation ancilla). ropt=⌊π42N⌋r_{\mathrm{opt}} = \left\lfloor\frac{\pi}{4}\sqrt{2^N}\right\rfloor is the theoretically optimal number of Grover iterations when there is only one solution to the problem. The column p(clique)p(\mathrm{clique}) is the probability of measuring the maximum clique, shot-based Qiskit/Aer execution, at the optimal roptr_{\mathrm{opt}}, using 1024 shots per instance. For N=5,6N = 5,6, 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 roptr_{\mathrm{opt}}, confirming convergence with no sign of degradation as NN 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 ∣x⟩|x\rangle, gives us a state vector ∣ϕ⟩=eiφx∣x⟩|\phi\rangle= e^{i\varphi_x}|x\rangle in which the phase φx\varphi_x of the element ∣x⟩|x\rangle encodes the number of hyperedges covered by S(x)S(x). The circuit for the HEO will have N=∣V(H)∣N = |V(\mathcal{H})| qubits. Its construction is given by Algorithm 1. Here is its description. At each qubit vv we add the uncontrolled phase gate P(∣NH(v)∣θ)P(\lvert\mathcal{N}_H(v)\rvert\theta). Then we add the multi-controlled phase gates defined as follows.

Definition 2. Let H\mathcal{H} be a hypergraph, E∈H\mathcal{E} \in\mathcal{H}, E={v1,v2,…,v∣E∣}\mathcal{E} = \{v_1,v_2,\ldots,v_{|\mathcal{E}|}\} and ∣E∣>1|\mathcal{E}| > 1. Given vj,vh∈Ev_j,v_h \in\mathcal{E} with j<hj < h, the multi-controlled phase gate called Cj,hθ(E)C^\theta_{j,h}(\mathcal{E}) applies to qubit vhv_h, the phase gate P(−θ)P(-\theta) controlled by all qubits v1,…,vj−1v_1,\ldots,v_{j-1} when they are in state ∣0⟩\lvert0\rangle and by the qubit vjv_j when it is in state ∣1⟩\lvert1\rangle.

As an example, if E={0,1,3,5,6}\mathcal{E} = \{0,1,3,5,6\} then C1,hθ(E)C^\theta_{1,h}(\mathcal{E}) is the phase gate P(−θ)P(-\theta) applied to vh∈{1,3,5,6}v_h \in\{1,3,5,6\} controlled by v1v_1 in state ∣1⟩\lvert1\rangle, while C3,hθ(E)C^\theta_{3,h}(\mathcal{E}) is the phase gate P(−θ)P(-\theta) applied to vh∈{5,6}v_h \in\{5,6\} controlled by v1v_1 and v2v_2 in state ∣0⟩\lvert0\rangle and v3v_3 in state ∣1⟩\lvert1\rangle (see Figure 8 for an example of C1,4θ(E)C^\theta_{1,4}(\mathcal{E}) and C3,5θ(E)C^\theta_{3,5}(\mathcal{E})). Note that C1,hθ(E)C^\theta_{1,h}(\mathcal{E}) is a controlled phase gate applied to qubit vhv_h controlled by the single qubit v1v_1.

Two examples of multi-controlled phase gate

Figure 8. Two examples of multi-controlled phase gate Cj,hθ(E)C^\theta_{j,h}(\mathcal{E}) with E={0,1,3,5,6}\mathcal{E} = \{0,1,3,5,6\}: left C1,4θ(E)C^\theta_{1,4}(\mathcal{E}), right C3,5θ(E)C^\theta_{3,5}(\mathcal{E}).

Now, for every hyperedge E∈E(H)\mathcal{E} \in E(\mathcal{H}) such that ∣E∣>1|\mathcal{E}| > 1, E={v1,v2,…,v∣E∣}\mathcal{E} = \{v_1,v_2,\ldots,v_{|\mathcal{E}|}\}, for every vj∈Ev_j \in\mathcal{E} with 1≤j<∣E∣1 \le j < |\mathcal{E}| and for every hh such that j<h≤∣E∣j < h \le|\mathcal{E}| we add the multi-controlled phase gate Cj,hθ(E)C^\theta_{j,h}(\mathcal{E}) to the circuit.

Algorithm 1 Quantum Circuit Construction for Hyperedge covering Encode

Require: Hypergraph H\mathcal{H}, phase angle parameter θ\theta

Ensure: Quantum circuit DD acting on ∣V(H)∣|V(\mathcal{H})| qubits

  1. Initialize an empty quantum circuit DD with ∣V(H)∣|V(\mathcal{H})| qubits ▷ Step 1: Apply uncontrolled phase gates to each qubit

  2. for each qubit v∈V(H)v \in V(\mathcal{H}) do

  3. h←∣NH(v)∣h \leftarrow|N_{\mathcal{H}}(v)| ▷ Number of hyperedges incident to vv

  4. Apply P(hθ)P(h\theta) to qubit vv in circuit DD

  5. end for

▷ Step 2: Apply multi-controlled phase gates for hyperedges of size >1> 1

  1. for each hyperedge E∈E(H)\mathcal{E} \in E(\mathcal{H}) with ∣E∣>1|\mathcal{E}| > 1 do

  2. Order the vertices in E\mathcal{E} as {v1,v2,…,v∣E∣}\{v_1,v_2,\ldots,v_{|\mathcal{E}|}\}

  3. for j←1j \leftarrow1 to ∣E∣−1|\mathcal{E}|-1 do

  4. for each target qubit vh∈{vj+1,…,v∣E∣}v_h \in\{v_{j+1},\ldots,v_{|\mathcal{E}|}\} do

▷ Apply gate Cj,hθ(E)C_{j,h}^{\theta}(\mathcal{E}) to qubit vhv_h:

  1. Apply P(−θ)P(-\theta) to target qubit vhv_h, controlled by:

    • Qubits v1,…,vj−1v_1,\ldots,v_{j-1} in state ∣0⟩|0\rangle

    • Qubit vjv_j in state ∣1⟩|1\rangle

  2. end for

  3. end for

  4. end for

  5. return Circuit DD

Example 1. Let H={E1,E2,E3,E4,E5}\mathcal{H}=\{\mathcal{E}_1,\mathcal{E}_2,\mathcal{E}_3,\mathcal{E}_4,\mathcal{E}_5\} where E1={0,3}\mathcal{E}_1=\{0,3\}, E2={0,4}\mathcal{E}_2=\{0,4\}, E3={1,3,4}\mathcal{E}_3=\{1,3,4\}, E4={0,1,2}\mathcal{E}_4=\{0,1,2\} and E5={2,3,4}\mathcal{E}_5=\{2,3,4\} (see Figure 9 for a bipartite representation of H\mathcal{H}). We use θ=2π/2m\theta=2\pi/2^m with m=4m=4 in order to avoid negative angles in the phase, so that in this example θ=π/8\theta=\pi/8. Then ∣NH(0)∣=3|N_{\mathcal{H}}(0)|=3, ∣NH(1)∣=2|N_{\mathcal{H}}(1)|=2, ∣NH(2)∣=2|N_{\mathcal{H}}(2)|=2, ∣NH(3)∣=3|N_{\mathcal{H}}(3)|=3 and ∣NH(4)∣=3|N_{\mathcal{H}}(4)|=3. So the algorithm will add a phase gate to each qubit vv with an angle θ×∣NH(v)∣\theta\times|N_{\mathcal{H}}(v)| (see Figure 10). Next, we add the multi-controlled phase gate in which δ=−π/8\delta=-\pi/8. In this example, there are 3 multi-controlled phase gates involving more than 2 qubits.

The hypergraph of Example 1, represented as a bipartite graph, with vertex set 0, 1, 2, 3, 4 on the top row and hyperedges 03, 04, 134, 012, 234 on the bottom row

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.

The circuit encoding the hypergraph of Example 1, with qubits $q_0$, $q_1$, $q_2$, $q_3$, and $q_4$, gates $P(3\pi/8)$, $P(\pi/4)$, and $P(\delta)$

Figure 10. The circuit encoding the hypergraph of Example 1, in which δ=−π/8\delta= -\pi/8.

Lemma 4. Let H\mathcal{H} be a hypergraph and E∈H\mathcal{E}\in\mathcal{H}, E={v1,v2,…,v∣E∣}\mathcal{E}=\{v_1,v_2,\ldots,v_{|\mathcal{E}|}\}. If ∣x⟩|x\rangle is a computational basis state then

  • Cj,hθ(E)∣x⟩=e−iθ∣x⟩C_{j,h}^{\theta}(\mathcal{E})|x\rangle=e^{-i\theta}|x\rangle if and only if

    1. vj∈S(x)∩Ev_j\in S(x)\cap\mathcal{E} and for all vz∈S(x)∩Ev_z\in S(x)\cap\mathcal{E}, j≤zj\le z and

    2. vh∈S(x)∩Ev_h\in S(x)\cap\mathcal{E}

  • Cj,hθ(E)∣x⟩=∣x⟩C_{j,h}^{\theta}(\mathcal{E})|x\rangle=|x\rangle otherwise.

Proof. Let ∣x0x1…xN−1⟩|x_0x_1\ldots x_{N-1}\rangle be the binary expansion of ∣x⟩|x\rangle. By definition, Cj,hθ(E)C_{j,h}^{\theta}(\mathcal{E}) applies the phase gate to qubit ∣xvh⟩|x_{v_h}\rangle if and only if qubits ∣xv1⟩=∣xv2⟩=⋯=∣xvj−1⟩=∣0⟩|x_{v_1}\rangle=|x_{v_2}\rangle=\cdots=|x_{v_{j-1}}\rangle=|0\rangle and ∣xvj⟩=∣1⟩|x_{v_j}\rangle=|1\rangle. Now, by contradiction, if vj∉S(x)v_j\notin S(x) then ∣xvj⟩=∣0⟩|x_{v_j}\rangle=|0\rangle and the phase gate is not triggered. If, on other hand, vj∈S(x)v_j\in S(x) but there exists a vz∈S(x)∩Ev_z\in S(x)\cap\mathcal{E} such that z<jz<j then ∣xvz⟩=∣1⟩|x_{v_z}\rangle=|1\rangle and the gate will not be triggered. This proves point (1). As for the point (2), if vh∉S(x)∩Ev_h\notin S(x)\cap\mathcal{E} since by definition vh∈Ev_h\in\mathcal{E} then we should have that vh∉S(x)v_h\notin S(x), that is, ∣xvh⟩=∣0⟩|x_{v_h}\rangle=|0\rangle. But by Lemma 1, the phase gate applied to a qubit in state ∣0⟩|0\rangle has no effect.

Lemma 5. Let H\mathcal{H} be a hypergraph and E∈H\mathcal{E} \in\mathcal{H}, E={v1,v2,…,v∣E∣}\mathcal{E} = \{v_1,v_2,\ldots,v_{|\mathcal{E}|}\}. If ∣x⟩|x\rangle is a computational basis state such that ∣S(x)∩E∣>1|S(x) \cap\mathcal{E}| > 1 then there are exactly ∣S(x)∩E∣−1|S(x) \cap\mathcal{E}| - 1 multi-controlled gates Cj,hθ(E)C_{j,h}^{\theta}(\mathcal{E}) that will be triggered by ∣x⟩|x\rangle.

Proof. Let vj∈S(x)∩Ev_j \in S(x) \cap\mathcal{E} that satisfies point (1) of Lemma 4. Then, by point (2) of Lemma 4, for each vh∈(S(x)∩E)∖{vj}v_h \in(S(x) \cap\mathcal{E}) \setminus\{v_j\} the multi-controlled gate Cj,hθ(E)C_{j,h}^{\theta}(\mathcal{E}) will be triggered. Thus the Lemma follows.

Theorem 2. Let H\mathcal{H} be a hypergraph and DHD_{\mathcal{H}} be HEO in output to Algorithm 1. If ∣x⟩|x\rangle is any computational basis vector then DH∣x⟩=eiφx∣x⟩D_{\mathcal{H}} |x\rangle= e^{i\varphi_x}|x\rangle and φx=∣ES(x)∣θ\varphi_x = |E_{S(x)}|\theta.

Proof. Denote by ∣x0x1…xN−1⟩|x_0x_1\ldots x_{N-1}\rangle the binary expansion of ∣x⟩|x\rangle. To determine the phase φx\varphi_x, we sum the contributions from Step 1 and Step 2 of the algorithm. In Step 1, every qubit v∈V(H)v \in V(\mathcal{H}) is acted upon by an uncontrolled phase gate P(∣NH(v)∣θ)P(|N_{\mathcal{H}}(v)|\theta). By Lemma 1, qubit vv acquires this phase if and only if ∣xv⟩=∣1⟩|x_v\rangle= |1\rangle (i.e., v∈S(x)v \in S(x)). Summing over all vertices in S(x)S(x) gives:

φx′=∑v∈S(x)∣NH(v)∣θ.\varphi'_x = \sum_{v \in S(x)} |N_{\mathcal{H}}(v)|\theta.

However, at this point, each hyperedge E\mathcal{E} covered by S(x)S(x) is counted ∣S(x)∩E∣|S(x) \cap\mathcal{E}| times in the phase φx′\varphi'_x, which implies that a hyperedge is counted more than once if ∣S(x)∩E∣>1|S(x) \cap\mathcal{E}| > 1. Now, in Step 2 of the algorithm, consider a hyperedge E∈E(H)\mathcal{E} \in E(\mathcal{H}) with ∣E∣>1|\mathcal{E}| > 1, ordered as {v1,v2,…,v∣E∣}\{v_1,v_2,\ldots,v_{|\mathcal{E}|}\} and consider all the multi-controlled gates Cj,hθ(E)C_{j,h}^{\theta}(\mathcal{E}) generated by Algorithm 1 when the hyperedge E\mathcal{E} is selected at line 6. If ∣E∩S(x)∣≤1|\mathcal{E} \cap S(x)| \leq1, none of these gates is triggered. Otherwise, by Lemma 4 and Lemma 5, there are precisely ∣S(x)∩E∣−1|S(x) \cap\mathcal{E}| - 1 of such gates that are triggered. If we repeat this for every hyperedge in which S(x)∩E≠∅S(x) \cap\mathcal{E} \neq\varnothing, that is for all hyperedges E∈ES(x)\mathcal{E} \in E_{S(x)}, we have that

φx=φx′−θ∑E∈ES(x)(∣S(x)∩E∣−1)=θ∑E∈ES(x)∣S(x)∩E∣−θ∑E∈ES(x)(∣S(x)∩E∣−1)=∣ES(x)∣θ\begin{aligned} \varphi_x = \varphi'_x - \theta\sum_{\mathcal{E} \in E_{S(x)}} \left(|S(x) \cap\mathcal{E}| - 1\right) \\ &= \theta\sum_{\mathcal{E} \in E_{S(x)}} |S(x) \cap\mathcal{E}| - \theta\sum_{\mathcal{E} \in E_{S(x)}} \left(|S(x) \cap\mathcal{E}| - 1\right) = |E_{S(x)}|\theta \end{aligned}

So we encode in the phase of ∣x⟩|x\rangle the number of hyperedges covered by S(x)S(x).

Example 2 (continued from Example 1). Consider the hypergraph of Example 1 and let ∣x⟩=∣31⟩=∣11111⟩|x\rangle= |31\rangle= |11111\rangle so that S(x)={0,1,2,3,4}S(x) = \{0,1,2,3,4\}. The unconditional phase gate of Step 1 adds to ∣x⟩|x\rangle a phase φx=13θ\varphi_x = 13\theta, which is exactly the number of edges of the bipartite graph of Figure 9. Now only the gates C1,2θ(E1)C_{1,2}^{\theta}(\mathcal{E}_1), C1,2θ(E2)C_{1,2}^{\theta}(\mathcal{E}_2), C1,2θ(E3)C_{1,2}^{\theta}(\mathcal{E}_3), C1,3θ(E3)C_{1,3}^{\theta}(\mathcal{E}_3), C1,2θ(E4)C_{1,2}^{\theta}(\mathcal{E}_4), C1,3θ(E4)C_{1,3}^{\theta}(\mathcal{E}_4), C1,2θ(E5)C_{1,2}^{\theta}(\mathcal{E}_5) and C1,3θ(E5)C_{1,3}^{\theta}(\mathcal{E}_5) are triggered. In the end, the total phase of ∣x⟩|x\rangle is 5θ5\theta as all the hyperedges of H\mathcal{H} are covered by S(x)S(x).

Since, by definition, a hitting set intersects with all hyperedges of the hypergraph, if for an xx the number of hyperedges covered by S(x)S(x) is equal to the number of hyperedges of the hypergraph, then S(x)S(x) is a hitting set. So if we apply at the end of the HEO circuit a global phase e−i∣E(H)∣θe^{-i|E(\mathcal{H})|\theta}, we have that S(x)S(x) is a hitting set if and only if φx=0\varphi_x = 0 (see Figure 11).

Schematic circuit of the HEO

Figure 11. Schematic circuit of the HEO. Note that we add at the end of the circuit a global phase e−i∣E(H)∣θe^{-i|E(\mathcal{H})|\theta}. In this way, if we measure the QPEHQPE_{\mathcal{H}} register, we obtain ∣ES(x)∣−∣E(H)∣|E_{S(x)}|-|E(\mathcal{H})|, which is zero if and only if S(x)S(x) is a hitting set of H\mathcal{H}.

Oracle construction

We can use the HEO and the Quantum Phase Estimation algorithm to obtain, in the phase register, the value of ∣ES(x)∣−∣E(H)∣|E_{S(x)}| - |E(\mathcal{H})|. 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 kk, we pre-load the weight register with ∣k⟩|k\rangle 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 k−∣S(x)∣<0k-|S(x)|<0 then the MSB of the weight register is set to one, thus signalling that the set S(x)S(x) has cardinality greater than kk. 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

Schematic circuit of the MHSP oracle

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 kk and instead of add one controlled circuit we used the controlled subtract-one circuit.

∣φ1⟩=∣∣ES(x)∣−∣E(H)∣⟩⊗∣x⟩⊗∣k⟩⊗∣−⟩(5)|\varphi_1\rangle=||E_{S(x)}|-|E(\mathcal{H})|\rangle\otimes|x\rangle\otimes|k\rangle\otimes|-\rangle \tag*{(5)}

Then, after the weight block (labeled as −∣S(x)∣-|S(x)|), we obtain that ∣φ2⟩|\varphi_2\rangle is

∣φ2⟩=∣∣ES(x)∣−∣E(H)∣⟩⊗∣x⟩⊗∣k−∣S(x)∣⟩⊗∣−⟩(6)|\varphi_2\rangle=||E_{S(x)}|-|E(\mathcal{H})|\rangle\otimes|x\rangle\otimes|k-|S(x)|\rangle\otimes|-\rangle \tag*{(6)}

At this point, if S(x)S(x) is a hitting set of H\mathcal{H} of cardinality at most kk, we have that the MSB of the weight register is zero. Therefore if

f(x)={1if S(x) is a hitting set of cardinality ∣S(x)∣≤k0otherwisef(x)=\begin{cases}1 & \text{if } S(x) \text{ is a hitting set of cardinality } |S(x)|\le k \\ 0 & \text{otherwise}\end{cases}

we have that ∣φ3⟩|\varphi_3\rangle is

∣φ3⟩=−1f(x)∣∣ES(x)∣−∣E(H)∣⟩⊗∣x⟩⊗∣k−∣S(x)∣⟩⊗∣−⟩(7)|\varphi_3\rangle=-1^{f(x)}||E_{S(x)}|-|E(\mathcal{H})|\rangle\otimes|x\rangle\otimes|k-|S(x)|\rangle\otimes|-\rangle \tag*{(7)}

That is, we obtained the phase flip required for Grover’s oracle.

Dualization of positive Boolean functions

We can also, by measuring the QPEHQPE_{\mathcal{H}} 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 NN Boolean variables is self-dual if and only if, in the corresponding hypergraph, the number of hitting sets is equal to 2N−12^{N-1}. We can obtain an approximation of the number of hitting sets of the hypergraph by setting the QPEHQPE_{\mathcal{H}} circuit and giving as input instead of ∣x⟩\lvert x\rangle the superposition of all eigenvectors 2−N/2∑x=02N−1∣x⟩2^{-N/2}\sum_{x=0}^{2^N-1}\lvert x\rangle. If we measure the frequencies in the phase register as we did for the corresponding QPEGQPE_{\mathcal{G}} of Figure 3, we can obtain an approximation of the number of hitting sets of H\mathcal{H} by measuring the frequencies of phase ∣ES(x)∣−∣E(H)∣\lvert E_{S(x)}\rvert-\lvert E(\mathcal{H})\rvert when ∣ES(x)∣−∣E(H)∣=0\lvert E_{S(x)}\rvert-\lvert E(\mathcal{H})\rvert=0. 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 S⊆V(H)S\subseteq V(\mathcal{H}) that cover exactly ∣ES∣\lvert E_S\rvert hyperedges.

∣E(GS)∣|E(G_S)|Probability %TG[∣E(GS)∣]T_G[|E(G_S)|]
037.5012
128.139
218.756
36.252
46.252
53.131

Table 1. Quantum spectrum of GG for the worked example: probability of each outcome of the phase register in Figure 3, and the corresponding raw subgraphs count TG[∣E(GS)∣]T_G[|E(G_S)|] that is the number of subsets S⊆V(G)S \subseteq V(G) which induced subgraph has exactly ∣E(GS)∣|E(G_S)| edges, following the convention of [26].

∣ES(x)∣\lvert E_{S(x)}\rvertProbability %#(subsets of V(H)V(\mathcal{H}))
03.131
100
26.252
312.504
428.139
550.0016

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 V(H)V(\mathcal{H}) which cover all the five hyperedges of the hypergraph is exactly 2N−12^{N-1}.

Complexity

The HEO circuit requires O(N)O(N) qubits and each hyperedge E\mathcal{E} requires O(∣E∣2)=O(N2)O(\lvert\mathcal{E}\rvert^2)=O(N^2) multi-controlled phase gates. Therefore, the total number of gates are O(MN2)O(MN^2). As in the case of clique oracle, the QPEHQPE_{\mathcal{H}} will require O(log⁡M)O(\log M) additional qubits and the weight register O(log⁡N)O(\log N) qubits. Thus the complete oracle requires O(N+log⁡M+log⁡N)O(N+\log M+\log N) qubits. This means that even if M=O(2N)M=O(2^N), that is, the hypergraph contains an exponential number of hyperedges, the number of qubits required is O(N+log⁡2N)=O(N)O(N+\log2^N)=O(N). As for the clique oracle, if DHD_{\mathcal{H}} is the HEO in output from Algorithm 1, the exponentiation DHjD_{\mathcal{H}}^j can be made by simply using the same algorithm but passing to it the phase parameter jθj\theta, since the matrix expansion of DHD_{\mathcal{H}} is a diagonal matrix diag⁡(d1,…,d2N)\operatorname{diag}(d_1,\ldots,d_{2^N}) whose elements are of the form dh=eiaθd_h=e^{ia\theta} for some aa. Since the oracle for the HEO is called log⁡2M\log_2 M times, the total gate cost of the oracle is O(Nlog⁡N+MN2log⁡M)=O(MN2log⁡M)O(N\log N+MN^2\log M)=O(MN^2\log M) 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 NN 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 kk-clique and triangle-finding problems by preparing Dicke states so as to restrict the uniform superposition exclusively to subsets of cardinality kk, 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 kk, an oracle composed of multi-controlled Toffoli (MCT) edge-detector and clique-detector blocks, finding the maximum clique by iteratively decreasing kk from NN. 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 ω(G)\omega(G) from the decision oracle, Grover’s search must be executed repeatedly for different values of the threshold kk. Depending on whether kk is scanned linearly or via binary search, this requires O(N)O(N) or O(log⁡N)O(\log N) 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 ω(G)\omega(G), 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 O(1)O(1) while maintaining O(2N)O(\sqrt{2^N}) Grover iterations. Nevertheless, like the previous circuit-model approaches, the underlying oracle in [12] still verifies edges explicitly through pairwise MCT gates, which requires O(N2)O(N^2) 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 ∣e∣>2|e| > 2 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 H\mathcal{H} with M=∣E(H)∣M = |E(\mathcal{H})| hyperedges, verifying whether a subset S(x)⊆V(H)S(x) \subseteq V(\mathcal{H}) intersects every hyperedge typically requires allocating one ancilla qubit per hyperedge before applying a multi-controlled operation over all MM flags. While this requires O(M)O(M) 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., M∈O(2N)M \in O(2^N) [23], making any oracle that scales linearly with MM 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 QPEGˉQPE_{\bar{G}} on the complement graph Gˉ\bar{G}, the number of edges ∣E(GˉS(x))∣|E(\bar{G}_{S(x)})| induced by each subset S(x)S(x) is accumulated directly in the phase of the computational basis state ∣x⟩|x\rangle and read out coherently into the phase register, while the cardinality condition ∣S(x)∣≥k|S(x)| \ge k 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 S(x)S(x) in multiple vertices is canceled directly in phase before applying QPEHQPE_{\mathcal{H}}.

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].

MethodQubit costOracle gate costGrover iterationsMeasurementsTotal gates
Haverly and López [13]O(N2)O(N^2)O(N2N)O(\sqrt{N}2^N)O(N2N)O(N2^N)O(N)O(N)O(kNN/22N)O(kN^{N/2}2^N)
Sanyal et al. [31]O(N2)O(N^2)O(N2N)O(\sqrt{N}2^N)O(NN2N)O(N\sqrt{N}2^N)O(N)O(N)O(kN2N+Nlog⁡2N)O(k\sqrt{N}2^N+N\log^2N)
Dias and Zateska [8]O(N2)O(N^2)O(N2)O(N^2)O((Nlog⁡2N)22N)O((N\log_2N)^2\sqrt{2^N})O(log⁡2N)O(\log_2N)O(kN2(log⁡2N)22N/2)O(kN^2(\log_2N)^22^{N/2})
Chang et al. [5]O(N2)O(N^2)O(N2)O(N^2)O(N2N)O(N\sqrt{2^N})O(N)O(N)O(kN2N/2)O(kN2^{N/2})
Han et al. [12]O(N2)O(N^2)O(N2)O(N^2)O(2N)O(\sqrt{2^N})O(1)O(1)O(N2N/2+N3/22N)O(N2^{N/2}+N^{3/2}2^N)
This work (GEO – MCP)O(N)O(N)O(∣E(Gˉ)∣log⁡∣E(Gˉ)∣+Nlog⁡N)O(|E(\bar{G})|\log|E(\bar{G})|+N\log N)O(2N/Mk)O(\sqrt{2^N/M_k})O(log⁡N)†O(\log N)^{\dagger}O(log⁡N⋅2N/2(∣E(Gˉ)∣log⁡∣E(Gˉ)∣+Nlog⁡N))†O(\log N\cdot2^{N/2}(|E(\bar{G})|\log|E(\bar{G})|+N\log N))^{\dagger}
This work (HEO – MHSP)O(N+log⁡M)O(N+\log M)O(MN2log⁡M+Nlog⁡N)O(MN^2\log M+N\log N)O(2N/Mk)O(\sqrt{2^N/M_k})O(log⁡N)†O(\log N)^{\dagger}O(log⁡N⋅2N/2(MN2log⁡M+Nlog⁡N))†O(\log N\cdot2^{N/2}(MN^2\log M+N\log N))^{\dagger}

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 ω(G)\omega(G) or minimum hitting set size via binary search over kk). Here N=∣V∣N=|V|, ∣E(Gˉ)∣≤(N2)|E(\bar{G})|\le\binom{N}{2} is the number of edges in the complement graph Gˉ\bar{G}, M=∣E(H)∣≤2NM=|E(\mathcal{H})|\le2^N is the number of hyperedges, and MkM_k denotes the number of valid solutions for threshold kk.

The main difference in Table 5 lies in the space complexity. All previous gate-model constructions for the MCP require O(N2)O(N^2) qubits due to the ancilla registers needed to store intermediate edge checks. By contrast, our GEO oracle requires NN qubits for the vertex register, ⌈log⁡2∣E(Gˉ)∣⌉+1\lceil\log_2|E(\bar{G})|\rceil+1 qubits for the phase register, ⌈log⁡2N⌉+1\lceil\log_2N\rceil+1 qubits for the weight register, and one flag qubit, yielding a total of O(N)O(N) qubits. For hypergraphs, since the phase register only needs to represent values up to M=∣E(H)∣M=|E(\mathcal{H})|, the HEO oracle requires O(N+log⁡M)O(N+\log M) qubits. As noted in § 4, this implies that even when the hypergraph has an exponential number of hyperedges, M∈O(2N)M\in O(2^N), the total number of qubits remains bounded by O(N+log⁡22N)=O(N)O(N+\log_2 2^N)=O(N), 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 UGθU_G^\theta and DHD_{\mathcal{H}} are diagonal in the computational basis, the controlled powers (UGθ)2j(U_G^\theta)^{2^j} and DH2jD_{\mathcal{H}}^{2^j} required by Quantum Phase Estimation do not need to repeat the base circuit 2j2^j times; each power is implemented by the exact same circuit with a rescaled phase angle 2jθ2^j\theta. Consequently, a single call to the oracle invokes the encoding operator only m=O(log⁡M)m=O(\log M) times, resulting in O(∣E(Gˉ)∣log⁡∣E(Gˉ)∣+Nlog⁡N)O(|E(\bar{G})|\log|E(\bar{G})|+N\log N) gates for the MCP and O(MN2log⁡M+Nlog⁡N)O(MN^2\log M+N\log N) gates for the MHSP. Notice also that for the MCP the gate cost depends on ∣E(Gˉ)∣|E(\bar{G})|, the number of edges of the complement graph, rather than being fixed at Θ(N2)\Theta(N^2). 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 GG, the complement Gˉ\bar{G} is sparse (∣E(Gˉ)∣≪(N2)|E(\bar{G})| \ll\binom{N}{2}), 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 k∈{1,…,N}k \in\{1,\ldots,N\} requires O(log⁡N)O(\log N) executions of the algorithm. This improves upon the O(N)O(N) sequential restarts of [5, 13, 31], matching the binary-search strategy of [8], although it requires more measurements than the O(1)O(1) dynamic-register approach of Han et al. [12]. Combining the dynamic threshold register of [12] with our O(N)O(N)-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 MM edges or hyperedges exactly requires a base rotation angle θ=2π/2⌈log⁡2M⌉+1=Θ(1/M)\theta= 2\pi/2^{\lceil\log_2 M\rceil+1} = \Theta(1/M). In the case of graphs, since ∣E(Gˉ)∣≤N(N−1)/2|E(\bar{G})| \le N(N-1)/2, the smallest phase angle scales inverse-polynomially as Ω(1/N2)\Omega(1/N^2), which falls within standard fault-tolerant gate-synthesis regimes. In the case of hypergraphs with an exponential number of hyperedges (M∈O(2N)M \in O(2^N)), the angle θ\theta scales as Ω(2−N)\Omega(2^{-N}) and hyperedges of size Θ(N)\Theta(N) require O(N)O(N)-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 NN vertices, the resulting MCP oracle requires N+⌈log⁡2∣E(Gˉ)∣⌉+⌈log⁡2N⌉+3=O(N)N + \lceil\log_2|E(\bar{G})|\rceil+ \lceil\log_2 N\rceil+ 3 = O(N) qubits, reducing the O(N2)O(N^2) space complexity of existing gate-model Grover algorithms to linear while requiring O(∣E(Gˉ)∣log⁡∣E(Gˉ)∣+Nlog⁡N)O(|E(\bar{G})|\log|E(\bar{G})| + N\log N) gates per oracle call. Our numerical experiments in Qiskit on graphs from N=5N=5 to N=10N=10 confirm that the compute–mark–uncompute sequence amplifies the target clique states as predicted by the theoretical bounds. For hypergraphs with NN vertices and MM hyperedges, the HEO uses inclusion–exclusion phase cancellation to count covered hyperedges in superposition, yielding an MHSP oracle that requires O(N+log⁡M)O(N+\log M) qubits. This remains O(N)O(N) even when the hypergraph has an exponential number of hyperedges, M∈O(2N)M \in O(2^N). Moreover, measuring the phase register of QPEHQPE_H 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 kk from O(log⁡N)O(\log N) to O(1)O(1) while keeping the O(N)O(N) 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 QPEHQPE_H 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. [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. [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. [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. [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. [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. [6]Turbasu Chatterjee, Shah Ishmam Mohtasim, and Akash Kundu. On the variational perspectives to the graph isomorphism problem. 11 2021.
  7. [7]Andrew M. Childs, Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. Finding cliques by quantum adiabatic evolution, 2000. arXiv:quant-ph/0012104.DOI
  8. [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. [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. [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. [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. [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. [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. [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. [15]Richard Hua and Michael J. Dinneen. Improved qubo formulation of the graph isomorphism problem. SN Computer Science, 1(19), 2020.DOI
  16. [16]Richard M. Karp. Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA, 1972.
  17. [17]A. Krpan, Janez Povh, and D. Pucher. Quantum computing and the stable set problem. Optimization Methods and Software, 40:837–870, 2025.
  18. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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.

Paper details

vlnc:W_nkxk5tv4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents