Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming

Authors Jonathan Allcock , Yassine Hamoudi , Antoine Joux, Felix Klingelhöfer, Miklos Santha



PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.6.pdf
  • Filesize: 1.32 MB
  • 18 pages

Document Identifiers

Author Details

Jonathan Allcock
  • Tencent Quantum Laboratory, Hong Kong, China
Yassine Hamoudi
  • Simons Institute for the Theory of Computing, University of California, Berkeley, CA, USA
Antoine Joux
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Felix Klingelhöfer
  • G-SCOP, Université Grenoble Alpes, France
Miklos Santha
  • Centre for Quantum Technologies and MajuLab, National University of Singapore, Singapore

Acknowledgements

JA thanks Shengyu Zhang for helpful discussions during the course of this work.

Cite AsGet BibTex

Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelhöfer, and Miklos Santha. Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.6

Abstract

Subset-Sum is an NP-complete problem where one must decide if a multiset of n integers contains a subset whose elements sum to a target value m. The best known classical and quantum algorithms run in time Õ(2^{n/2}) and Õ(2^{n/3}), respectively, based on the well-known meet-in-the-middle technique. Here we introduce a novel classical dynamic-programming-based data structure with applications to Subset-Sum and a number of variants, including Equal-Sums (where one seeks two disjoint subsets with the same sum), 2-Subset-Sum (a relaxed version of Subset-Sum where each item in the input set can be used twice in the summation), and Shifted-Sums, a generalization of both of these variants, where one seeks two disjoint subsets whose sums differ by some specified value. Given any modulus p, our data structure can be constructed in time O(np), after which queries can be made in time O(n) to the lists of subsets summing to any value modulo p. We use this data structure in combination with variable-time amplitude amplification and a new quantum pair finding algorithm, extending the quantum claw finding algorithm to the multiple solutions case, to give an O(2^{0.504n}) quantum algorithm for Shifted-Sums. This provides a notable improvement on the best known O(2^{0.773n}) classical running time established by Mucha et al. [Mucha et al., 2019]. We also study Pigeonhole Equal-Sums, a variant of Equal-Sums where the existence of a solution is guaranteed by the pigeonhole principle. For this problem we give faster classical and quantum algorithms with running time Õ(2^{n/2}) and Õ(2^{2n/5}), respectively.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
Keywords
  • Quantum algorithm
  • classical algorithm
  • dynamic programming
  • representation technique
  • subset-sum
  • equal-sum
  • shifted-sum

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. A. Abboud. Fine-grained reductions and quantum speedups for dynamic programming. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pages 8:1-8:13, 2019. Google Scholar
  2. A. Abboud, K. Bringmann, D. Hermelin, and D. Shabtay. SETH-based lower bounds for subset sum and bicriteria path. In Proceedings of the 30th Symposium on Discrete Algorithms (SODA), pages 41-57, 2019. Google Scholar
  3. J. Allcock, Y. Hamoudi, A. Joux, F. Klingelhöfer, and M. Santha. Classical and quantum algorithms for variants of subset-sum via dynamic programming, 2021. http://arxiv.org/abs/2111.07059 [quant-ph].
  4. A. Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1):210-239, 2007. Google Scholar
  5. A. Ambainis. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 636-647, 2012. Google Scholar
  6. A. Ambainis, K. Balodis, J. Iraids, M. Kokainis, K. Prusis, and J. Vihrovs. Quantum speedups for exponential-time dynamic programming algorithms. In Proceedings of the 30th Symposium on Discrete Algorithms (SODA), pages 1783-1793, 2019. Google Scholar
  7. C. Bazgan, M. Santha, and Z. Tuza. Efficient approximation algorithms for the Subset-Sums Equality problem. Journal of Computer and System Sciences, 64(2):160-170, 2002. Google Scholar
  8. A. Becker, J.-S. Coron, and A. Joux. Improved generic algorithms for hard knapsacks. In Proceedings of the 30th International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pages 364-385, 2011. Google Scholar
  9. D. J. Bernstein, S. Jeffery, T. Lange, and A. Meurer. Quantum algorithms for the subset-sum problem. In Proceedings of the 5th International Workshop on Post-Quantum Cryptography (PQCrypto), pages 16-33, 2013. Google Scholar
  10. X. Bonnetain, R. Bricout, A. Schrottenloher, and Y. Shen. Improved classical and quantum algorithms for subset-sum. In Proceedings of the 26th International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), pages 633-666, 2020. Google Scholar
  11. M. Boyer, G. Brassard, P. Høyer, and A. Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4-5):493-505, 1998. Google Scholar
  12. K. Bringmann. A near-linear pseudopolynomial time algorithm for subset sum. In Proceedings of the 28th Symposium on Discrete Algorithms (SODA), pages 1073-1084, 2017. Google Scholar
  13. H. Buhrman, B. Loff, and L. Torenvliet. Hardness of approximation for knapsack problems. Theory of Computing Systems, 56(2):372-393, 2015. Google Scholar
  14. X. Chen, Y. Jin, T. Randolph, and R. A. Servedio. Average-case subset balancing problems. In Proceedings of the 33rd Symposium on Discrete Algorithms (SODA), pages 743-778, 2022. Google Scholar
  15. A. Esser and A. May. Low weight discrete logarithm and subset sum in 2^0.65n with polynomial memory. In Proceedings of the 39th International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pages 94-122, 2020. Google Scholar
  16. R. G. Gallager. Information Theory and Reliable Communication. John Wiley and Sons, 1968. Google Scholar
  17. G. H. Hardy and E. M. Wright. An Introduction to the Theory of Numbers. Oxford, fourth edition, 1975. Google Scholar
  18. A. Helm and A. May. Subset sum quantumly in 1.17ⁿ. In Proceedings of the 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), pages 5:1-5:15, 2018. Google Scholar
  19. E. Horowitz and S. Sahni. Computing partitions with applications to the knapsack problem. Journal of the ACM, 21(2):277-292, 1974. Google Scholar
  20. N. Howgrave-Graham and A. Joux. New generic algorithms for hard knapsacks. In Proceedings of the 29th International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pages 235-256, 2010. Google Scholar
  21. K. Jansen, F. Land, and K. Land. Bounding the running time of algorithms for scheduling and packing problems. SIAM Journal on Discrete Mathematics, 30(1):343-366, 2016. Google Scholar
  22. S. Jeffery. Frameworks for Quantum Algorithms. PhD thesis, University of Waterloo, 2014. Google Scholar
  23. R. M. Karp. Reducibility among combinatorial problems. In Proceedings of the Symposium on the Complexity of Computer Computations, pages 85-103, 1972. Google Scholar
  24. H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer, 2004. Google Scholar
  25. F. Magniez, A. Nayak, J. Roland, and M. Santha. Search via quantum walk. SIAM Journal on Computing, 40(1):142-164, 2011. Google Scholar
  26. N. Megiddo and C. H. Papadimitriou. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2):317-324, 1991. Google Scholar
  27. M. Mucha, J. Nederlof, J. Pawlewicz, and K. Wegrzycki. Equal-subset-sum faster than the meet-in-the-middle. In Proceedings of the 27th European Symposium on Algorithms (ESA), pages 73:1-73:16, 2019. Google Scholar
  28. C. H. Papadimitriou. On graph-theoretic lemmata and complexity classes (extended abstract). In Proceedings of the 31st Symposium on Foundations of Computer Science (FOCS), pages 794-801, 1990. Google Scholar
  29. K. Sotiraki, M. Zampetakis, and G. Zirdelis. Ppp-completeness with connections to cryptography. In Proceedings of the 59th Symposium on Foundations of Computer Science (FOCS), pages 148-158, 2018. Google Scholar
  30. S. Tani. Claw finding algorithms using quantum walk. Theoretical Computer Science, 410(50):5285-5297, 2009. Google Scholar
  31. G. J. Woeginger. Open problems around exact algorithms. Discrete Applied Mathematics, 156(3):397-405, 2008. Google Scholar
  32. G. J. Woeginger and Z. Yu. On the equal-subset-sum problem. Information Processing Letters, 42(6):299-302, 1992. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail