Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum Information Processing

Quantum speedup for solving the minimum vertex cover problem based on Grover search algorithm

Zhaocai Wang, Kun Liang, Xiaoguang Bao, Tunhua Wu

Published Jul 1, 2023• 8 citations
Publisher
DOI
10.1007/s11128-023-04010-4

Related papers

An improved quantum-inspired evolutionary algorithm framework implemented to solve minimum vertex cover problem

Sulabh Bansal, Shiladitya Bhattacharjee

Structural and Multidisciplinary Optimization•Jul 1, 2025•3 citations

Applying the quantum approximate optimization algorithm to the minimum vertex cover problem

Yongqiang Zhang, X.D. Mu, Xiaowen Liu +6 more

Applied Soft Computing•Feb 5, 2022•46 citations

Qubit-Efficient Quantum Circuit for the Minimum Vertex Cover Problem Using Grover's Algorithm

Krissada Sarawit, Kamonluk Suksen

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 size$k^\star$is much smaller than the number of vertices$n$(i.e.,$k^\star \ll 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 from$O(m)$to$O(\log m)$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 from$O(\sum _{i} w_{i})$to$O(\log |\mathcal {C}|) \subseteq O(n)$in expectation, where$\mathcal {C}$is 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.

IEEE Transactions on Quantum Engineering•Jan 1, 2026•0 citations

Circuit optimization of Grover quantum search algorithm

Xi Wu, Qingyi Li, Zhiqiang Li +5 more

Quantum Information Processing•Jan 18, 2023•20 citations

Novel Quantum Circuit Designs for the Oracle of Grover’s Algorithm to Solve the Vertex Cover Problem

Jehn‐Ruey Jiang, Wei-Han Yan

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 $\mathrm{O}(\sqrt{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.

IEEE Eurasia Conference on IOT, Communication and Engineering (ECICE)•Oct 27, 2023•6 citations

Using modifications to Grover’s Search algorithm for quantum global optimization

Yipeng Liu, Gary J. Kœhler

European Journal of Operational Research•Jun 17, 2010•25 citations
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⋆k^\stark⋆is much smaller than the number of verticesnnn(i.e.,k⋆≪nk^\star \ll nk⋆≪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)O(m)O(m)toO(log⁡m)O(\log m)O(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)O(\sum _{i} w_{i})O(∑i​wi​)toO(log⁡∣C∣)⊆O(n)O(\log |\mathcal {C}|) \subseteq O(n)O(log∣C∣)⊆O(n)in expectation, whereC\mathcal {C}Cis 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)\mathrm{O}(\sqrt{N})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.