[Resource Topic] 2024/646: Efficient Quantum Algorithm for SUBSET-SUM Problem

Welcome to the resource topic for 2024/646

Efficient Quantum Algorithm for SUBSET-SUM Problem

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


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 .