The Minimum Vertex Cover (MVC) problem is a fundamental NP-hard combinatorial optimization problem with applications in network security, resource allocation, and scheduling. As quantum computing moves toward fault-tolerant operation, developing qubit-efficient algorithms remains a critical challenge. This paper presents three quantum circuit architectures for solving MVC and its weighted variant using Grover's search algorithm: a Dicke-state restricted search that uses Generalized Dicke State Preparation to filter the search space, an arithmetic-based binary counter using the Cuccaro comparator for edge validation, and a weighted arithmetic solver supporting heterogeneous vertex weights. Our results demonstrate that while Dicke-state preparation offers the fastest convergence in terms of Grover iterations with minimal qubit overhead when the optimal cover sizek⋆is much smaller than the number of verticesn(i.e.,k⋆≪n), which occurs in graphs with small vertex covers such as star graphs, the arithmetic-based approaches provide superior scaling for dense graphs by reducing edge validation fromO(m)toO(logm)ancilla qubits. The weighted arithmetic solver is the only architecture capable of handling heterogeneous vertex weights. We also introduce Skip-K, a classical optimization shared by all three architectures that exploits measurement outcomes to skip intermediate pivot values, reducing the number of Grover executions fromO(∑iwi)toO(log∣C∣)⊆O(n)in expectation, whereCis the set of feasible covers, and to two executions in the best case. We analyze the trade-offs between qubit requirements and circuit depth across all three architectures, providing a roadmap for implementing these solvers on fault-tolerant quantum hardware.
We propose new quantum circuit designs for the Grover oracle, i.e., the oracle of Grover’s algorithm, to solve the vertex cover problem (VCP) efficiently. Grover’s algorithm is an unstructured quantum search algorithm to search a target data item out of N data pieces by calling the oracle O(N) times. It represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires O(N) oracle calls. We are in the noisy intermediate-scale quantum (NISQ) era in which quantum computers have a limited number of qubits, short decoherence time, and low gate fidelity. It is thus desirable to design quantum circuits with three properties: (1) a reduced number of qubits, (2) shorter quantum depth, and (3) fewer gates. We created novel designs of a quantum counter and a quantum semaphore to be applied to the Grover oracle to have the three properties. Through the IBM Quantum Lab service, we executed Grover’s algorithm with the novel quantum circuit designs to solve the VCP to validate the design correctness.