An Efficient Quantum Solution for NP-Complete Problems using n Partial Measurements

Dhananjay P. Mehendale

Phil Gossett

Abstract: By allowing measurement (read-out) of some, but not all, qubits, this paper shows that NP-complete problems are efficiently solvable by quantum computers in polynomial time with bounded probability (NP in BQP). This is demonstrated by describing a polynomially large network of quantum gates that solves the 3SAT problem with bounded probability in polynomial time. The “weak Church-Turing thesis ” is thus shown to be false. 1.

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.

Masanori Ohya, Igor V. Volovich

Irmi Sax, Sebastian Feld, Sebastian Zielinski +3 more

Many problems of industrial interest are NP-complete, and quickly exhaust resources of computational devices with increasing input sizes. Quantum annealers (QA) are physical devices that aim at this class of problems by exploiting quantum mechanical properties of nature. However, they compete with efficient heuristics and probabilistic or randomised algorithms on classical machines that allow for finding approximate solutions to large NP-complete problems.

Masanori Ohya, Igor Vasil'evich Volovich