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

arXiv:2610.07252

Resource-Aware Grover Search for Minimum Vertex Cover

Beilei Jiang, Harry Fu, Pavan Krishna Yarlagadda, Alexander Shan, Yunhe Feng, Song Fu

quant-phcs.ETSubmitted Oct 5, 2026• Announced Oct 7, 2026• 0 citations
arXivHTMLPDF

Abstract

The Minimum Vertex Cover (MVC) problem is a fundamental NP-hard combinatorial optimization problem with applications in network analysis and resource allocation. Grover's algorithm provides a quadratic reduction in query complexity for unstructured search, but existing Grover-based MVC formulations can incur substantial quantum resource overhead due to costly vertex-counting circuits and complex oracle constructions. We develop and evaluate several encoding and oracle-design strategies for reducing the qubit count, circuit depth, and gate complexity of Grover-based MVC search. First, we construct a Dicke-Parallel formulation that restricts the search to fixed-cardinality subsets, eliminating explicit vertex counting, together with a parallel edge-verification oracle that reduces feasibility-checking overhead. We then develop an Edge-Counting formulation that replaces per-edge auxiliary storage with a logarithmic-size counting register, substantially reducing ancillary-qubit requirements. Finally, we propose an Edge-Centric encoding that represents endpoint selections directly and derives vertex-selection states through incident-edge Boolean operations, enabling more depth-efficient oracle construction. Our resource analysis reveals complementary trade-offs among qubit width, circuit depth, gate count, and Grover iteration count. Edge-Counting is particularly attractive under tight qubit constraints, while Edge-Centric can reduce both circuit depth and Grover iteration count when the graph has a moderate edge count and sufficient representation multiplicity. Dicke-Parallel provides a more robust choice when such multiplicity is limited or graph density makes the edge-based search space large. These results provide practical guidance for selecting Grover-based MVC formulations according to hardware constraints and graph structure.

Comments
13 pages, 12 figures

Related papers

Reducing circuit resources in Grover’s algorithm via constraint-aware initialization

Eunok Bae, Jeonghyeon Shin, Minjin Choi

Abstract Grover’s search algorithm provides a quadratic speedup over classical brute-force methods for unstructured search problems in terms of query complexity and is widely used as a versatile subroutine in numerous quantum algorithms, including those for combinatorial problems with large search spaces. For such problems, it is natural to reduce the effective search space by incorporating problem constraints at the initialization step, which in Grover’s algorithm can be achieved by preparing structured initial states that encode constraint information. In this work, we present a systematic framework with a simple preprocessing procedure for constraint-aware initialization in Grover’s algorithm, focusing on problems with linear constraints. The proposed framework incorporates cardinality constraints and parity constraints extracted from more general linear constraints. While such structured initial states can reduce the number of oracle queries required to obtain a solution, their preparation incurs additional circuit-level costs. We therefore offer a conservative circuit-level resource analysis, showing that the resulting constraint-aware initialization can improve resource efficiency in terms of gate counts and circuit depth. The proposed framework is further illustrated numerically using the exact-cover problem as a representative application. Overall, our results indicate that this approach serves as a practical baseline for achieving more resource-efficient implementations of Grover’s algorithm compared to the standard uniform initialization.

Scientific Reports•Jul 29, 2026•0 citations

Reducing Circuit Resources in Grover's Algorithm via Constraint-Aware Initialization

Eunok Bae, Jeonghyeon Shin, Minjin Choi

Grover's search algorithm provides a quadratic speedup over classical brute-force search in terms of query complexity and is widely used as a versatile subroutine in numerous quantum algorithms, including those for combinatorial problems with large search spaces. For such problems, it is natural to reduce the effective search space by incorporating problem constraints at the initialization step, which in Grover's algorithm can be achieved by preparing structured initial states that encode constraint information. In this work, we present a systematic framework with a simple preprocessing procedure for constraint-aware initialization in Grover's algorithm, focusing on problems with linear constraints. While such structured initial states can reduce the number of oracle queries required to obtain a solution, their preparation incurs additional circuit-level costs. We therefore offer a conservative circuit-level resource analysis, showing that the resulting constraint-aware initialization can improve resource efficiency in terms of gate counts and circuit depth. The validity of the framework is further demonstrated numerically using the exact-cover problem. Overall, our results indicate that this approach serves as a practical baseline for achieving more resource-efficient implementations of Grover's algorithm compared to the standard uniform initialization.

quant-pharXiv:2601.17725•Jan 27, 2026•0 citations

Explicit Quantum Search Algorithm for the Densest k-Subgraph Problem

Yu. A. Biriukov, R. D. Morozov, I. V. Dyakonov +1 more

This paper addresses the problem of finding the densest $k$-vertex subgraph in an arbitrary graph. This problem is NP-hard and has important applications in social network analysis, fraud detection, recommendation systems, and bioinformatics. We propose two quantum approaches to solve this problem: reduction to Quadratic Unconstrained Binary Optimization (QUBO) and using Grover's quantum search algorithm. For the latter approach, we present an explicit gate-based oracle circuit utilizing Dicke states and Quantum Fourier Transform for edge counting. Numerical simulations demonstrate a quadratic speedup over classical Brute-force search.

quant-pharXiv:2604.27782•May 1, 2026•0 citations

Utilizing Novel Quantum Counters for Grover's Algorithm to Solve the Dominating Set Problem

Jehn‐Ruey Jiang, Qiao-Yi Lin

Grover's algorithm is a well-known unstructured quantum search algorithm run on quantum computers. It constructs an oracle and calls the oracle O($\sqrt N$) times to locate specific data out of N unsorted data. This represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires to call the oracle O(N) times. We are currently 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 components with three good properties: (i) a reduced number of qubits, (ii) shorter quantum depth, and (iii) fewer gates. This paper utilizes novel quantum counters with the above-mentioned three good properties to construct the oracle of Grover's algorithm to efficiently solve the dominating set problem (DSP), as defined below. For a given graph G=(V, E), a dominating set (DS) D is a subset of the vertex set V, such that every vertex is in D or has an adjacent vertex in D. The DSP is to decide for a given graph G and an integer k whether there exists a DS with size k. Algorithms solving the DSP have many applications. For example, they can be applied to check whether k routers suffice to connect all computers in a computer network. The DSP is an NP-complete problem, indicating that no classical algorithm exists to solve the DSP with polynomial time complexity in the worst case. Therefore, using quantum algorithms, such as Grover's algorithm, to exploit the potent computational capabilities of quantum computers to solve the DSP is highly promising. We execute the whole quantum circuit of Grover's algorithm using novel quantum counters through the IBM Quantum Lab service to validate that the circuit can solve the DSP efficiently and correctly.

arXiv:2312.09388•Dec 14, 2023•1 citation

Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem

F. S. Luiz, A. K. F. Iwakami, D. H. Moraes +1 more

We propose a novel heuristic quantum algorithm for the Minimum Vertex Cover (MVC) problem based on continuous-time quantum walks (CTQWs). In this framework, the coherent propagation of a quantum walker over a graph encodes its structural properties into state amplitudes, enabling the identification of highly influential vertices through their transition probabilities. To enhance stability and solution quality, we introduce a dynamic decoupling (``freezing'') mechanism that isolates vertices already selected for the cover, preventing their interference in subsequent iterations of the algorithm. The method employs a compact binary encoding, requiring only $\lceil \log_2 (V)\rceil$ qubits to represent a graph with $V$ vertices, resulting in an exponential reduction of quantum resources compared to conventional vertex-based encodings. We benchmark the proposed heuristic against exact solutions obtained via Mixed-Integer Linear Programming (MILP) and against established classical heuristics, including Simulated Annealing, FastVC, and the 2-Approximation algorithm, across Erdős--Rényi, Barabási--Albert and regular random graph ensembles. Our results demonstrate that the CTQW-based heuristic consistently achieves superior approximation ratios and exhibits remarkable robustness with respect to network topology, outperforming classical approaches in both heterogeneous and homogeneous structures. These findings indicate that continuous-time quantum walks, when combined with topology-independent decoupling strategies, provide a powerful paradigm for large-scale combinatorial optimization and complex network control, with potential applications spanning infrastructure resilience, epidemic containment, sensor network optimization, and biological systems analysis.

quant-pharXiv:2512.02940•Dec 3, 2025•0 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•5 citations
The Minimum Vertex Cover (MVC) problem is a fundamental NP-hard combinatorial optimization problem with applications in network analysis and resource allocation. Grover's algorithm provides a quadratic reduction in query complexity for unstructured search, but existing Grover-based MVC formulations can incur substantial quantum resource overhead due to costly vertex-counting circuits and complex oracle constructions. We develop and evaluate several encoding and oracle-design strategies for reducing the qubit count, circuit depth, and gate complexity of Grover-based MVC search. First, we construct a Dicke-Parallel formulation that restricts the search to fixed-cardinality subsets, eliminating explicit vertex counting, together with a parallel edge-verification oracle that reduces feasibility-checking overhead. We then develop an Edge-Counting formulation that replaces per-edge auxiliary storage with a logarithmic-size counting register, substantially reducing ancillary-qubit requirements. Finally, we propose an Edge-Centric encoding that represents endpoint selections directly and derives vertex-selection states through incident-edge Boolean operations, enabling more depth-efficient oracle construction. Our resource analysis reveals complementary trade-offs among qubit width, circuit depth, gate count, and Grover iteration count. Edge-Counting is particularly attractive under tight qubit constraints, while Edge-Centric can reduce both circuit depth and Grover iteration count when the graph has a moderate edge count and sufficient representation multiplicity. Dicke-Parallel provides a more robust choice when such multiplicity is limited or graph density makes the edge-based search space large. These results provide practical guidance for selecting Grover-based MVC formulations according to hardware constraints and graph structure.
Abstract Grover’s search algorithm provides a quadratic speedup over classical brute-force methods for unstructured search problems in terms of query complexity and is widely used as a versatile subroutine in numerous quantum algorithms, including those for combinatorial problems with large search spaces. For such problems, it is natural to reduce the effective search space by incorporating problem constraints at the initialization step, which in Grover’s algorithm can be achieved by preparing structured initial states that encode constraint information. In this work, we present a systematic framework with a simple preprocessing procedure for constraint-aware initialization in Grover’s algorithm, focusing on problems with linear constraints. The proposed framework incorporates cardinality constraints and parity constraints extracted from more general linear constraints. While such structured initial states can reduce the number of oracle queries required to obtain a solution, their preparation incurs additional circuit-level costs. We therefore offer a conservative circuit-level resource analysis, showing that the resulting constraint-aware initialization can improve resource efficiency in terms of gate counts and circuit depth. The proposed framework is further illustrated numerically using the exact-cover problem as a representative application. Overall, our results indicate that this approach serves as a practical baseline for achieving more resource-efficient implementations of Grover’s algorithm compared to the standard uniform initialization.
Grover's search algorithm provides a quadratic speedup over classical brute-force search in terms of query complexity and is widely used as a versatile subroutine in numerous quantum algorithms, including those for combinatorial problems with large search spaces. For such problems, it is natural to reduce the effective search space by incorporating problem constraints at the initialization step, which in Grover's algorithm can be achieved by preparing structured initial states that encode constraint information. In this work, we present a systematic framework with a simple preprocessing procedure for constraint-aware initialization in Grover's algorithm, focusing on problems with linear constraints. While such structured initial states can reduce the number of oracle queries required to obtain a solution, their preparation incurs additional circuit-level costs. We therefore offer a conservative circuit-level resource analysis, showing that the resulting constraint-aware initialization can improve resource efficiency in terms of gate counts and circuit depth. The validity of the framework is further demonstrated numerically using the exact-cover problem. Overall, our results indicate that this approach serves as a practical baseline for achieving more resource-efficient implementations of Grover's algorithm compared to the standard uniform initialization.
This paper addresses the problem of finding the densest kkk-vertex subgraph in an arbitrary graph. This problem is NP-hard and has important applications in social network analysis, fraud detection, recommendation systems, and bioinformatics. We propose two quantum approaches to solve this problem: reduction to Quadratic Unconstrained Binary Optimization (QUBO) and using Grover's quantum search algorithm. For the latter approach, we present an explicit gate-based oracle circuit utilizing Dicke states and Quantum Fourier Transform for edge counting. Numerical simulations demonstrate a quadratic speedup over classical Brute-force search.
Grover's algorithm is a well-known unstructured quantum search algorithm run on quantum computers. It constructs an oracle and calls the oracle O(N\sqrt NN​) times to locate specific data out of N unsorted data. This represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires to call the oracle O(N) times. We are currently 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 components with three good properties: (i) a reduced number of qubits, (ii) shorter quantum depth, and (iii) fewer gates. This paper utilizes novel quantum counters with the above-mentioned three good properties to construct the oracle of Grover's algorithm to efficiently solve the dominating set problem (DSP), as defined below. For a given graph G=(V, E), a dominating set (DS) D is a subset of the vertex set V, such that every vertex is in D or has an adjacent vertex in D. The DSP is to decide for a given graph G and an integer k whether there exists a DS with size k. Algorithms solving the DSP have many applications. For example, they can be applied to check whether k routers suffice to connect all computers in a computer network. The DSP is an NP-complete problem, indicating that no classical algorithm exists to solve the DSP with polynomial time complexity in the worst case. Therefore, using quantum algorithms, such as Grover's algorithm, to exploit the potent computational capabilities of quantum computers to solve the DSP is highly promising. We execute the whole quantum circuit of Grover's algorithm using novel quantum counters through the IBM Quantum Lab service to validate that the circuit can solve the DSP efficiently and correctly.
We propose a novel heuristic quantum algorithm for the Minimum Vertex Cover (MVC) problem based on continuous-time quantum walks (CTQWs). In this framework, the coherent propagation of a quantum walker over a graph encodes its structural properties into state amplitudes, enabling the identification of highly influential vertices through their transition probabilities. To enhance stability and solution quality, we introduce a dynamic decoupling (``freezing'') mechanism that isolates vertices already selected for the cover, preventing their interference in subsequent iterations of the algorithm. The method employs a compact binary encoding, requiring only ⌈log⁡2(V)⌉\lceil \log_2 (V)\rceil⌈log2​(V)⌉ qubits to represent a graph with VVV vertices, resulting in an exponential reduction of quantum resources compared to conventional vertex-based encodings. We benchmark the proposed heuristic against exact solutions obtained via Mixed-Integer Linear Programming (MILP) and against established classical heuristics, including Simulated Annealing, FastVC, and the 2-Approximation algorithm, across Erdős--Rényi, Barabási--Albert and regular random graph ensembles. Our results demonstrate that the CTQW-based heuristic consistently achieves superior approximation ratios and exhibits remarkable robustness with respect to network topology, outperforming classical approaches in both heterogeneous and homogeneous structures. These findings indicate that continuous-time quantum walks, when combined with topology-independent decoupling strategies, provide a powerful paradigm for large-scale combinatorial optimization and complex network control, with potential applications spanning infrastructure resilience, epidemic containment, sensor network optimization, and biological systems analysis.
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.