Quantum Computation and NP-Complete Problems

Takashi Mihara, Tetsuro Nishino

Colin P. Williams

V. Černý

In this paper we discuss physical aspects of intractable (NP-complete) computing problems. We show, using a specific model, that a quantum-mechanical computer can in principle solve an NP-complete problem in polynomial time; however, it would use an exponentially large energy for that computation. We conjecture that our model reflects a complementarity principle concerning the time and the energy needed to perform an NP-complete computation.

Seda Nur Gungor, Mehmet Karaköse

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.

Neema Rustin Badihian

In this paper, we propose two new methods for solving Set Constraint Problems, as well as a potential polynomial solution for NP-Complete problems using quantum computation. While current methods of solving Set Constraint Problems focus on classical techniques, we offer both a quantum-inspired matrix method and a quantum matrix method that neutralizes common contradictions and inconsistencies that appear in these types of problems. We then use our new method to show how a potential polynomial solution for NP-Complete problems could be found using quantum computation. We state this as a potential solution, rather than an actual solution, as the outcome of any quantum computation may not be the same as the expected outcome. We start by formally defining a Set Constraint Problem. We then explain current, classical methods that are used to solve these problems and the drawbacks of such methods. After this, we explain a new quantum-inspired matrix method that allows us to solve these problems, with classical limitations. Then, we explain a new quantum matrix method that solves these problems using quantum information science. Finally, we describe how we can extend this method to potentially solve NP-Complete problems in polynomial time using quantum computation.

Dhananjay P. Mehendale