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

Springer eBooks

Solving NP-Complete Problems with Quantum Search

Martin Fürer

Published Apr 3, 2008• 20 citations
Publisher
DOI
10.1007/978-3-540-78773-0_67

Related papers

Solving NP-Complete Problems with a Quantum Computer

Colin P. Williams

Texts in computer science•Dec 6, 2010•3 citations

A New Efficient Quantum Algorithm for Solving NP-complete Problems

Dhananjay P. Mehendale

•Jan 1, 2026•0 citations

Quantum scaling advantage using reduced search in an NP-complete problem

Nature Computational Science•Aug 3, 2026•0 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

Quantum computation and NP-complete problems

Takashi Mihara, Tetsuro Nishino

Lecture notes in computer science•Jan 1, 1994•1 citation

Circuit Design for K-coloring Problem and its Implementation on Near-term Quantum Devices

Amit Saha, Debasri Saha, Amlan Chakrabarti

Nowadays in Quantum Computing, the implementation of quantum algorithm has created a stir since Noisy Intermediate-Scale Quantum (NISQ) devices are out in the market. Researchers are mostly interested in solving NP-complete problems with the help of quantum algorithms for its speedup. As per the work on computational complexity by Karp [1], if any of the NP-complete problem can be solved then any other NP-complete problem can be reduced to that problem in polynomial time. In this Paper, K-coloring problem (NP-complete problem) has been considered to solve using Grover's search. A comparator-based approach has been used to implement K-coloring problem which enables the reduction of the qubit cost compared to the state-of-the-art. An end-to-end automated framework has been proposed to implement the K-coloring problem for any unweighted and undirected graph on any available Noisy Intermediate-Scale Quantum (NISQ) devices, which helps in generalizing our approach.

arXiv:2009.06073•IEEE International Symposium on Smart Electronic Systems (iSES)•Dec 1, 2020•12 citations
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.
Nowadays in Quantum Computing, the implementation of quantum algorithm has created a stir since Noisy Intermediate-Scale Quantum (NISQ) devices are out in the market. Researchers are mostly interested in solving NP-complete problems with the help of quantum algorithms for its speedup. As per the work on computational complexity by Karp [1], if any of the NP-complete problem can be solved then any other NP-complete problem can be reduced to that problem in polynomial time. In this Paper, K-coloring problem (NP-complete problem) has been considered to solve using Grover's search. A comparator-based approach has been used to implement K-coloring problem which enables the reduction of the qubit cost compared to the state-of-the-art. An end-to-end automated framework has been proposed to implement the K-coloring problem for any unweighted and undirected graph on any available Noisy Intermediate-Scale Quantum (NISQ) devices, which helps in generalizing our approach.