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 .