Paper 2024/646
Efficient Quantum Algorithm for SUBSET-SUM Problem
, Istituto Nazionale di Ottica del Consiglio Nazionale delle Ricerche (CNR-INO), Florence, Italy, University of Florence, Sesto Fiorentino, Italy, TCG Centres for Research and Education in Science and Technology, Kolkata, India, Academy of Scientific and Innovative Research (AcSIR), Ghaziabad, India, University of Florence, Sesto Fiorentino, ItalyAbstract
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.
Note: Preprint, 6 pages, 2 figures, comments welcome.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Subset-Sum ProblemNP-complete ProblemBQP AlgorithmQuantum AlgorithmExponential Speedup
- Contact author(s)
-
sanchita ghosh14 @ gmail com
anantsharma2410 @ gmail com
sreetama das @ ino cnr it
roy shibdas @ gmail com - History
- 2024-04-29: approved
- 2024-04-27: 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}
}
