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⋆is much smaller than the number of vertices
n(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 from
O(m)to
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 from
O(∑iwi)to
O(log∣C∣)⊆O(n)in expectation, where
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.
Quantum computing offers an accelerated mechanism for solving combinatorial optimization problems that could be hardly solvable with classical tools, in this context, this paper highlights the utility of quantum computing in solving NP-complete problems efficiently and shows up the importance of employing quantum algorithms achieving parallel calculation in the purpose of reducing the algorithmic complexity and simplifying the development of optimization applications. Within this publication, an optimized version of quantum circuit conception for developing the oracle of the Grover's search algorithm is introduced for solving the vertex cover problem, and it was also tested using the Qiskit library and applied to a set of instances to evaluate its performance.
Abstract Quantum computing is a new mode that follows the laws of quantum mechanics. It performs computational tasks based on the control of quantum units. From the view of computable problems, quantum computers can only solve the problems that traditional computers can solve, but considering the efficiency of computation, due to the existence of quantum superposition, some known quantum algorithms are exponentially faster than traditional general-purpose computers. In this article, we combine quantum computing with a classical neural network to design a quantum Hopfield network. Each neuron is initialized to a specified state and evolved into a steady state. The output result is one of patterns in a training set. We also present an application of this protocol in image recognition. The simulation results show that this network works in the quantum environment and the output images are correct, therefore the feasibility of this protocol is verified.
We investigate and compare the performance of two quantum optimization approaches, the Quantum Approximate Optimization Algorithm (QAOA) and quantum annealing, applied to the Minimum Vertex Cover ( MVC ) problem. The problem is encoded as an Ising Hamiltonian, and experiments are conducted on the ibm_kingston gate-based quantum machine, accessed via the IBM Quantum Platform , and on the D-Wave Advantage2 quantum annealer, accessed via the D-Wave Leap quantum cloud service. A classical 2-approximation algorithm is included as a reference baseline. The variational parameters used in the QAOA implementation are selected using the Qiskit AerSimulator with calibration data from the ibm_kingston quantum processor. For quantum annealing, the parameters are determined testing multiple configurations of simulated annealing performed with the SimulatedAnnealingSampler of the dwave-samplers package, and retaining those yielding the best solution quality. Performance is evaluated in terms of solution quality, measurement probability, and proportion of valid solutions. Our results show that, within our experimental setting, quantum annealing consistently outperforms QAOA on instances with up to 10 vertices, and in some cases recovers the exact minimum vertex cover, while the classical 2-approximation baseline serves as a reference point for solution quality. On larger instances, both paradigms exhibit reduced stability and yield fewer valid solutions, with performance becoming increasingly sensitive to parameter choices such as the penalty term.
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
⌈log2(V)⌉ 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.