Quantum oracles count edges to find cliques and hitting sets

Turning graph structure into a phase

A graph has vertices and pairwise edges. A clique is a set of vertices with every possible pair connected. The authors check this indirectly: a set is a clique in a graph precisely when it contains no edge of that graph's complement, the graph containing the pairs that were absent originally. Their Graph Encoding Operator (GEO) applies controlled phase gates along graph edges. For a chosen vertex subset, the resulting phase tracks the number of edges among the selected vertices. Quantum phase estimation transfers that count into an auxiliary register while retaining the subset in superposition.

The oracle also needs a size threshold. A reversible counter adds one for each selected vertex to a two's-complement register initialized with the negative threshold. The circuit marks a subset only when its complement-graph edge count is zero and its size reaches the threshold. Reversing the computation clears the auxiliary registers, leaving the phase mark Grover search needs. Repeating this test across thresholds can locate the maximum clique.

Extending the count to hypergraphs

A hypergraph edge, or hyperedge, can contain more than two vertices. A hitting set intersects every hyperedge. The authors' Hypergraph Encoding Operator (HEO) assigns each selected vertex a phase contribution based on its incident hyperedges, then uses multi-controlled phase gates to correct repeated counts when several selected vertices lie in one hyperedge. The net phase represents how many hyperedges the subset covers. Phase estimation can therefore test whether all hyperedges are covered; a reversible subtractor checks whether the subset size is at most a chosen limit.

The HEO has another proposed use. When phase estimation is applied to an equal superposition of vertex subsets and the phase register is measured, its outcomes encode covered-hyperedge counts. The authors show how the probability of the outcome for complete coverage can estimate the number of hitting sets. They connect that count to dualization of positive Boolean functions in positive irredundant disjunctive normal form: in the condition cited in the paper, self-duality corresponds to exactly half of all vertex subsets being hitting sets. This is an algorithmic proposal, not a reported practical solution to large dualization instances.

Fewer qubits, not a practical speedup guarantee

The main resource claim concerns space. For a graph with N vertices, the proposed clique oracle uses N vertex qubits plus registers whose sizes grow logarithmically with the edge count and N, giving O(N) qubits because a graph has at most quadratically many edges. For a hypergraph with M hyperedges, the stated bound is O(N + log M); even if M grows exponentially in N, that expression is O(N). This avoids storing a separate qubit flag for every edge or hyperedge.

That space bound does not mean the computation is efficient overall. The paper's gate analysis gives a worst-case Grover search on the order of 2^(N/2) oracle iterations, each requiring substantial circuit work. For the HEO, the construction uses O(MN^2) gates before the additional phase-estimation and search costs. The authors also note that their gate counts do not include the engineering cost of realizing the required phase precision on hardware. Maximum clique remains NP-hard; Grover's quadratic reduction in search effort is not a polynomial-time solution.

Evidence is limited to circuit constructions, proofs, and simulator checks. The reported clique examples include a five-vertex graph with one size-three solution, where one Grover iteration raised the simulated success probability from 0.0313 to 0.2583, and shot-based Qiskit/Aer runs on six examples with five to ten vertices. Those small simulated instances do not establish performance on larger instances or real devices. The paper's hitting-set examples are also worked constructions; it does not report a hardware demonstration. The paper is posted as an arXiv preprint, and the record identifies version 1 as submitted on 2026-11-07.