Allcock, Jonathan ;
Hamoudi, Yassine ;
Joux, Antoine ;
Klingelhöfer, Felix ;
Santha, Miklos
Classical and Quantum Algorithms for Variants of SubsetSum via Dynamic Programming
Abstract
SubsetSum is an NPcomplete 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 wellknown meetinthemiddle technique. Here we introduce a novel classical dynamicprogrammingbased data structure with applications to SubsetSum and a number of variants, including EqualSums (where one seeks two disjoint subsets with the same sum), 2SubsetSum (a relaxed version of SubsetSum where each item in the input set can be used twice in the summation), and ShiftedSums, 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 variabletime 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 ShiftedSums. 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 EqualSums, a variant of EqualSums 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.
BibTeX  Entry
@InProceedings{allcock_et_al:LIPIcs.ESA.2022.6,
author = {Allcock, Jonathan and Hamoudi, Yassine and Joux, Antoine and Klingelh\"{o}fer, Felix and Santha, Miklos},
title = {{Classical and Quantum Algorithms for Variants of SubsetSum via Dynamic Programming}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {6:16:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772471},
ISSN = {18688969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16944},
URN = {urn:nbn:de:0030drops169444},
doi = {10.4230/LIPIcs.ESA.2022.6},
annote = {Keywords: Quantum algorithm, classical algorithm, dynamic programming, representation technique, subsetsum, equalsum, shiftedsum}
}
01.09.2022
Keywords: 

Quantum algorithm, classical algorithm, dynamic programming, representation technique, subsetsum, equalsum, shiftedsum 
Seminar: 

30th Annual European Symposium on Algorithms (ESA 2022)

Issue date: 

2022 
Date of publication: 

01.09.2022 