2026-08-17T00:09:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9252 2024-03-06T10:43:47Z ddc:004 open_access

Subset Sum Quantumly in 1.17^n Helm, Alexander May, Alexander Subset sum Quantum walk Representation technique We study the quantum complexity of solving the subset sum problem, where the elements a_1, ..., a_n are randomly chosen from Z_{2^{l(n)}} and t = sum_i a_i in Z_{2^{l(n)}} is a sum of n/2 elements. In 2013, Bernstein, Jeffery, Lange and Meurer constructed a quantum subset sum algorithm with heuristic time complexity 2^{0.241n}, by enhancing the classical subset sum algorithm of Howgrave-Graham and Joux with a quantum random walk technique. We improve on this by defining a quantum random walk for the classical subset sum algorithm of Becker, Coron and Joux. The new algorithm only needs heuristic running time and memory 2^{0.226n}, for almost all random subset sum instances. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Helm and Alexander May 2018 Is Part Of LIPIcs, Volume 111, 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2018.5 urn:nbn:de:0030-drops-92527 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2018.5 eng https://creativecommons.org/licenses/by/3.0/legalcode