A Quantum Computing Based Solution Approach for NP-Complete Problems
Seda Nur Gungor, Mehmet Karaköse · 2025
Although NP-complete problems have solutions that can be verified in polynomial time, their exponential computational complexity presents significant challenges for classical computing methods. This study focuses on transferring various NP-complete problems into the quantum computing framework. The application of specific quantum computing algorithms is proposed for solving these problems. Within the scope of this study, a reusable quantum component with problem-specific constraints is designed, and a quantum circuit model is introduced to adapt the Quantum Feasibility Labeling algorithm for solving the Maximum Clique problem. Additionally, the Quick Quantum Search algorithm, which performs a search with a single oracle call, is integrated into the solution of the Maximum Independent Set problem. The proposed quantum circuits provide illustrative examples of how the components of an NP-complete problem can be represented in a quantum computing environment and how problem-specific constraints can be implemented within a quantum circuit. The utilization of modular circuit designs effectively demonstrates the applicability of larger and more complex problems in quantum environments. These approaches not only enable more efficient use of computational resources compared to traditional methods but also lead to significant reductions in solution times. This study provides a comprehensive framework that not only demonstrates the practicality of quantum circuits for small-scale NP-complete problems but also lays the groundwork for addressing larger and more complex challenges in future quantum computing applications.