Science China Information Sciences

Quantum algorithm and experimental demonstration for the subset sum problem

Qilin Zheng, Pingyu Zhu, Shichuan Xue, Yang Wang, Chao Wu, Xinyao Yu, Miaomiao Yu, Yingwen Liu, Mingtang Deng, Junjie Wu, Ping Xu

Published Dec 13, 2021• 8 citations

Publisher

DOI: 10.1007/s11432-021-3334-1

Related papers

Quantum Algorithms for the Subset-Sum Problem

Daniel J. Bernstein, Stacey Jeffery, Tanja Lange +1 more

Lecture notes in computer scienceJan 1, 201371 citations

Improved Classical and Quantum Algorithms for Subset-Sum

Xavier Bonnetain, Rémi Bricout, André Schrottenloher +1 more

arXiv:2002.05276Lecture notes in computer scienceJan 1, 202042 citations

Quantum Algorithms of the Subset-Sum Problem on a Quantum Computer

Weng-Long Chang, Ting-Ting Ren, Mang Feng +3 more

In this paper, quantum algorithms for solving an instance of the subset-sum problem is proposed and a NMR experiment for the simplest subset-sum problem to test our theory is also performed.

WASE International Conference on Information EngineeringJul 1, 200911 citations

Classical and quantum dynamic programming for Subset-Sum and variants.

Jonathan Allcock, Yassine Hamoudi, Antoine Joux +2 more

Nov 13, 20210 citations

Improved Quantum Algorithms for Subset Sum and $k$ -SUM

Nikolai Chukhin, Alexander S. Kulikov, Maksim Levitskii +1 more

arXiv:2608.07309Aug 7, 20260 citations

Quantum Algorithms and Applications

Melinda Andrews, Joseph Stephen Dulny, Andrew N. Glaudell +6 more

Sep 1, 20200 citations

Science China Information Sciences

Quantum algorithm and experimental demonstration for the subset sum problem

Qilin Zheng, Pingyu Zhu, Shichuan Xue, Yang Wang, Chao Wu, Xinyao Yu, Miaomiao Yu, Yingwen Liu, Mingtang Deng, Junjie Wu, Ping Xu

Published Dec 13, 2021• 8 citations

Publisher

DOI: 10.1007/s11432-021-3334-1

Related papers

Quantum Algorithms for the Subset-Sum Problem

Daniel J. Bernstein, Stacey Jeffery, Tanja Lange +1 more

Lecture notes in computer scienceJan 1, 201371 citations

Improved Classical and Quantum Algorithms for Subset-Sum

Xavier Bonnetain, Rémi Bricout, André Schrottenloher +1 more

arXiv:2002.05276Lecture notes in computer scienceJan 1, 202042 citations

Quantum Algorithms of the Subset-Sum Problem on a Quantum Computer

Weng-Long Chang, Ting-Ting Ren, Mang Feng +3 more

In this paper, quantum algorithms for solving an instance of the subset-sum problem is proposed and a NMR experiment for the simplest subset-sum problem to test our theory is also performed.

WASE International Conference on Information EngineeringJul 1, 200911 citations

Classical and quantum dynamic programming for Subset-Sum and variants.

Jonathan Allcock, Yassine Hamoudi, Antoine Joux +2 more

Subset-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 $\tilde{O}(2^{n/2})$ and $\tilde{O}(2^{n/3})$ , respectively, based on the well-known meet-in-the-middle technique. Here we introduce a novel dynamic programming 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 a same value modulo $p$ . We use this data structure to give new $\tilde{O}(2^{n/2})$ and $\tilde{O}(2^{n/3})$ classical and quantum algorithms for Subset-Sum, not based on the meet-in-the-middle method. We then use the data structure in combination with variable time amplitude amplification and a quantum pair finding algorithm, extending quantum element distinctness and claw finding algorithms to the multiple solutions case, to give an $O(2^{0.504n})$ quantum algorithm for Shifted-Sums, an improvement on the best known $O(2^{0.773n})$ classical running time. We also study Pigeonhole Equal-Sums and Pigeonhole Modular Equal-Sums, where the existence of a solution is guaranteed by the pigeonhole principle. For the former problem we give classical and quantum algorithms with running time $\tilde{O}(2^{n/2})$ and $\tilde{O}(2^{2n/5})$ , respectively. For the more general modular problem we give a classical algorithm which also runs in time $\tilde{O}(2^{n/2})$ .Subset-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 $\tilde{O}(2^{n/2})$ and $\tilde{O}(2^{n/3})$, respectively, based on the well-known meet-in-the-middle technique. Here we introduce a novel dynamic programming 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 a same value modulo $p$. We use this data structure to give new $\tilde{O}(2^{n/2})$ and $\tilde{O}(2^{n/3})$ classical and quantum algorithms for Subset-Sum, not based on the meet-in-the-middle method. We then use the data structure in combination with variable time amplitude amplification and a quantum pair finding algorithm, extending quantum element distinctness and claw finding algorithms to the multiple solutions case, to give an $O(2^{0.504n})$ quantum algorithm for Shifted-Sums, an improvement on the best known $O(2^{0.773n})$ classical running time. We also study Pigeonhole Equal-Sums and Pigeonhole Modular Equal-Sums, where the existence of a solution is guaranteed by the pigeonhole principle. For the former problem we give classical and quantum algorithms with running time $\tilde{O}(2^{n/2})$ and $\tilde{O}(2^{2n/5})$, respectively. For the more general modular problem we give a classical algorithm which also runs in time $\tilde{O}(2^{n/2})$.

Nov 13, 20210 citations

Improved Quantum Algorithms for Subset Sum and $k$ -SUM

Nikolai Chukhin, Alexander S. Kulikov, Maksim Levitskii +1 more

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^*(2^{n/2})$ (Horowitz and Sahni, 1974), whereas the best quantum upper bound is $O^*(2^{n/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 $\widetilde O(n^{\lceil k/2\rceil})$ , whereas the best quantum running time is $\widetilde O(n^{k/3})$ (Tani, 2009). For random instances, a quantum algorithm with running time $\widetilde O(n^{Φ_k})$ is known, where $Φ_k=\frac{2k-\lfloor k/7\rfloor-\lfloor (k+3)/7\rfloor}{6}$ (Schrottenloher, 2021). We present a new quantum algorithm solving worst-case $k$ -SUM in time $\widetilde O(n^{Ψ_k})$ , where $Ψ_k=Φ_k-\frac{[k\equiv 3\bmod 7]}{9}-\frac{[k\equiv 6\bmod 7]}{18}.$ 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^*(2^{2n/7})$ quantum algorithm for Subset Sum, improving the previously known $O^*(2^{n/3})$ algorithm.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^*(2^{n/2})$ (Horowitz and Sahni, 1974), whereas the best quantum upper bound is $O^*(2^{n/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 $\widetilde O(n^{\lceil k/2\rceil})$, whereas the best quantum running time is $\widetilde O(n^{k/3})$ (Tani, 2009). For random instances, a quantum algorithm with running time $\widetilde O(n^{Φ_k})$ is known, where $$ Φ_k=\frac{2k-\lfloor k/7\rfloor-\lfloor (k+3)/7\rfloor}{6} $$ (Schrottenloher, 2021). We present a new quantum algorithm solving worst-case $k$-SUM in time $\widetilde O(n^{Ψ_k})$, where $$ Ψ_k=Φ_k-\frac{[k\equiv 3\bmod 7]}{9}-\frac{[k\equiv 6\bmod 7]}{18}. $$ 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^*(2^{2n/7})$ quantum algorithm for Subset Sum, improving the previously known $O^*(2^{n/3})$ algorithm.

arXiv:2608.07309Aug 7, 20260 citations

Quantum Algorithms and Applications

Melinda Andrews, Joseph Stephen Dulny, Andrew N. Glaudell +6 more

Sep 1, 20200 citations

Subset-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

\tilde{O}(2^{n/2})

and

\tilde{O}(2^{n/3})

, respectively, based on the well-known meet-in-the-middle technique. Here we introduce a novel dynamic programming 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 a same value modulo

p

. We use this data structure to give new

\tilde{O}(2^{n/2})

and

\tilde{O}(2^{n/3})

classical and quantum algorithms for Subset-Sum, not based on the meet-in-the-middle method. We then use the data structure in combination with variable time amplitude amplification and a quantum pair finding algorithm, extending quantum element distinctness and claw finding algorithms to the multiple solutions case, to give an

O(2^{0.504n})

quantum algorithm for Shifted-Sums, an improvement on the best known

O(2^{0.773n})

classical running time. We also study Pigeonhole Equal-Sums and Pigeonhole Modular Equal-Sums, where the existence of a solution is guaranteed by the pigeonhole principle. For the former problem we give classical and quantum algorithms with running time

\tilde{O}(2^{n/2})

and

\tilde{O}(2^{2n/5})

, respectively. For the more general modular problem we give a classical algorithm which also runs in time

\tilde{O}(2^{n/2})

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^*(2^{n/2})

(Horowitz and Sahni, 1974), whereas the best quantum upper bound is

O^*(2^{n/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

\widetilde O(n^{\lceil k/2\rceil})

, whereas the best quantum running time is

\widetilde O(n^{k/3})

(Tani, 2009). For random instances, a quantum algorithm with running time

\widetilde O(n^{Φ_k})

is known, where

Φ_k=\frac{2k-\lfloor k/7\rfloor-\lfloor (k+3)/7\rfloor}{6}

(Schrottenloher, 2021). We present a new quantum algorithm solving worst-case

k

-SUM in time

\widetilde O(n^{Ψ_k})

, where

Ψ_k=Φ_k-\frac{[k\equiv 3\bmod 7]}{9}-\frac{[k\equiv 6\bmod 7]}{18}.

The algorithm is not only faster for all

k

congruent to

3

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^*(2^{2n/7})

quantum algorithm for Subset Sum, improving the previously known

O^*(2^{n/3})

algorithm.