Quantum resource efficient Grover search methods improve vertex cover problem
Resource-Aware Grover Search for Minimum Vertex Cover
Emerging Technologies
Summary
Finding the smallest set of nodes that cover all edges in a network is a hard problem for computers. Grover's quantum search algorithm can speed this search but often requires lots of quantum resources, making it expensive. This paper explores new ways to design these quantum searches that use fewer qubits and simpler operations. The authors show trade-offs among different designs, helping to pick the best method depending on hardware limits and network structure.
What this means in practice
- •For quantum hardware engineers: Optimize quantum circuits for minimum vertex cover searches to reduce qubit demand and improve execution efficiency on limited quantum devices.
- •For network analysis teams: Use improved quantum search methods to analyze network structures faster by efficiently solving vertex cover problems on quantum hardware.
Authors
Beilei Jiang, Harry Fu, Pavan Krishna Yarlagadda, Alexander Shan, Yunhe Feng, Song Fu
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.