## File(s) not publicly available

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

conference contribution

posted on 2023-11-29, 18:26 authored by Jonathan Allcock, Yassine Hamoudi, Antoine JouxAntoine Joux, Felix Klingelhöfer, Miklos SanthaSubset-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 Oe(2n/2
) and Oe(2n/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(20.504n
) quantum algorithm for Shifted-Sums. This provides a notable improvement on
the best known O(20.773n
) classical running time established by Mucha et al. [27]. 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 Oe(2n/2
) and Oe(22n/5
), respectively.

## History

## Preferred Citation

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: European Symposium on Algorithms (ESA). 2022.## Primary Research Area

- Algorithmic Foundations and Cryptography

## Name of Conference

European Symposium on Algorithms (ESA)## Legacy Posted Date

2023-06-07## Open Access Type

- Unknown

## BibTeX

@inproceedings{cispa_all_3964, title = "Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming", author = "Allcock, Jonathan and Hamoudi, Yassine and Joux, Antoine and Klingelhöfer, Felix and Santha, Miklos", booktitle="{European Symposium on Algorithms (ESA)}", year="2022", }## Usage metrics

## Categories

No categories selected## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC