Welcome to the resource topic for
**2024/646**

**Title:**

Efficient Quantum Algorithm for SUBSET-SUM Problem

**Authors:**
Sanchita Ghosh, Anant Sharma, Sreetama Das, Shibdas Roy

**Abstract:**

Problems in the complexity class NP are not all known to be solvable, but are verifiable given the solution, in polynomial time by a classical computer. The complexity class BQP includes all problems solvable in polynomial time by a quantum computer. Prime factorization is in NP class, and is also in BQP class, owing to Shorâ€™s algorithm. The hardest of all problems within the NP class are called NP-complete. If a quantum algorithm can solve an NP-complete problem in polynomial time, it would imply that a quantum computer can solve all problems in NP in polynomial time. Here, we present a polynomial-time quantum algorithm to solve an NP-complete variant of the SUBSET-SUM problem, thereby, rendering NP\subseteq BQP. We illustrate that given a set of integers, which may be positive or negative, a quantum computer can decide in polynomial time whether there exists any subset that sums to zero. There are many real-world applications of our result, such as finding patterns efficiently in stock-market data, or in recordings of the weather or brain activity. As an example, the decision problem of matching two images in image processing is NP-complete, and can be solved in polynomial time, when amplitude amplification is not required.

**ePrint:**
https://eprint.iacr.org/2024/646

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .