Efficient Quantum Algorithm for SUBSET-SUM Problem

Sanchita Ghosh; Anant Sharma; Sreetama Das; Shibdas Roy

Paper 2024/646

Efficient Quantum Algorithm for SUBSET-SUM Problem

Sanchita Ghosh, TCG Centres for Research and Education in Science and Technology, Kolkata, India

Anant Sharma, TCG Centres for Research and Education in Science and Technology, Kolkata, India

Sreetama Das

, Istituto Nazionale di Ottica del Consiglio Nazionale delle Ricerche (CNR-INO), Florence, Italy, University of Florence, Sesto Fiorentino, Italy

Shibdas Roy

, 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, Italy

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.

Note: Added the second-last sentence in step 4 of algorithm in Section III about the exponentiated swap operator W.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: Subset-Sum Problem NP-complete Problem BQP Algorithm Quantum Algorithm Exponential Speedup
Contact author(s): sanchita ghosh14 @ gmail com
anantsharma2410 @ gmail com
sreetama das @ ino cnr it
roy shibdas @ gmail com
History: 2024-08-02: last of 2 revisions; 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},
      url = {https://eprint.iacr.org/2024/646}
}