Logo PTI Logo FedCSIS

Proceedings of the 20th Conference on Computer Science and Intelligence Systems (FedCSIS)

Annals of Computer Science and Information Systems, Volume 43

Adiabatic Quantum Computing for the Subset Sum Problem: Preliminary Studies

, , , ,

DOI: http://dx.doi.org/10.15439/2025F5496

Citation: Proceedings of the 20th Conference on Computer Science and Intelligence Systems (FedCSIS), M. Bolanowski, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 43, pages 635–639 ()

Full text

Abstract. The Subset Sum Problem (SSP) is one of those combinatorial problems that are very easy to understand (take a bunch of integer numbers and verify whether there exists a subset of these numbers which sums up to a given target integer), but it can be very difficult to solve. The SSP is actually an NP-complete problem, but it is ``weakly'' NP-hard, implying that there are instances of SSP that can be solved in polynomial time. For this particular problem, the instance hardness can be measured by evaluating the so-called ``density'' index, which basically compares the number of involved integer numbers to the number of bits we need for their binary representation. In our preliminary study on the use of adiabatic quantum computing for the SSP, we investigate the actual feasibility in solving hard instances of the problem. In fact, hard SSP instances are those requiring a large number of bits for the representation of the integers, while the analog nature of the quantum computer does not allow us to ensure highly accurate integer representations. Some preliminary computational experiments performed on D-Wave quantum annealer are presented and compared to standard solvers for classical computers.

References

  1. T. Albash, D.A. Lidar, Adiabatic Quantum Computation, Reviews of Modern Physics 90(1), 015002, 2018.
  2. J. Allcock, Y. Hamoudi, A. Joux, F. Klingelhöfer, M. Santha, Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming, 30th Annual European Symposium on Algorithms (ESA22), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 28 pages, 2022.
  3. P. Austrin, P. Kaski, M. Koivisto, J. Nederlof, Dense Subset Sum May Be the Hardest, Leibniz International Proceedings in Informatics, 33rd Symposium on Theoretical Aspects of Computer Science, Article No. 13, 13:1–13:14, 2016.
  4. D.J. Bernstein, S. Jeffery, T. Lange, A. Meurer, Quantum Algorithms for the Subset Sum Problem. In: Post-Quantum Cryptography, Proceedings 5, 16–33, 5th International Workshop PQCrypto 2013.
  5. X. Bonnetain, R. Bricout, A. Schrottenloher, Y. Shen, Improved Classical and Quantum Algorithms for Subset-Sum, International Conference on the Theory and Application of Cryptology and Information Security, Springer International Publishing, 633–666, 2020.
  6. M.J. Coster, A. Joux, B.A. LaMacchia, A.M. Odlyzko, C.P. Schnorr, J. Stern, Improved Low-density Subset Sum Algorithms, Computational Complexity 2, 111–128, 1992.
  7. M.G. Damaceno, A. Mucherino, R. Medeiros de Araújo, P.H. Souto Ribeiro, N. Rubiano da Silva, Experimental Investigation of Optical Processing With Spatial Light Modulation, arXiv preprint https://arxiv.org/abs/2507.03821, 2025.
  8. F. Glover, G. Kochenberger, Y. Du, A Tutorial on Formulating and Using QUBO Models, arXiv preprint https://arxiv.org/abs/1811.11538, 2018.
  9. A. Helm, A. May, The Power of few Qubits and Collisions–Subset Sum below Grover’s Bound, Springer International Publishing, International Conference on Post-Quantum Cryptography, 445–460. 2020.
  10. S.B. Hengeveld, N. Rubiano da Silva, D.S. Gonçalves, P.H. Souto Ribeiro, A. Mucherino, An Optical Processor for Matrix-by-Vector Multiplication: an Application to the Distance Geometry Problem in 1D, Journal of Optics 24(1), 015701, 2022.
  11. E. Horowitz, S. Sahni, Computing Partitions with Applications to the Knapsack Problem, Journal of the ACM (JACM) 21(2), 277–292, 1974.
  12. R.M. Karp, Reducibility Among Combinatorial Problems. In: R.E. Miller, J.W. Thatcher, J.D. Bohlinger (Eds.), “Complexity of Computer Computations”. New York: Plenum. 85–103, 1972.
  13. T. Kadowaki, H. Nishimori, Quantum Annealing in the Transverse Ising Model, Physical Review E, 58(5), 5355, 1998.
  14. S. Kirkpatrick, C.D. Gelatt, M.P Vecchi, Optimization by Simulated Annealing, Science 220, 671–680, 1983.
  15. L. Liberti, C. Lavor, N. Maculan, A Branch-and-Prune Algorithm for the Molecular Distance Geometry Problem, International Transactions in Operational Research 15, 1–17, 2008.
  16. L. Liberti, C. Lavor, N. Maculan, A. Mucherino, Euclidean Distance Geometry and Applications, SIAM Review 56(1), 3–69, 2014.
  17. A. Mucherino, C. Lavor, L. Liberti, The Discretizable Distance Geometry Problem, Optimization Letters 6(8), 1671–1686, 2012.
  18. J. Salas, Beyond Worst-Case Subset Sum: An Adaptive, Structure-Aware Solver with Sub-2n/2 Enumeration, arXiv preprint https://arxiv.org/abs/2503.20162, 2025.
  19. C.P. Schnorr, T. Shevchenko, Solving Subset Sum Problems of Density close to 1 by Randomized BKZ-Reduction, Cryptology ePrint Archive, 5 pages, 2012.
  20. Q. Zheng, Y. Miaomiao, Z. Pingyu, W. Yan, L. Weihong, X. Ping, Solving the Subset Sum Problem by the Quantum Ising Model with Variational Quantum Optimization based on Conditional Values at Risk, Science China Physics, Mechanics & Astronomy 67(8), 280311, 2024.
  21. D-Wave Systems Inc., Technical Description of the D-Wave Quantum Processing Unit, https://docs.dwavesys.com, 2021.
  22. Gurobi Optimization, LLC, Gurobi Optimizer Reference Manual, https://www.gurobi.com, 2024.