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 and Ising model, and experiments are conducted on IBM’s GenericBackendV2 noisy superconducting qubit simulator and the D-Wave Advantage2 quantum annealer. Performance is evaluated in terms of solution quality, measurement probability, and proportion of valid solutions. The results we obtained show that, within our experimental setting, quantum annealing consistently outperforms its classical counterpart on small instances, while QAOA, though currently limited by simulation constraints, shows promising behavior that improves with increasing circuit depth. As problem size grows, both approaches exhibit sensitivity to parameter choices such as the penalty term and graph density, underscoring the need for careful tuning. These findings suggest that while both paradigms hold potential for combinatorial optimization, further advances in hardware capabilities and parameter calibration will be necessary to achieve reliable performance on larger instances.
Simone Faro, G. Messina, Damiano Muzzicato et al.· IEEE International Symposium...· 0 citations
We present a full-scale implementation and experimental evaluation of a quantum algorithm for the Longest Common Substring (LCS) problem in the circuit model, bridging the gap between recent theoretical advances and practical realization. Building upon a previously proposed \(\tilde{O}(\sqrt {n})\)-depth quantum circuit, we develop a modular implementation in Qiskit that supports non-binary alphabets and incorporates several key enhancements, including a deterministic BBHT-inspired Grover search, domain expansion via ancillary qubits to stabilize amplitude amplification, and circuit-level optimizations that reduce overhead. Our approach is validated through an extensive experimental campaign over a binary alphabet augmented with two termination symbols and length 16 demonstrating an overall accuracy of 98.4%. The results show that errors are both rare and small, with a consistent conservative bias toward underestimation, and that the algorithm maintains high performance across a wide range of input configurations. We further analyze the behavior of the algorithm under realistic noise models, showing a progressive degradation of accuracy and identifying a structural asymmetry in the error patterns induced by the oracle. These findings provide concrete evidence that circuit-based quantum algorithms for string processing can achieve reliable behavior in ideal settings, while highlighting key challenges for their deployment on noisy quantum devices.
R. Cantone, G. Falci, Simone Faro et al.· IEEE International Symposium...· 0 citations