A Quantum Approach to Subset-Sum and Similar Problems

Preprint English OPEN
Daskin, Ammar (2017)
  • Subject: Computer Science - Computational Complexity | Computer Science - Data Structures and Algorithms | Quantum Physics

In this paper, we study the subset-sum problem by using a quantum heuristic approach similar to the verification circuit of quantum Arthur-Merlin games. Under described certain assumptions, we show that the exact solution of the subset sum problem my be obtained in polynomial time and the exponential speed-up over the classical algorithms may be possible. We give a numerical example and discuss the complexity of the approach and its further application to the knapsack problem.
Share - Bookmark