{"id":"a3853853-1dd4-42ef-811c-e250b925f9cb","arxiv_id":"2608.07309","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A quantum walk over randomly sampled subset pairs yields a worst-case O~(n^{2k/7}) algorithm for k-SUM and an O^*(2^{2n/7}) algorithm for Subset Sum.","lead":"The paper gives a new quantum algorithm for k-SUM whose worst-case exponent beats the previous best for every k>3, and uses it to solve Subset Sum in quantum time 2^{2n/7}. A generalist should care because this improves long-standing upper bounds for two foundational NP-hard problems and touches post-quantum cryptography.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 3.2 defines m=floor(n^{r/2}) while Eqs. (1) and Section 3.4 use m=n^r; the runtime claim only follows for m=n^r.","rationale":"The paper presents a coherent new worst-case quantum algorithm for k-SUM with exponent Psi_k, improving on Tani for all k>3 and yielding O^*(2^{2n/7}) for Subset Sum via the standard block reduction. The overall architecture is plausible and the components (four-block decomposition, random-prime filtering, quantum walk on Johnson graphs, claw finding) fit together. The most concrete obstruction to verifying the central claim is the inconsistent definition of m: Section 3.2 says m=floor(n^{r/2}), while the subsequent calculations require m=n^r. This is a fixable typo rather than a deep flaw, but it is load-bearing because the runtime exponent depends directly on m. Lemma 3.1 (the random-prime filtering step) was also examined closely: the probability bound via Proposition 2.3 is sound, the union bound over the 2m sampled tuples is valid, and the conclusion that a constant fraction of vertices are marked follows. Thus no fatal error was found in the argument. The reader's CONDITIONAL verdict is appropriate: the proof needs a small correction but the central claim survives once the typo is fixed. Agreement with the reader is partial because the reader's weakest_assumption focused on Lemma 3.1, whereas this stress-test identifies the m inconsistency as the primary load-bearing issue; however, the reader's rationale did correctly mention this inconsistency as well.","tokens_in":13194,"tokens_out":41866,"duration_ms":348831,"concrete_test":"Recompute the marked fraction and total time using m = floor(n^{r/2}) as written in Section 3.2. For k=7 (j=0, d=1, ell=3, k2=k4=2, r=2), verify that the resulting exponent is n^{2.5}, not the claimed Psi_7 = 2. Then replace the definition with m = n^r (with flooring as appropriate) and confirm that Eq. (1), the runtime expression, and Table 1 all become consistent. This one-line correction would settle the concern.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central runtime claim (Theorem 1.2) depends on the sample size m for the subsets S2,S4. Section 3.2 sets m = floor(n^{r/2}), but Equation (1) and the running-time analysis in Section 3.4 implicitly use m = n^r. In particular, Eq. (1) writes |V*|/|V(G)| = m^2/n^{k2+k4} = Omega(n^{2r-k2-k4}), which is valid only when m = n^r; the setup cost T_set = O~(n^r) and the check time T_chk = O~(n^{(k1+k3)/3+r/2}) (from sqrt(p) with p ~ m log^2 n) also assume m = n^r. If the literal definition m = n^{r/2} were used, the marked fraction would be only n^{r-k2-k4}, so 1/sqrt(mu) = n^{(k2+k4-r)/2}, and for k=7 (r=2, k2=k4=2, ell=3) the total time would be O~(n^{2.5}) instead of the claimed n^2. Since Table 1 and the final formula are consistent only with m = n^r, the Section 3.2 definition is a typo. This is load-bearing because a reader cannot verify the proof without correcting it, and the error is in the central parameter of the construction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a new quantum algorithm for worst-case k-SUM running in time O~(n^{Psi_k}), where Psi_k = Phi_k - [k≡3 mod 7]/9 - [k≡6 mod 7]/18, improving over Tani's O~(n^{k/3}) for every k>3 and over Schrottenloher's random-instance bound for k≡3,6 mod 7. The algorithm partitions the k lists into four blocks, samples m-element subsets from the two larger blocks, filters by a random prime, and searches with a quantum walk on a product of Johnson graphs, with Claw Finding inside the vertex check. The authors combine the 7-SUM case with the standard block reduction to derive an O*(2^{2n/7}) quantum algorithm for Subset Sum, improving the previous O*(2^{n/3}), and also give an application to Pigeonhole Modular Equal Subset Sum. The proof structure is a correctness proof, a random-prime isolation lemma, and a parameter-balanced runtime analysis, with the final exponents summarized in Table 1.","tokens_in":13355,"tokens_out":24760,"duration_ms":211482,"significance":"If the main theorem is correct after fixing the parameter definition, this is a notable advance: it is the first worst-case quantum k-SUM algorithm to beat Tani's n^{k/3} for all k>3, and it improves the quantum Subset Sum bound from 2^{n/3} to 2^{2n/7}. The exponent Psi_k is derived analytically from the algorithm's own parameters with no fitted constants, and the four-block decomposition with random-prime bucket isolation and a quantum walk on two Johnson graphs is a clean and apparently new alternative to the merging-tree paradigm. The paper also gives a self-contained marked-fraction calculation and a concrete application to a modular pigeonhole variant. However, the current text contains a load-bearing inconsistency in the definition of the sample size m, and the bit-length reduction invoked in Lemma 3.1 is only cited, not stated; both points must be addressed before the proof is verifiable.","major_comments":[{"comment":"Section 3.2 and Algorithm 1 define m = floor(n^{r/2}), but every subsequent calculation uses m = Theta(n^r). In particular, Eq. (1) asserts |V*|/|V(G)| = m^2/n^{k2+k4} = Omega(n^{2r-k2-k4}), which is valid only when m = Omega(n^r); with m = n^{r/2} the marked fraction would be n^{r-k2-k4}. Likewise, Section 3.4 uses T_set = O~(n^r) and T_chk = O~(n^{(k1+k3)/3+r/2}) from p ~ m log^2 n, both assuming m = n^r. Under the literal definition, for k=7 (r=2, k2=k4=2, ell=3) the total walk time would be O~(n^{2.5}) rather than the claimed O~(n^2), so Theorem 1.2 and Table 1 are not derivable from the text as written. The intended parameter is evidently m = Theta(n^r); the definition should be corrected, for example to m = floor(c n^r) for a constant c<1. If m = n^r is used with r = k2, which occurs in several rows of Table 1, then m = |X_i| and the stated Johnson-graph condition m <= |X|/2 is violated; the corrected definition should also ensure m <= |X_i|/2.","section":"Section 3.2 / Eq. (1) / Section 3.4 / Algorithm 1"},{"comment":"The proof of Lemma 3.1 assumes log|Sigma_i(x) - z*_i| = O(log n), i.e., that all input integers have O(k log n) bits. The only support for this is the one-sentence assertion in Section 2.1 that this can be achieved by 'the standard fingerprinting technique [ALW14]', but no precise statement of the reduction or its error probability is given. A direct modular reduction by a random prime of size n^{O(1)} has a collision probability for a fixed nonzero difference proportional to log|Sigma_i(x)-z*_i| / n^{O(1)}, which is not automatically O(1/(m log n)) if the original integers have large bit-length. The authors should state the exact fingerprinting lemma they are invoking and explain how it preserves both directions of the k-SUM decision problem; otherwise the worst-case claim in Theorem 1.2 is not fully supported.","section":"Section 2.1 / Lemma 3.1"}],"minor_comments":[{"comment":"The equality in the displayed total running time drops the contribution O~(n^{k2-r/2}) coming from the (1/sqrt(mu)) sqrt(m) T_upd term; the omitted term is dominated by the displayed max for the parameter choices in Table 1, but this should be stated explicitly in the text.","section":"Section 3.4"},{"comment":"The informal description says the walk stores one canonical representative per residue bucket, while the formal definition of D_{v,i} stores all entries in the bucket and R_{v,i}(s) returns the minimum; these two descriptions should be reconciled.","section":"Section 3.2"},{"comment":"The running time in the statement of Theorem 4.2 is printed as O*(32n/7); it should be O*(3^{2n/7}) to match the proof, where M = 3^{ceil(n/7)} and the total is O(n^2) * O~(M^2).","section":"Theorem 4.2"},{"comment":"The sentence 'The algorithm is not only faster for all k congruent to 3 or 6 modulo 7' is imprecise: Theorem 1.2 improves Tani's n^{k/3} for every k>3, and improves Schrottenloher's Phi_k only for k ≡ 3 or 6 mod 7; the sentence should be rephrased to avoid implying the only improvements are those residue classes.","section":"Section 1"}],"recommendation":"major_revision","confidential_remarks":"The m-definition inconsistency in Section 3.2 appears to be a correctable typo rather than a fundamental flaw: the algorithm's intended parameter is m = Theta(n^r), and with that correction the runtime analysis and Table 1 are internally consistent. The paper would be a strong contribution once the sample-size definition is fixed and the bit-length reduction in Lemma 3.1 is stated with enough precision to be verifiable. I therefore recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real result—worst-case quantum k-SUM in about n^{2k/7}, and Subset Sum in 2^{2n/7}—and the proof is mostly sound. The one thing that needs fixing before I'd trust the write-up: Section 3.2 defines m = floor(n^{r/2}), but every equation that matters uses m = n^r. Equation (1), the T_set/T_chk values, and Table 1 all require m = n^r. The stress-test note did the arithmetic: if you take the literal definition, the k=7 exponent degrades to n^{2.5}. I'm fairly confident it's a typo rather than a real flaw, because the entire analysis after Section 3.2 consistently uses m = n^r, and the optimized parameters in Table 1 only make sense that way. A referee should catch it; it's load-bearing.\n\nWhat's new: the four-block decomposition with a random-prime residue filter and a quantum walk over sampled subset pairs is genuinely new, and it converts Schrottenloher's random-instance-only bound into a worst-case guarantee while beating Tani's n^{k/3} for all k>3. The correctness argument (Lemma 3.1) and the runtime balance in Table 1 check out under the m=n^r reading. The application to Subset Sum via block reduction is standard and gives the stated 2^{2n/7}.\n\nOne more soft spot, minor: for several parameter choices (e.g., k=7), r = k2, so m = |X2|, and the Johnson graph degenerates to a single vertex. The paper doesn't discuss this, but the walk time formula still gives the right bound if you treat that case separately. It's a technical footnote, not a structural gap.\n\nThe citation pattern is fine, no circularity—the reference to Schrottenloher's Psi_k is purely a benchmark comparison. No code, but that's normal for this kind of theory.\n\nWho should read it: anyone working on quantum algorithms for subset-sum-type problems, and the fine-grained complexity crowd will want to know about the Subset Sum improvement. It deserves a serious referee. The typo will force a revision, but the result is important enough to justify the time.","headline":"Real improvement in quantum k-SUM/Subset Sum with a fixable but load-bearing typo in the main parameter.","tokens_in":631,"tokens_out":763,"would_cite":true,"duration_ms":78704,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"A single four-block quantum walk beats the previous worst-case k-SUM bound for every k>3, yielding quantum Subset Sum in O^*(2^{2n/7}).","keywords":["k-SUM","Subset Sum","quantum walk","Johnson graph","Claw Finding","random prime filtering","meet-in-the-middle"],"falsifier":"Construct a family of k-SUM instances where the inputs have bit-length much larger than O(k\\log n), say ~$n^{{100}}$, and test whether a random prime in [m\\$log^{2}$ n, 2m\\$log^{2}$ n] can fail to isolate a solution with probability bounded away from a constant. A concrete counterexample would be a set of sums where a nonzero difference is divisible by many primes in that interval, violating the O(\\log|z|/M) bound used in the proof.","tokens_in":12848,"feed_emoji":"🧮","tokens_out":6069,"duration_ms":51704,"temperature":0.7,"pith_summary":"This paper claims a new quantum algorithm for the worst-case k-SUM problem, not just for random instances. The central result is that k-SUM can be solved in quantum time O~($n^{{\\Psi_k}}$) for every k>3, where \\Psi_k = \\Phi_k minus corrections for k congruent to 3 or 6 modulo 7. This improves the previous worst-case quantum bound O~($n^{{k/3}}$) and, asymptotically, the exponent is 2k/7 + O(1). The same machinery applied to the case k=7 gives a quantum Subset Sum algorithm running in O^*($2^{{2n/7}}$), improving the earlier O^*($2^{{n/3}}$). A sympathetic reader should care because this is a concrete advance on two central NP-complete searching problems and transfers the known random-instance speedup to all instances.","feed_headline":"Quantum walk cracks worst-case k-SUM near n^{2k/7}","feed_subtitle":"Same method drops quantum Subset Sum from 2^{n/3} to 2^{2n/7}.","key_machinery":"The core mechanism is a quantum walk on the Johnson graph J(X_2,m) \\times J(X_4,m): the k input lists are grouped into four consecutive blocks of sizes roughly (3k/14, 2k/7, 3k/14, 2k/7), and the walk searches over m-element samples S_2 and S_4 drawn from the two large block-tuple sets. A random prime p is chosen from [m\\$log^{2}$ n, 2m\\$log^{2}$ n], and each sampled vertex stores dictionaries of sums grouped by their residues modulo p. To check a vertex, the algorithm uses quantum search over residues q and then Claw Finding on the reduced left- and right-hand lists. The random prime ensures that, with constant probability, a fixed solution's two block sums are exposed in their residue buckets, giving a constant fraction of marked walk vertices.","core_discovery":"The paper's central claim is Theorem 1.2: for every integer k>3, worst-case k-SUM can be solved in quantum time O~($n^{{\\Psi_k}}$), where \\Psi_k = (2k - \\lfloor k/7 \\rfloor - \\lfloor (k+3)/7 \\rfloor)/6 - [k\\equiv 3 \\bmod 7]/9 - [k\\equiv 6 \\bmod 7]/18. This is a worst-case upper bound, improving Tani's O~($n^{{k/3}}$) for every k>3, and it matches or improves the random-instance exponent \\Phi_k for all k. A corollary is that the Subset Sum problem can be solved in quantum time O^*($2^{{2n/7}}$), improving the previously known O^*($2^{{n/3}}$). The algorithm also gives a positive answer for the Pigeonhole Modular Equal Subset Sum problem in quantum time O^*($3^{{2n/7}}$).","pith_inferences":["The same four-block walk with a random-prime filter may transfer to k-XOR-type problems, where comparable exponents are currently known only for random instances.","The residue-class optimization (mod 7) suggests that further tuning, perhaps with other block counts or modulus classes, could shave more off the exponent for specific values of k.","Replacing the final Claw Finding step with a faster matching routine might lower the (k_1+k_3)/3 contribution and improve the exponent for small k.","If the block-reduction idea extends to more than seven blocks, the quantum exponent for Subset Sum might approach 1/4, though this is not claimed by the paper."],"forward_implications":["For every k>3, the worst-case quantum running time of k-SUM becomes O~(n^{\\Psi_k}), strictly below the previous O~(n^{k/3}).","Quantum Subset Sum can now be solved in O^*(2^{2n/7}), improving the prior O^*(2^{n/3}).","Using k=7 in the block reduction gives O^*(3^{2n/7}) for Pigeonhole Modular Equal Subset Sum.","The improvement holds for all worst-case instances with a solution, not only for single-solution random instances.","The exponent \\Psi_k matches the earlier random-instance exponent \\Phi_k for k not congruent to 3 or 6 mod 7, and improves it for k congruent to 3 or 6 mod 7."],"supporting_citations":[{"why":"Supplies the classical meet-in-the-middle baseline and the block-reduction starting point that the new algorithm improves on.","marker":"[HS74]"},{"why":"Gives the previous quantum Subset Sum upper bound O*(2^{n/3}) that the paper improves.","marker":"[BJLM13]"},{"why":"Defines the random-instance exponent \\Phi_k that the new worst-case exponent \\Psi_k refines.","marker":"[Sch21]"},{"why":"Provides the Claw Finding quantum algorithm used as the final search primitive inside the vertex check.","marker":"[Tan09]"},{"why":"Supplies the coherent dictionary construction and lookup primitives used to store residue buckets at walk vertices.","marker":"[Amb07]"},{"why":"The quantum walk search theorem that converts marked fraction, update cost, and check cost into total running time.","marker":"[Sze04]"},{"why":"Refines the quantum walk search framework used for the running-time analysis.","marker":"[MNRS11]"},{"why":"Bounds the spectral gap of the lazy Johnson graph walk, which determines the number of walk steps needed.","marker":"[KT17]"},{"why":"The fingerprinting technique that justifies assuming all input integers have bit-length O(k log n).","marker":"[ALW14]"}],"fun_headline_variants":["Subset Sum quantum time cut to 2^{2n/7} from 2^{n/3}","Worst-case k-SUM quantum algorithm beats classical for every k","Quantum algorithm solves Subset Sum in 2^{2n/7}","Worst-case k-SUM quantum time improved for every k>3","Quantum walk turns random-instance k-SUM speedup into worst-case"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a uniformly random prime p in the interval [m\\$log^{2}$ n, 2m\\$log^{2}$ n] divides any nonzero difference of two relevant sums with probability O(1/(m\\log n)), which relies on all input integers having bit-length O(k\\log n); if that fails, the constant marked fraction of walk vertices degrades.","fun_headline_variants_meta":{"raw":{"variants":["Subset Sum quantum time cut to 2^{2n/7} from 2^{n/3}","Worst-case k-SUM quantum algorithm beats classical for every k","Quantum algorithm solves Subset Sum in 2^{2n/7}","Worst-case k-SUM quantum time improved for every k>3","Quantum walk turns random-instance k-SUM speedup into worst-case"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001535,"raw_usage":{"total_tokens":6234,"prompt_tokens":1125,"completion_tokens":5109,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":741,"completion_tokens_details":{"reasoning_tokens":5004}},"tokens_in":741,"tokens_out":5109,"duration_ms":33756,"temperature":1.0,"reasoning_tokens":5004,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T10:33:58.420358+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a family of k-SUM instances where the inputs have bit-length much larger than O(k\\log n), say ~$n^{{100}}$, and test whether a random prime in [m\\$log^{2}$ n, 2m\\$log^{2}$ n] can fail to isolate a solution with probability bounded away from a constant. A concrete counterexample would be a set of sums where a nonzero difference is divisible by many primes in that interval, violating the O(\\log|z|/M) bound used in the proof.","supporting_citations":[],"review_version":1}