© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2504.15529

Potential for Polynomial Solution for NP-Complete Problems using Quantum Computation

Neema Rustin Badihian

Published Apr 22, 2025• 0 citations

Abstract

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.

DOI: 10.48550/arxiv.2504.15529

Related papers

A Quantum Computing Based Solution Approach for NP-Complete Problems

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.

•Feb 19, 2025•4 citations

The Subset Sum Problem: Reducing Time Complexity of NP-Completeness with Quantum Search

Bo Moon

The Subset Sum Problem is a member of the NP-complete class, so no known polynomial time algorithm exists for it. Although there are polynomial time approximations and heuristics, these are not always acceptable, yet exact-solution algorithms are unfeasible for large input. Quantum computation offers new insights for not only the Subset Sum Problem but also the entire NP-complete class; most notably, Grover's quantum algorithm for an unstructured database search can be tailored to identify solutions to problems within mathematics and computer science. This paper discusses the physical and conceptual feasibility of quantum computation and demonstrates the utility of quantum search by analyzing the time complexities of the classical dynamic programming algorithm and Grover's algorithm in solving the Subset Sum Problem, evincing the implications this has on the NP-complete class in general.

Undergraduate Journal of Mathematical Modeling One + Two•May 1, 2013•3 citations

The P Vs NP Problem: A Method for Solving NP-Complete Problems by use of Graph Embodiment on a Quantum Computation Paradigm using a Relational Database Query

Shadrack Mwanik, Andrew Mwaura Kahonge, Evans Kirimi Miriti

The relationship between the complexity class P and NP is one of the most fascinating and unresolved question in theoretical Computer Science. The classical computational paradigm, hedged on Turing thesis may be by itself the limiting factor. To investigate this relationship, a method for solving a query problem on a relational database on the classical and the quantum computational paradigm has been developed. The method solves queries or database problems through the use of graphs. The results indicate that the solution to the P vs NP cannot be resolved under the current computation paradigms and may requires a new computation paradigm to resolve it.

•Jan 1, 2013•0 citations

New quantum algorithm solving the NP complete problem

Makoto Ohya

We review the quantum chaos algorithm solving the NP-complete problems in polynomial time. This work has been done in the series of papers with Professor Igor Volovich for nearly ten years.

P-Adic Numbers Ultrametric Analysis and Applications•Feb 1, 2012•0 citations

On New Quantum Search Algorithms and Complexity of NP-Complete Problems

Dhananjay P. Mehendale

We develop three new quantum algorithms for searching the desired target state in the unstructured database of size N. The first algorithm requires Log N iterative steps. It constructs two quantum bags of equal size in terms of two quantum states, out of which exactly one quantum state will have nonzero overlap with the target state. This determination of overlap is done by taking the inner product, in Log N time [2], of the implicitly known target state with any one of these two quantum states. The second algorithm requires just one single step which uses a new suitable operator and the choice of this operator is problem dependent, i.e. it depends upon the number of qubits required to be used to represent an element in the index set. The third algorithm again requires only a single step and this algorithm makes use of a fixed (same) operator. It is known that algorithm for unstructured database search can be easily adaptable for solving NP-Complete problems. However, the computational complexity of NP-Complete problems after the adaptations of both the classical as well as quantum [1] search algorithms remains of the exponential order as the exponent for quantum [1] algorithm changes only to one-half times the exponent for classical algorithm. But for our quantum algorithms the exponent falls substantially so that our new quantum algorithms for unstructured search are capable if reducing the computational complexity of NP-Complete problems to polynomial order!

•Jul 1, 2016•0 citations

Solving NP-complete Problems Using Quantum Weightless Neuron Nodes

Fernando M. de Paula Neto, Teresa B. Ludermir, Wilson Rosa de Oliveira +1 more

Despite neural networks have super-Turing computing power, there is no known algorithm for obtaining a classical neural networks that solves NP-complete problems in polynomial time. However this paper shows that a quantum neural networks model coupled with a non-unitary operator can solve 3-SAT in polynomial time. The proposed method uses a network circuit to represent a Boolean logic function and a non-unitary operator to decide the satisfiability. The parameters of the network is set deterministically and manually, accordingly to the problem at hand with neither quantum nor classical learning.

Brazilian Conference on Intelligent Systems•Nov 1, 2015•5 citations

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.

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.

The Subset Sum Problem is a member of the NP-complete class, so no known polynomial time algorithm exists for it. Although there are polynomial time approximations and heuristics, these are not always acceptable, yet exact-solution algorithms are unfeasible for large input. Quantum computation offers new insights for not only the Subset Sum Problem but also the entire NP-complete class; most notably, Grover's quantum algorithm for an unstructured database search can be tailored to identify solutions to problems within mathematics and computer science. This paper discusses the physical and conceptual feasibility of quantum computation and demonstrates the utility of quantum search by analyzing the time complexities of the classical dynamic programming algorithm and Grover's algorithm in solving the Subset Sum Problem, evincing the implications this has on the NP-complete class in general.

The relationship between the complexity class P and NP is one of the most fascinating and unresolved question in theoretical Computer Science. The classical computational paradigm, hedged on Turing thesis may be by itself the limiting factor. To investigate this relationship, a method for solving a query problem on a relational database on the classical and the quantum computational paradigm has been developed. The method solves queries or database problems through the use of graphs. The results indicate that the solution to the P vs NP cannot be resolved under the current computation paradigms and may requires a new computation paradigm to resolve it.

We develop three new quantum algorithms for searching the desired target state in the unstructured database of size N. The first algorithm requires Log N iterative steps. It constructs two quantum bags of equal size in terms of two quantum states, out of which exactly one quantum state will have nonzero overlap with the target state. This determination of overlap is done by taking the inner product, in Log N time [2], of the implicitly known target state with any one of these two quantum states. The second algorithm requires just one single step which uses a new suitable operator and the choice of this operator is problem dependent, i.e. it depends upon the number of qubits required to be used to represent an element in the index set. The third algorithm again requires only a single step and this algorithm makes use of a fixed (same) operator. It is known that algorithm for unstructured database search can be easily adaptable for solving NP-Complete problems. However, the computational complexity of NP-Complete problems after the adaptations of both the classical as well as quantum [1] search algorithms remains of the exponential order as the exponent for quantum [1] algorithm changes only to one-half times the exponent for classical algorithm. But for our quantum algorithms the exponent falls substantially so that our new quantum algorithms for unstructured search are capable if reducing the computational complexity of NP-Complete problems to polynomial order!

Despite neural networks have super-Turing computing power, there is no known algorithm for obtaining a classical neural networks that solves NP-complete problems in polynomial time. However this paper shows that a quantum neural networks model coupled with a non-unitary operator can solve 3-SAT in polynomial time. The proposed method uses a network circuit to represent a Boolean logic function and a non-unitary operator to decide the satisfiability. The parameters of the network is set deterministically and manually, accordingly to the problem at hand with neither quantum nor classical learning.