Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2311.08042 · Leibniz international proceedings in informatics

Quantum Algorithms for Graph Coloring and Other Partitioning, Covering, and Packing Problems

Serge Gaspers, Jerry Zirui Li

Published Nov 14, 2023• 9 citations
arXivHTMLPDF

Abstract

Let U be a universe on n elements, let k be a positive integer, and let ℱ be a family of (implicitly defined) subsets of U. We consider the problems of partitioning U into k sets from ℱ, covering U with k sets from ℱ, and packing k non-intersecting sets from ℱ into U. Classically, these problems can be solved via inclusion-exclusion in 2ⁿ n^O(1) time [Andreas Björklund et al., 2009]. Quantumly, there are faster algorithms for graph coloring with running time O(1.9140ⁿ) [Kazuya Shimizu and Ryuhei Mori, 2022] and for Set Cover with a small number of sets with running time O(1.7274ⁿ |ℱ|^O(1)) [Andris Ambainis et al., 2019]. In this paper, we give a quantum speedup for Set Partition, Set Cover, and Set Packing whenever there is a classical enumeration algorithm that lends itself to a quadratic quantum speedup, which, for any subinstance on a set X ⊆ U, enumerates at least one member of a k-partition, k-cover, or k-packing (if one exists) restricted to (or projected onto, in the case of k-cover) the set X in c^|X| n^O(1) time with c < 2. Our bounded-error quantum algorithm runs in time (2+c)^{n/2} n^O(1) for Set Partition, Set Cover, and Set Packing. It is obtained by combining three algorithms that have the best running time for some values of c. When c ≤ 1.147899, our algorithm is slightly faster than (2+c)^{n/2} n^O(1); when c approaches 1, it matches the O(1.7274ⁿ |ℱ|^O(1)) running time of [Andris Ambainis et al., 2019] for Set Cover when |ℱ| is subexponential in n. For covering, packing, and partitioning into maximal independent sets, maximal cliques, maximal bicliques, maximal cluster graphs, maximal triangle-free graphs, maximal cographs, maximal claw-free graphs, maximal trivially-perfect graphs, maximal threshold graphs, maximal split graphs, maximal line graphs, and maximal induced forests, we obtain bounded-error quantum algorithms with running times ranging from O(1.8554ⁿ) to O(1.9629ⁿ). Packing and covering by maximal induced matchings can be done quantumly in O(1.8934ⁿ) time. For Graph Coloring (covering with k maximal independent sets), we further improve the running time to O(1.7956ⁿ) by leveraging faster algorithms for coloring with a small number of colors to better balance our divide-and-conquer steps. For Domatic Number (packing k minimal dominating sets), we obtain a O((2-ε)ⁿ) running time for some ε > 0. Several of our results should be of interest to proponents of classical computing: - We present an inclusion-exclusion algorithm with running time O^*(∑_{i=0}^⌊αn⌋ binom(n,i)), which determines, for each X ⊆ U of size at most α n, 0 ≤ α ≤ 1, whether (X,ℱ) has a k-cover, k-partition, or k-packing. This running time is best-possible, up to polynomial factors. - We prove that for any linear-sized vertex subset X ⊆ V of a graph G = (V,E), the number of minimal dominating sets of G that are subsets of X is O((2-ε)^|X|) for some ε > 0.

DOI
10.48550/arxiv.2311.08042

Related papers

Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs

Adam Glos, Martins Kokainis, Ryuhei Mori +1 more

Motivated by the quantum speedup for dynamic programming on the Boolean hypercube by Ambainis et al. (2019), we investigate which graphs admit a similar quantum advantage. In this paper, we examine a generalization of the Boolean hypercube graph, the $n$-dimensional lattice graph $Q(D,n)$ with vertices in $\{0,1,\ldots,D\}^n$. We study the complexity of the following problem: given a subgraph $G$ of $Q(D,n)$ via query access to the edges, determine whether there is a path from $0^n$ to $D^n$. While the classical query complexity is $\widetildeΘ((D+1)^n)$, we show a quantum algorithm with complexity $\widetilde O(T_D^n)$, where $T_D < D+1$. The first few values of $T_D$ are $T_1 \approx 1.817$, $T_2 \approx 2.660$, $T_3 \approx 3.529$, $T_4 \approx 4.421$, $T_5 \approx 5.332$. We also prove that $T_D \geq \frac{D+1}{\mathrm e}$, thus for general $D$, this algorithm does not provide, for example, a speedup, polynomial in the size of the lattice. While the presented quantum algorithm is a natural generalization of the known quantum algorithm for $D=1$ by Ambainis et al., the analysis of complexity is rather complicated. For the precise analysis, we use the saddle-point method, which is a common tool in analytic combinatorics, but has not been widely used in this field. We then show an implementation of this algorithm with time complexity $\text{poly}(n)^{\log n} T_D^n$, and apply it to the Set Multicover problem. In this problem, $m$ subsets of $[n]$ are given, and the task is to find the smallest number of these subsets that cover each element of $[n]$ at least $D$ times. While the time complexity of the best known classical algorithm is $O(m(D+1)^n)$, the time complexity of our quantum algorithm is $\text{poly}(m,n)^{\log n} T_D^n$.

arXiv:2104.14384•Leibniz international proceedings in informatics•Jan 1, 2021•13 citations

Exponential-Time Quantum Algorithms for Graph Coloring Problems

Kazuya Shimizu, Ryuhei Mori

Abstract The fastest known classical algorithm deciding the k-colorability of n-vertex graph requires running time $$\varOmega (2^n)$$ Ω ( 2 n ) for $$k\ge 5$$ k ≥ 5 . In this work, we present an exponential-space quantum algorithm computing the chromatic number with running time $$O(1.9140^n)$$ O ( 1 . 9140 n ) using quantum random access memory (QRAM). Our approach is based on Ambainis et al’s quantum dynamic programming with applications of Grover’s search to branching algorithms. We also present a polynomial-space quantum algorithm not using QRAM for the graph 20-coloring problem with running time $$O(1.9575^n)$$ O ( 1 . 9575 n ) . For the polynomial-space quantum algorithm, we essentially develop $$(4-\epsilon )^n$$ ( 4 - ϵ ) n -time classical algorithms that can be improved quadratically by Grover’s search.

arXiv:1907.00529•Algorithmica•Jun 1, 2022•28 citations

Polynomial-Space Quantum Algorithms from Classical Branching: Colouring, Domination and Monotone Local Search

Sebastian Senge

We give quantum algorithms for exponential-time problems on $n$ vertices or elements, with bounded error, polynomial space and no quantum random access memory. Our results are these. (1) 4-Colouring in quantum time $O(1.3032^n)$, from a polynomial-space branching algorithm with polynomial-space terminal algorithms; with the branching algorithm alone, $O(1.3100^n)$. The previous best bound in this model, to our knowledge, is $O(1.3231^n)$. (2) $k$-Colouring below the previous best bound for $k \in \{5, 7, 8, 9, 10, 11\}$ and $13 \le k \le 18$, from $O(1.4518^n)$ for $k = 5$ to $O(1.9233^n)$ for $k = 18$. (3) Dominating Set in $O(1.2235^n)$, against the previous $O(2^{n/2})$, Independent Dominating Set in $O(1.1583^n)$, and Edge Dominating Set and Minimum Maximal Matching in $O(1.1501^n)$. (4) A quantum form of monotone local search: if the extension problem has a backtracking tree with $c^k$ nodes up to polynomial factors, the problem is solved in quantum time $(2 - 1/c)^{n/2}$ up to polynomial factors. This gives Feedback Vertex Set in $O(1.3081^n)$, Subset and Group Feedback Vertex Set in $O(1.3229^n)$, Cluster Vertex Deletion in $O(1.2033^n)$, 3-Hitting Set in $O(1.2405^n)$, Proper Interval Vertex Deletion in $O(1.3541^n)$, Multicut on Trees in $O(1.1647^n)$ and Min-Ones $d$-SAT in $O^*((2-1/d)^{n/2})$. (5) Quantum exponential-time approximations below the quantum exact bounds, such as a 1.1-approximation for Vertex Cover in $O(1.0555^n)$ and for Feedback Vertex Set in $O(1.2161^n)$. The colouring exponents for $k \ge 6$ come from an evaluation of a known reduction recursion, computed in floating point with a margin.

arXiv:2611.12714•Nov 9, 2026•0 citations

Quantum Query Algorithms for the Constructive Diagonal Ramsey Theorem

Cheng Xin

The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an $N$-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every $K\ge2$ and $N\ge4^{K-1}$, finds and verifies a homogeneous $K$-set using $O\!\left(2^K K\log\frac Kη\right)$ edge queries with failure probability at most $η$. At the Ramsey scale $N=2^n$, this yields a homogeneous set of order $\lfloor n/2\rfloor+1$ using $O(\sqrt N\log N\log(\log N/η))$ queries, improving on the $O(N)$ queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an $Ω(N^{1/12})$ quantum lower bound by a reduction from collision finding. The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an $Ω(N^{1-1/\sqrt2})$ randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution $G(N,1/2)$. On that distribution a greedy quantum search uses only $\widetilde O(N^{1/4})$ queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.

quant-pharXiv:2609.05812•Sep 8, 2026•0 citations

Quantum algorithms for subset finding

Andrew M. Childs, Eisenberg, J M

Recently, Ambainis gave an O(N^(2/3))-query quantum walk algorithm for element distinctness, and more generally, an O(N^(L/(L+1)))-query algorithm for finding L equal numbers. We point out that this algorithm actually solves a much more general problem, the problem of finding a subset of size L that satisfies any given property. We review the algorithm and give a considerably simplified analysis of its query complexity. We present several applications, including two algorithms for the problem of finding an L-clique in an N-vertex graph. One of these algorithms uses O(N^(2L/(L+1))) edge queries, and the other uses \\tilde{O}(N^((5L-2)/(2L+4))), which is an improvement for L <= 5. The latter algorithm generalizes a recent result of Magniez, Santha, and Szegedy, who considered the case L=3 (finding a triangle). We also pose two open problems regarding continuous time quantum walk and lower bounds.

•Nov 6, 2003•54 citations

Improved Quantum Algorithms for Subset Sum and kkk-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.

arXiv:2608.07309•Aug 7, 2026•1 citation
Let U be a universe on n elements, let k be a positive integer, and let ℱ be a family of (implicitly defined) subsets of U. We consider the problems of partitioning U into k sets from ℱ, covering U with k sets from ℱ, and packing k non-intersecting sets from ℱ into U. Classically, these problems can be solved via inclusion-exclusion in 2ⁿ n^O(1) time [Andreas Björklund et al., 2009]. Quantumly, there are faster algorithms for graph coloring with running time O(1.9140ⁿ) [Kazuya Shimizu and Ryuhei Mori, 2022] and for Set Cover with a small number of sets with running time O(1.7274ⁿ |ℱ|^O(1)) [Andris Ambainis et al., 2019]. In this paper, we give a quantum speedup for Set Partition, Set Cover, and Set Packing whenever there is a classical enumeration algorithm that lends itself to a quadratic quantum speedup, which, for any subinstance on a set X ⊆ U, enumerates at least one member of a k-partition, k-cover, or k-packing (if one exists) restricted to (or projected onto, in the case of k-cover) the set X in c^|X| n^O(1) time with c < 2. Our bounded-error quantum algorithm runs in time (2+c)^{n/2} n^O(1) for Set Partition, Set Cover, and Set Packing. It is obtained by combining three algorithms that have the best running time for some values of c. When c ≤ 1.147899, our algorithm is slightly faster than (2+c)^{n/2} n^O(1); when c approaches 1, it matches the O(1.7274ⁿ |ℱ|^O(1)) running time of [Andris Ambainis et al., 2019] for Set Cover when |ℱ| is subexponential in n. For covering, packing, and partitioning into maximal independent sets, maximal cliques, maximal bicliques, maximal cluster graphs, maximal triangle-free graphs, maximal cographs, maximal claw-free graphs, maximal trivially-perfect graphs, maximal threshold graphs, maximal split graphs, maximal line graphs, and maximal induced forests, we obtain bounded-error quantum algorithms with running times ranging from O(1.8554ⁿ) to O(1.9629ⁿ). Packing and covering by maximal induced matchings can be done quantumly in O(1.8934ⁿ) time. For Graph Coloring (covering with k maximal independent sets), we further improve the running time to O(1.7956ⁿ) by leveraging faster algorithms for coloring with a small number of colors to better balance our divide-and-conquer steps. For Domatic Number (packing k minimal dominating sets), we obtain a O((2-ε)ⁿ) running time for some ε > 0. Several of our results should be of interest to proponents of classical computing: - We present an inclusion-exclusion algorithm with running time O^*(∑_{i=0}^⌊αn⌋ binom(n,i)), which determines, for each X ⊆ U of size at most α n, 0 ≤ α ≤ 1, whether (X,ℱ) has a k-cover, k-partition, or k-packing. This running time is best-possible, up to polynomial factors. - We prove that for any linear-sized vertex subset X ⊆ V of a graph G = (V,E), the number of minimal dominating sets of G that are subsets of X is O((2-ε)^|X|) for some ε > 0.
Motivated by the quantum speedup for dynamic programming on the Boolean hypercube by Ambainis et al. (2019), we investigate which graphs admit a similar quantum advantage. In this paper, we examine a generalization of the Boolean hypercube graph, the nnn-dimensional lattice graph Q(D,n)Q(D,n)Q(D,n) with vertices in {0,1,…,D}n\{0,1,\ldots,D\}^n{0,1,…,D}n. We study the complexity of the following problem: given a subgraph GGG of Q(D,n)Q(D,n)Q(D,n) via query access to the edges, determine whether there is a path from 0n0^n0n to DnD^nDn. While the classical query complexity is Θ~((D+1)n)\widetildeΘ((D+1)^n)Θ((D+1)n), we show a quantum algorithm with complexity O~(TDn)\widetilde O(T_D^n)O(TDn​), where TD<D+1T_D < D+1TD​<D+1. The first few values of TDT_DTD​ are T1≈1.817T_1 \approx 1.817T1​≈1.817, T2≈2.660T_2 \approx 2.660T2​≈2.660, T3≈3.529T_3 \approx 3.529T3​≈3.529, T4≈4.421T_4 \approx 4.421T4​≈4.421, T5≈5.332T_5 \approx 5.332T5​≈5.332. We also prove that TD≥D+1eT_D \geq \frac{D+1}{\mathrm e}TD​≥eD+1​, thus for general DDD, this algorithm does not provide, for example, a speedup, polynomial in the size of the lattice. While the presented quantum algorithm is a natural generalization of the known quantum algorithm for D=1D=1D=1 by Ambainis et al., the analysis of complexity is rather complicated. For the precise analysis, we use the saddle-point method, which is a common tool in analytic combinatorics, but has not been widely used in this field. We then show an implementation of this algorithm with time complexity poly(n)log⁡nTDn\text{poly}(n)^{\log n} T_D^npoly(n)lognTDn​, and apply it to the Set Multicover problem. In this problem, mmm subsets of [n][n][n] are given, and the task is to find the smallest number of these subsets that cover each element of [n][n][n] at least DDD times. While the time complexity of the best known classical algorithm is O(m(D+1)n)O(m(D+1)^n)O(m(D+1)n), the time complexity of our quantum algorithm is poly(m,n)log⁡nTDn\text{poly}(m,n)^{\log n} T_D^npoly(m,n)lognTDn​.
Abstract The fastest known classical algorithm deciding the k-colorability of n-vertex graph requires running time Ω(2n)\varOmega (2^n)Ω(2n) Ω ( 2 n ) for k≥5k\ge 5k≥5 k ≥ 5 . In this work, we present an exponential-space quantum algorithm computing the chromatic number with running time O(1.9140n)O(1.9140^n)O(1.9140n) O ( 1 . 9140 n ) using quantum random access memory (QRAM). Our approach is based on Ambainis et al’s quantum dynamic programming with applications of Grover’s search to branching algorithms. We also present a polynomial-space quantum algorithm not using QRAM for the graph 20-coloring problem with running time O(1.9575n)O(1.9575^n)O(1.9575n) O ( 1 . 9575 n ) . For the polynomial-space quantum algorithm, we essentially develop (4−ϵ)n(4-\epsilon )^n(4−ϵ)n ( 4 - ϵ ) n -time classical algorithms that can be improved quadratically by Grover’s search.
We give quantum algorithms for exponential-time problems on nnn vertices or elements, with bounded error, polynomial space and no quantum random access memory. Our results are these. (1) 4-Colouring in quantum time O(1.3032n)O(1.3032^n)O(1.3032n), from a polynomial-space branching algorithm with polynomial-space terminal algorithms; with the branching algorithm alone, O(1.3100n)O(1.3100^n)O(1.3100n). The previous best bound in this model, to our knowledge, is O(1.3231n)O(1.3231^n)O(1.3231n). (2) kkk-Colouring below the previous best bound for k∈{5,7,8,9,10,11}k \in \{5, 7, 8, 9, 10, 11\}k∈{5,7,8,9,10,11} and 13≤k≤1813 \le k \le 1813≤k≤18, from O(1.4518n)O(1.4518^n)O(1.4518n) for k=5k = 5k=5 to O(1.9233n)O(1.9233^n)O(1.9233n) for k=18k = 18k=18. (3) Dominating Set in O(1.2235n)O(1.2235^n)O(1.2235n), against the previous O(2n/2)O(2^{n/2})O(2n/2), Independent Dominating Set in O(1.1583n)O(1.1583^n)O(1.1583n), and Edge Dominating Set and Minimum Maximal Matching in O(1.1501n)O(1.1501^n)O(1.1501n). (4) A quantum form of monotone local search: if the extension problem has a backtracking tree with ckc^kck nodes up to polynomial factors, the problem is solved in quantum time (2−1/c)n/2(2 - 1/c)^{n/2}(2−1/c)n/2 up to polynomial factors. This gives Feedback Vertex Set in O(1.3081n)O(1.3081^n)O(1.3081n), Subset and Group Feedback Vertex Set in O(1.3229n)O(1.3229^n)O(1.3229n), Cluster Vertex Deletion in O(1.2033n)O(1.2033^n)O(1.2033n), 3-Hitting Set in O(1.2405n)O(1.2405^n)O(1.2405n), Proper Interval Vertex Deletion in O(1.3541n)O(1.3541^n)O(1.3541n), Multicut on Trees in O(1.1647n)O(1.1647^n)O(1.1647n) and Min-Ones ddd-SAT in O∗((2−1/d)n/2)O^*((2-1/d)^{n/2})O∗((2−1/d)n/2). (5) Quantum exponential-time approximations below the quantum exact bounds, such as a 1.1-approximation for Vertex Cover in O(1.0555n)O(1.0555^n)O(1.0555n) and for Feedback Vertex Set in O(1.2161n)O(1.2161^n)O(1.2161n). The colouring exponents for k≥6k \ge 6k≥6 come from an evaluation of a known reduction recursion, computed in floating point with a margin.
The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an NNN-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every K≥2K\ge2K≥2 and N≥4K−1N\ge4^{K-1}N≥4K−1, finds and verifies a homogeneous KKK-set using O ⁣(2KKlog⁡Kη)O\!\left(2^K K\log\frac Kη\right)O(2KKlogηK​) edge queries with failure probability at most ηηη. At the Ramsey scale N=2nN=2^nN=2n, this yields a homogeneous set of order ⌊n/2⌋+1\lfloor n/2\rfloor+1⌊n/2⌋+1 using O(Nlog⁡Nlog⁡(log⁡N/η))O(\sqrt N\log N\log(\log N/η))O(N​logNlog(logN/η)) queries, improving on the O(N)O(N)O(N) queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an Ω(N1/12)Ω(N^{1/12})Ω(N1/12) quantum lower bound by a reduction from collision finding. The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an Ω(N1−1/2)Ω(N^{1-1/\sqrt2})Ω(N1−1/2​) randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution G(N,1/2)G(N,1/2)G(N,1/2). On that distribution a greedy quantum search uses only O~(N1/4)\widetilde O(N^{1/4})O(N1/4) queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.
Recently, Ambainis gave an O(N^(2/3))-query quantum walk algorithm for element distinctness, and more generally, an O(N^(L/(L+1)))-query algorithm for finding L equal numbers. We point out that this algorithm actually solves a much more general problem, the problem of finding a subset of size L that satisfies any given property. We review the algorithm and give a considerably simplified analysis of its query complexity. We present several applications, including two algorithms for the problem of finding an L-clique in an N-vertex graph. One of these algorithms uses O(N^(2L/(L+1))) edge queries, and the other uses \\tilde{O}(N^((5L-2)/(2L+4))), which is an improvement for L <= 5. The latter algorithm generalizes a recent result of Magniez, Santha, and Szegedy, who considered the case L=3 (finding a triangle). We also pose two open problems regarding continuous time quantum walk and lower bounds.
The Subset Sum problem asks whether, given nnn integers and a target, some subset of the integers sums to the target. Its best known worst-case running time is O∗(2n/2)O^*(2^{n/2})O∗(2n/2) (Horowitz and Sahni, 1974), whereas the best quantum upper bound is O∗(2n/3)O^*(2^{n/3})O∗(2n/3) (Bernstein, Jeffery, Lange, and Meurer, 2013). The kkk-SUM problem is a parameterized version of Subset Sum asking whether there are kkk integers that sum to the target. The best classical upper bound for it is O~(n⌈k/2⌉)\widetilde O(n^{\lceil k/2\rceil})O(n⌈k/2⌉), whereas the best quantum running time is O~(nk/3)\widetilde O(n^{k/3})O(nk/3) (Tani, 2009). For random instances, a quantum algorithm with running time O~(nΦk)\widetilde O(n^{Φ_k})O(nΦk​) is known, where Φk=2k−⌊k/7⌋−⌊(k+3)/7⌋6 Φ_k=\frac{2k-\lfloor k/7\rfloor-\lfloor (k+3)/7\rfloor}{6} Φk​=62k−⌊k/7⌋−⌊(k+3)/7⌋​ (Schrottenloher, 2021). We present a new quantum algorithm solving worst-case kkk-SUM in time O~(nΨk)\widetilde O(n^{Ψ_k})O(nΨk​), where Ψk=Φk−[k≡3 mod 7]9−[k≡6 mod 7]18. Ψ_k=Φ_k-\frac{[k\equiv 3\bmod 7]}{9}-\frac{[k\equiv 6\bmod 7]}{18}. Ψk​=Φk​−9[k≡3mod7]​−18[k≡6mod7]​. The algorithm is not only faster for all kkk congruent to 333 or 666 modulo 777, but also gives a worst-case guarantee rather than a guarantee restricted to single-solution random instances. Combining our algorithm for 777-SUM with the standard block reduction technique yields an O∗(22n/7)O^*(2^{2n/7})O∗(22n/7) quantum algorithm for Subset Sum, improving the previously known O∗(2n/3)O^*(2^{n/3})O∗(2n/3) algorithm.