arXiv:2610.07252
Resource-Aware Grover Search for Minimum Vertex Cover
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.
AI Summary
The paper studies how search encodings and reversible-oracle designs affect the resources required for Grover-based minimum vertex cover (MVC) search. It compares three formulations for finding a cover of a specified size $k$, separating per-iteration circuit costs from amplitude-amplification iteration counts. Dicke-Parallel searches the $\binom{n}{k}$ fixed-weight vertex subsets and computes coverage flags using one ancilla per edge. Edge-Counting uses the same search space but replaces stored edge flags with sequential reversible counting in a $\lceil\log_2(m+1)\rceil$-qubit register. Edge-Centric searches $2^m$ endpoint assignments, each inducing a valid cover, and checks the derived cover’s size using reversible Wallace-tree population counting. Every minimum cover is proved reachable; a cover $C$ has exactly $2^{|E_{\mathrm{in}}(C)|}$ representations. Consequently, its marked-state fraction is $2^{-m}\sum_C2^{|E_{\mathrm{in}}(C)|}$, compared with $M_k/\binom{n}{k}$ for Dicke search, yielding an explicit criterion for fewer Grover iterations. Qiskit logical-resource comparisons use cycle graphs with $n=4$–$14$, dense complete-minus-matching graphs, and an $n=8$ density sweep. Edge-Counting uses the fewest qubits in these benchmarks; Edge-Centric has lower per-iteration depth and gate counts on sparse instances, while Dicke-Parallel leads on dense instances. Correctness is checked by 1,024-shot simulations on representative six-vertex graphs. The evaluation excludes hardware mapping and routing and uses a fixed no-ancilla MCX synthesis. Larger instances receive resource estimates rather than full simulation. The paper emphasizes that per-iteration savings need not translate into total-search savings: Edge-Centric’s iteration count depends on representation multiplicity and its exponentially growing edge-assignment space.
Error found: Dicke-Parallel incorrectly infers simultaneous edge-predicate execution from Boolean independence, although incident-edge circuits share vertex qubits and require scheduling or additional resources. The resource comparisons do not establish complete minimum-finding costs because they assume a target cardinality and iteration count without accounting for their determination. The density-based iteration-count explanation overlooks exact cancellation between internal-edge multiplicity and search-space growth, so increasing the edge count need not worsen Edge-Centric's marked fraction.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 13 pages, 12 figures