Abstract. This paper introduces a subset-sum algorithm with heuristic asymptotic cost exponent below 0.25. The new algorithm combines the 2010 Howgrave-Graham–Joux subset-sum algorithm with a new streamlined data structure for quantum walks on Johnson graphs.
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.
Quantum walk-based search algorithms have demonstrated an asymptotic quadratic speedup compared to classical search methods. Formulating a generic search problem as a (quantum) search over a graph makes the efficiency of the algorithm to be closely dependent on the properties of the graph itself. In this work, we present a complete implementation of a quantum walk search procedure on Johnson graphs, speeding up the solution of the Subset Sum Problem, a well-known computational problem with applications in resource allocation, scheduling, and cryptanalysis. We provide a detailed design of each sub-circuit, quantifying their costs in terms of gate count, circuit depth, and qubit width, and exhibit all figures of merit as a function of the problem parameters. Our approach includes two distinct implementations: one that minimizes qubit usage and another focused on optimizing circuit depth. We compare our solutions against the unstructured Grover based quantum search algorithm, demonstrating a reduction of the cost on terms of T-count and T-depth, for practically solvable instances. The proposed design serves as a foundational building block for the development of efficient quantum search algorithms that can be modeled on Johnson graphs, bridging the gap with existing theoretical complexity analyses.
Search algorithms based on quantum walks have emerged as a promising approach to solve computational problems across various domains, including combinatorial optimization, and cryptography. Stating a generic search problem in terms of a (quantum) search over a graph makes the efficiency of the algorithmic method depend on the structure of the graph itself. In this work, we propose a complete implementation of a quantum walk search on Johnson graphs, speeding up the solution of the subset-sum problem. We provide a detailed design of each sub-circuit, quantifying their cost in terms of gate number, depth, and width. We compare our solution against a Grover quantum search, showing a reduction of the T-count and T-depth for practically solvable problems. The proposed design provides a building block for the construction of efficient quantum search algorithms that can be modelled on Johnson graphs, filling the gap with the existing theoretical complexity analyses.
Solving random subset sum instances plays an important role in constructing cryptographic systems. For the random subset sum problem, in 2013 Bernstein et al. proposed a quantum algorithm with heuristic time complexity O(20.241n), where the "O" symbol is used to omit poly(logn) factors. In 2018, Helm and May proposed another quantum algorithm that reduces the heuristic time and memory complexity to O(20.226n). In this paper, a new quantum algorithm is proposed, with heuristic time and memory complexity O(20.209n).
The Subset Sum Problem is a member of the NP-complete class, so no known polynomial time algorithm exists for it. Although there are polynomial time approximations and heuristics, these are not always acceptable, yet exact-solution algorithms are unfeasible for large input. Quantum computation offers new insights for not only the Subset Sum Problem but also the entire NP-complete class; most notably, Grover's quantum algorithm for an unstructured database search can be tailored to identify solutions to problems within mathematics and computer science. This paper discusses the physical and conceptual feasibility of quantum computation and demonstrates the utility of quantum search by analyzing the time complexities of the classical dynamic programming algorithm and Grover's algorithm in solving the Subset Sum Problem, evincing the implications this has on the NP-complete class in general.
The Subset Sum problem asks whether, given n integers and a target, some subset of the integers sums to the target. Its best known worst-case running time is O∗(2n/2) (Horowitz and Sahni, 1974), whereas the best quantum upper bound is O∗(2n/3) (Bernstein, Jeffery, Lange, and Meurer, 2013). The k-SUM problem is a parameterized version of Subset Sum asking whether there are k integers that sum to the target. The best classical upper bound for it is O(n⌈k/2⌉), whereas the best quantum running time is O(nk/3) (Tani, 2009). For random instances, a quantum algorithm with running time O(nΦk) is known, where Φk=62k−⌊k/7⌋−⌊(k+3)/7⌋ (Schrottenloher, 2021). We present a new quantum algorithm solving worst-case k-SUM in time O(nΨk), where Ψk=Φk−9[k≡3mod7]−18[k≡6mod7]. The algorithm is not only faster for all k congruent to 3 or 6 modulo 7, but also gives a worst-case guarantee rather than a guarantee restricted to single-solution random instances. Combining our algorithm for 7-SUM with the standard block reduction technique yields an O∗(22n/7) quantum algorithm for Subset Sum, improving the previously known O∗(2n/3) algorithm.