Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Texts in computer science

Solving NP-Complete Problems with a Quantum Computer

Colin P. Williams

Published Dec 6, 2010• 3 citations
Publisher
DOI
10.1007/978-1-84628-887-6_7

Related papers

Solving NP-Complete Problems with Quantum Search

Martin Fürer

Springer eBooks•Apr 3, 2008•23 citations

A New Efficient Quantum Algorithm for Solving NP-complete Problems

Dhananjay P. Mehendale

•Jan 1, 2026•0 citations

Quantum Resonance for Solving NP-complete Problems by Simulations

Michail A. Zak

Lecture notes in computer science•Jan 1, 1999•4 citations

Quantum computers and intractable (NP-complete) computing problems

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.

Physical Review A•Jul 1, 1993•38 citations

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

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.

arXiv:2504.15529•Apr 22, 2025•0 citations

Experimental verification of NP-complete problems via linear optics

Jian Li, Tongjun Liu, Tianlei Hou +4 more

Non-deterministic polynomial (NP)-complete problems are collections of intractable problems for classical computers, but they may be easier to solve for quantum computers. Considering that practical quantum computers and networks are still under development, it is necessary to find alternatives to solve these problems. Simulations with linear optics offer a good choice since much of the research on quantum information is executed with this approach. In this work, based on Aaronson's protocol (Theory Comput, 5, 1, 2009) ad Arrazola et. al.'s linear optics scheme (npj Quantum Inf, 78, 022310, 2018), we present a demonstration of the NP-complete 2-out-of-4 SAT problem for 4 variables. The experimental results show that NP-complete problems can be well simulated through linear optical systems.

International Conference on Wireless Communications and Signal Processing (WCSP)•Oct 20, 2021•1 citation
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.
Non-deterministic polynomial (NP)-complete problems are collections of intractable problems for classical computers, but they may be easier to solve for quantum computers. Considering that practical quantum computers and networks are still under development, it is necessary to find alternatives to solve these problems. Simulations with linear optics offer a good choice since much of the research on quantum information is executed with this approach. In this work, based on Aaronson's protocol (Theory Comput, 5, 1, 2009) ad Arrazola et. al.'s linear optics scheme (npj Quantum Inf, 78, 022310, 2018), we present a demonstration of the NP-complete 2-out-of-4 SAT problem for 4 variables. The experimental results show that NP-complete problems can be well simulated through linear optical systems.