Paper 2024/646
Efficient Quantum Algorithm for SUBSETSUM Problem
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 polynomialtime quantum algorithm to solve an $NP$complete variant of the $SUBSETSUM$ 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 realworld applications of our result, such as finding patterns efficiently in stockmarket 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.
Note: Added the secondlast sentence in step 4 of algorithm in Section III about the exponentiated swap operator W.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 SubsetSum ProblemNPcomplete ProblemBQP AlgorithmQuantum AlgorithmExponential Speedup
 Contact author(s)

sanchita ghosh14 @ gmail com
anantsharma2410 @ gmail com
sreetama das @ ino cnr it
roy shibdas @ gmail com  History
 20240802: last of 2 revisions
 20240427: received
 See all versions
 Short URL
 https://ia.cr/2024/646
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/646, author = {Sanchita Ghosh and Anant Sharma and Sreetama Das and Shibdas Roy}, title = {Efficient Quantum Algorithm for {SUBSET}{SUM} Problem}, howpublished = {Cryptology ePrint Archive, Paper 2024/646}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/646}}, url = {https://eprint.iacr.org/2024/646} }