The Subset Sum Problem: Reducing Time Complexity of NP-Completeness with Quantum Search

Authors

Bo Moon, University of South Florida

Publication Year

2012

Abstract

The Subset Sum Problem is a member of the NP-complete class, so no known polynomial time algorithm exists for it. Although there are polynomial time approximations and heuristics, these are not always acceptable, yet exact-solution algorithms are unfeasible for large input. Quantum computation offers new insights for not only the Subset Sum Problem but also the entire NP-complete class; most notably, Grover's quantum algorithm for an unstructured database search can be tailored to identify solutions to problems within mathematics and computer science. This paper discusses the physical and conceptual feasibility of quantum computation and demonstrates the utility of quantum search by analyzing the time complexities of the classical dynamic programming algorithm and Grover's algorithm in solving the Subset Sum Problem, evincing the implications this has on the NP-complete class in general.

Recommended Citation

Moon, Bo (2012) "The Subset Sum Problem: Reducing Time Complexity of NP-Completeness with Quantum Search," Undergraduate Journal of Mathematical Modeling: One + Two: Vol. 4: Iss. 2, Article 2.
DOI: http://dx.doi.org/10.5038/2326-3652.4.2.2
Available at: https://digitalcommons.usf.edu/ujmm/vol4/iss2/2

Creative Commons License

This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 4.0 License.