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

Technical Summary: Grover-Amplified Oracles for Maximum Clique and Minimum Hitting Set via Quantum Phase Estimation

Problem Statement
The paper addresses two fundamental NP-hard combinatorial optimization problems: the Maximum Clique Problem (MCP) on graphs and the Minimum Hitting Set Problem (MHSP) on hypergraphs. The MCP seeks the largest subset of pairwise-adjacent vertices in a graph $G$, while the MHSP seeks the smallest subset of vertices that intersects every hyperedge in a hypergraph $H$. These problems are central to fields ranging from computational biology to cybersecurity.

Existing quantum approaches, particularly those based on Grover's algorithm, face significant scalability challenges regarding space complexity. Traditional gate-model oracles for MCP typically require $O(N^2)$ qubits (where $N$ is the number of vertices) to explicitly check pairwise adjacencies or store edge information. For hypergraphs, where the number of hyperedges $M$ can be exponential in $N$ ($M \in O(2^N)$), standard approaches requiring an ancilla qubit per hyperedge become infeasible.

Methodology
The authors propose a novel construction of Grover oracles based on Quantum Phase Estimation (QPE) and two specific encoding operators: the Graph Encoding Operator (GEO) and the Hypergraph Encoding Operator (HEO).

1. Graph Encoding Operator (GEO) for MCP:

   • Instead of checking edges explicitly, the authors utilize the complement graph $\bar{G}$. A subset $S$ is a clique in $G$ if and only if it induces an empty subgraph in $\bar{G}$ (i.e., zero edges).
   • The GEO, originally defined in a companion paper [26] as a graph isomorphism invariant, is applied to $\bar{G}$. It computes the number of edges induced by a vertex subset $S$ and encodes this count into the phase of the computational basis state $|x\rangle$ representing $S$.
   • Oracle Construction:
     • Phase Register: QPE is performed on the GEO to extract the edge count $|E(\bar{G}_S)|$ into a phase register.
     • Weight Register: A separate register, pre-loaded with $-k$ (in two's complement), is used to verify if the subset size $|S| \geq k$. Controlled increment operations update this register based on the bits of $|x\rangle$.
     • Flagging: If the phase register indicates zero edges (meaning $S$ is a clique in $G$) AND the Most Significant Bit (MSB) of the weight register indicates $|S| \geq k$, a phase flip is applied to mark the state for Grover amplification.
   • Space Efficiency: The circuit uses $N$ qubits for the vertex register, $\lceil \log_2 |E(\bar{G})| \rceil + 1$ for the phase register, and $\lceil \log_2 N \rceil + 1$ for the weight register. Since $|E(\bar{G})| \leq N(N-1)/2$, the total qubit count is $O(N)$.

2. Hypergraph Encoding Operator (HEO) for MHSP:

   • The HEO is designed to count the number of hyperedges covered by a subset $S$. A subset is a hitting set if it covers all $M$ hyperedges.
   • Mechanism: The operator uses an inclusion-exclusion principle implemented via phase gates.
     • Step 1: Uncontrolled phase gates add a phase proportional to the degree of each vertex (number of incident hyperedges).
     • Step 2: Multi-controlled phase gates subtract phases for over-counted intersections. Specifically, for a hyperedge $E$, if a subset $S$ intersects $E$ in $k$ vertices, the construction ensures the net phase contribution corresponds to exactly 1 covered hyperedge (rather than $k$).
   • Oracle Construction: Similar to the GEO, QPE is used to extract the count of covered hyperedges. A global phase shift of $-|E(H)|\theta$ is applied so that a hitting set (covering all edges) results in a net phase of 0. A weight register checks if $|S| \leq k$.
   • Space Efficiency: The HEO requires $N$ qubits for vertices and a phase register of size $\lceil \log_2 M \rceil$. Even if $M \in O(2^N)$, the total qubit requirement remains $O(N)$ because $\log(2^N) = N$.

Key Contributions

• Linear Space Complexity: The primary contribution is the reduction of qubit requirements for Grover-based MCP and MHSP oracles from $O(N^2)$ (or $O(M)$ for hypergraphs) to $O(N)$. This is achieved by encoding structural information (edge/hyperedge counts) into the phase of the state rather than using ancilla qubits for explicit storage or checking.
• Scalability for Hypergraphs: The HEO allows the solution of MHSP on hypergraphs with an exponential number of hyperedges ($M \in O(2^N)$) using only linear qubits, a feat not previously achieved by gate-model Grover oracles.
• Dualization of Boolean Functions: The paper demonstrates that measuring the QPE register of the HEO under a uniform superposition allows for the approximation of the number of hitting sets. Since finding the exact number of hitting sets directly solves the dualization problem for positive Boolean functions represented in positive irredundant disjunctive normal form (PIDNF), this capability provides a quantum approach to addressing the dualization problem.
• Gate Complexity Analysis: The authors provide a detailed analysis showing that while the space complexity is linear, the gate complexity per oracle call is $O(|E(\bar{G})| \log |E(\bar{G})| + N \log N)$ for graphs and $O(MN^2 \log M)$ for hypergraphs. They note that for dense graphs $G$, the complement $\bar{G}$ is sparse, making the GEO efficient in practice.

Results and Verification

• Numerical Simulation: The authors implemented the full Grover algorithm using Qiskit and the AerSimulator.
  • Graphs: Tested on graphs with $N=5$ to $N=10$. The simulations confirmed that the "compute-mark-uncompute" sequence correctly amplifies the target clique states, achieving success probabilities of 99.5%–100% at the theoretically optimal number of iterations.
  • Hypergraphs: The HEO construction was verified to correctly encode the number of covered hyperedges, with phase cancellation working as predicted to identify hitting sets.
• Comparison: The paper contrasts its $O(N)$ space complexity with existing algorithms (e.g., Haverly and López, Sanyal et al., Han et al.) which require $O(N^2)$ qubits. The authors note that while their approach trades space for circuit depth and phase precision, it offers a significant advantage in qubit count, which is currently the primary bottleneck for near-term quantum hardware.

Significance and Claims
The paper claims that its proposed algorithms outperform all previous Grover-based quantum algorithms for the Maximum Clique and Minimum Hitting Set problems in terms of space computational complexity.

• By requiring only $O(N)$ qubits, the method makes these problems tractable on quantum simulators and potential future hardware for larger $N$ than previously possible.
• The ability to handle hypergraphs with exponential edges using linear qubits is highlighted as a unique capability, enabling the approximation of the number of hitting sets, which is the key step in solving the dualization problem for positive Boolean functions in a quantum setting.
• The authors modestly acknowledge that the approach relies on high-precision phase rotations (especially for hypergraphs with $M \in O(2^N)$), which shifts the complexity burden from qubit count to gate precision and circuit depth, a trade-off relevant to fault-tolerant quantum computing.

The work does not claim a super-polynomial speedup over classical algorithms (as MCP remains NP-hard), but rather a quadratic speedup over classical exhaustive search via Grover's iteration, achieved with a significantly more efficient resource footprint.