PaperlayerView exact revision on arXiv

Source-linked AI summary

Exponential quantum speedup for $\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE

Robin Kothari, Tony Metger, Ryan O'Donnell, Noah Shutty, Kewen Wu

arXiv:2609.40321v1quant-phcs.CRcs.DS

TL;DR

For 3-Subset-Sum, the improved classical constant ε=0.1022 leaves open whether an exponential quantum speedup is possible at smaller ε. The paper proves a deterministic classical attack for binary-error LWE and uses the Chen–Liu–Zhandry quantum reduction to obtain F3 subset-sum algorithms. For every fixed ε>0, the quantum algorithm solves F3 subset sum with m=ε·n², while the classical algorithm achieves ε=0.1022.

  • Problem

    For 3-Subset-Sum, the improved classical constant ε=0.1022 leaves open whether an exponential quantum speedup is possible at smaller ε.

    Source: §1 · p. 4

  • Method

    The paper proves a deterministic classical attack for binary-error LWE and uses the Chen–Liu–Zhandry quantum reduction to obtain F3 subset-sum algorithms.

    Source: §1 · p. 3

  • Results

    For every fixed ε>0, the quantum algorithm solves F3 subset sum with m=ε·n², while the classical algorithm achieves ε=0.1022.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    The results renew the possibility of an exponential quantum speedup for F3 subset sum at sample counts below the reported classical constant.

    Source: §1 · p. 4

    The classical algorithm achieving ε=0.1022 is not fully described or formally proved in the paper.

    Source: §1.3 · p. 6

Abstract

from arXiv · show

We study vector subset sum over $\mathbb{F}_3^n$: given $m$ random vectors from $\mathbb{F}_3^n$, find a nonempty subset that sums to zero; the smaller $m$, the more difficult it is to find such a subset. Chen, Liu, and Zhandry (EUROCRYPT'22) introduced an efficient quantum algorithm that solves this problem when $m\approx n^2/2$, where a naive classical algorithm would require exponential time. Subsequently, Kothari, O'Donnell, and Wu (STOC'2026) gave an efficient classical algorithm that only requires $m \approx n^2/3$ vectors, thus removing the hope for an exponential quantum advantage in this parameter regime. Using the framework of Chen, Liu, and Zhandry, we give quantum algorithms that require much fewer input vectors, renewing the possibility of an exponential quantum speedup: for any fixed $\epsilon>0$, our quantum algorithm solves $\mathbb{F}_3$-subset sum in polynomial time with $m=\epsilon\cdot n^2$ vectors. More generally, we establish a full sample--time tradeoff that interpolates between exponential and polynomial runtime. The main ingredient is a deterministic classical algorithm for the binary-error Learning-with-Errors problem, which is of independent cryptographic interest. For this, we rigorously establish a sample--time tradeoff that was predicted by earlier algebraic heuristics. For vector subset sums over larger fields, we also significantly improve classical algorithms in Kothari, O'Donnell, and Wu (STOC'2026).

1 Introduction

The paper develops quantum algorithms for average-case F3 subset sum and a deterministic classical decoder for binary-error LWE, with a shared sample–time tradeoff. It also improves classical subset-sum algorithms over larger fields.

1 Introduction

  • The study targets explicit search problems with efficiently checkable solutions, motivated by the limited set of known candidates for exponential quantum speedups.It also connects subset sum to post-quantum cryptography and the study of quantum attacks on related schemes.Source: §1 · p. 3

1.3 Classical algorithms for F𝑛

  • The classical F3 subset-sum algorithm reaches ε=0.1022, suggesting a possible exponential quantum speedup at smaller ε.The paper says this constant came from LLM-assisted optimization and does not provide a complete description or formal proof of the algorithm.Source: §1 · p. 4, §1.3 · p. 6

1.1 Quantum algorithms for average-case F𝑛

  • For any fixed ε, a quantum algorithm for Problem 1.1 smoothly interpolates between the information-theoretic threshold m≈κ⋆·n and prior polynomial-time-solvable threshold m≈n^(2/3), yielding polynomial-time solvability at m=ε·n².Source: §1.1 · p. 4
  • For every m≥κn with κ>log(3), the quantum algorithm succeeds with probability at least 1−2^-Ωκ(m) in time (m/n)^Oκ(⌈n^2/m⌉).The theorem gives a sample–time tradeoff across this range of m.Source: §1.1 · p. 4

1.2 Classical algorithms for Binary-Error LWE over F𝑞

  • The decoder’s recovery guarantee holds for every secret and binary error vector, with probability taken only over the random matrix A.The matrices on which it fails may depend on the secret and error vector.Source: §1.2 · pp. 5–6
  • For every m≥κn with κ>log_q/2(q), a deterministic classical algorithm solves Problem 1.5 with probability at least 1−2^-Ω_{q,κ}(m), in time (m/n)^O_{q,κ}(⌈n²/m⌉).Theorem 1.7 unconditionally proves the semi-regularity-predicted curve in the stronger pointwise sense.Source: §1.2 · p. 6
  • For polynomial-time binary-error LWE attacks, the rigorous sample threshold improves from m≥(κq/2+o(1))n^2 to m≥εn^2 for every constant ε>0.The prior threshold is attributed to.Source: §1.2 · p. 6

1.3 Classical algorithms for F𝑛

  • At η=2^-Ω(n), Theorem 1.10 lowers the n-exponent from 2k+1 to k+1; for worst-case Problem 1.9, Theorem 1.11 replaces the Θ(q log q) exponent with q−1.Source: §1.3 · p. 7

2 Sketch of the Binary-Error LWE analysis

The sketch reduces binary-error LWE to solving quadratic equations over F3 and analyzes the system through its degree of regularity. Bounds on how random linear forms make monomials achievable yield classical algorithms and a sample–time tradeoff.

2.1 Reduction to degree of regularity

  • For solvable quadratic systems over F3, the classical algorithm runs in poly(N_D, m) time, with N_D=(Θ(n/D))^D.Source: §2.1 · p. 9
  • With m≥κn for κ>log_3/2(3), the degree of regularity is bounded with high probability, yielding a polynomial-time algorithm when m=εn² for fixed ε.The sketch gives an O(log(1/ε)/ε) degree-of-regularity bound for constant ε.Source: §2.1 · p. 9, §2.4 · p. 13

2.2 Outline of the degree of regularity bound

  • For fixed degree D, the analysis tracks the codimension of achievable degree-D polynomials and seeks a substantial decrease after each random equation.Source: §2.2 · p. 10
  • The outline’s bound reaches zero remaining dimensions with m=O(n² log(D)/D) samples, except with probability exp(−Ω(m)).Source: §2.2 · p. 10

2.3 First argument: a popular pair of variables

  • A popular pair of variables in many unachievable monomials yields a constant-probability gain of Ω(D²/n²)·h_t dimensions from a random equation.The argument compares four shifted coefficient vectors; at least one gains r/4 dimensions, and each vector is uniformly random.Source: §2.3 · p. 11

2.4 Second argument: Kruskal–Katona

  • The second argument uses incidence-matrix rank and a lexicographic determinant argument to preserve rank despite correction terms, supporting the O(log(1/ε)/ε) regularity bound.The rank bound uses the multiplicity version of Schwartz–Zippel and a Kruskal–Katona argument.Source: §2.4 · pp. 12–13

3 Quantum reduction from F𝑛

The section explains the established [CLZ22] reduction from F3 subset sum to average-case Binary-Error LWE and how a decoder yields a quantum subset-sum algorithm, including when decoding errors occur.

3 Quantum reduction from F𝑛

  • A decoder for average-case Binary-Error LWE over F3 yields a quantum algorithm for average-case F3-Subset-Sum with runtime poly(m, n, T).The reduction is presented as following [CLZ22], not as a new reduction.Source: §3 · p. 13
  • Measuring the prepared state in the computational basis yields a uniformly random signed zero-sum solution.The section focuses on signed-sum, where coefficients are ±1, and relates it to subset-sum, where coefficients are 0 or 1.Source: §3 · p. 13
  • The reduction uses decoder outputs to recover the secret coherently from Binary-Error LWE instances generated from the input vectors.Each error coordinate is chosen uniformly from the two F3 elements unequal to the corresponding inner product.Source: §3 · p. 15

3.1 Allowing decoding errors

  • A perfect decoder is only an idealization because distinct secrets can produce the same observation with different error vectors, though such collisions are highly unlikely.The error analysis therefore handles decoder errors rather than assuming perfect decoding.Source: §3.1 · p. 15, §3 · p. 15
  • Decoder failures contribute an unsuccessful state component whose squared norm equals the decoder's error probability, averaged over A.The successful component differs from the desired coherent sum by missing terms; the squared norm of the combined error term bounds invalid-output probability.Source: §3.1 · p. 16

4 Pointwise Binary-Error LWE via quotient decoding

This section develops quotient-decoding methods for pointwise binary-error LWE, proving a deterministic classical sample–time tradeoff and deriving the quantum algorithm’s runtime and failure bound. Its analysis establishes the required surjectivity condition using martingale analysis, symbolic rank, and multiset shadows.

4.1 The algebraic version of the quotient decoder

  • The binary-error equations define a candidate-secret set whose size equals dim(S/J); when that dimension is 1, the quotient determines each secret coordinate.The equations vanish exactly when each residual is 0 or 1, and the quotient’s evaluation map identifies its dimension with the number of candidates.Source: §4.1 · pp. 17–18

4.2 The algorithmic version of the quotient decoder

  • When Φ_{m,D} is surjective, the decoder computes reduced polynomial remainders and multiplication maps in deterministic polynomial time, then closes valid relations to represent S/J as V/N.The multiplication maps may fail to commute on V, so the algorithm forms a relation space N invariant under those maps before recovering the quotient.Source: §4.2 · pp. 19–21

4.3 Proofs of Theorem 1.7 and Theorem 1.3

  • For 500n ≤ m ≤ n², the surjectivity theorem uses D = ⌈500n²/m⌉; in the proof of Theorem 1.7, nonsurjectivity is an additional failure event beyond nonunique candidates.Theorem 1.7’s candidate-nonuniqueness probability is at most 2^{−Ω_{q,κ}(m)}.Source: §4.3 · p. 22
  • For κ > log_{q/2}(q) and every m ≥ κn, a deterministic classical algorithm solves Problem 1.5 with probability at least 1 − 2^{−Ω_{q,κ}(m)} in time (m/n)^{O_{q,κ}(⌈n²/m⌉)}.The proof combines quotient decoding with the fact that the candidate secret is unique except with probability at most 2^{−Ω_{q,κ}(m)}.Source: §4.3 · p. 22
  • For every m ≥ κn with κ > log(3), the quantum algorithm solves Problem 1.1 with failure at most 2^-Ωκ(m) in time (m/n)^Oκ(⌈n^2/m⌉).For m ≥ 3n, the proof applies the q = 3 classical decoder and Theorem 3.1; for smaller m in the range, it uses exhaustive search.Source: §4.3 · pp. 22–23

4.4 Proof of the probabilistic surjectivity condition

  • For 500n ≤ m ≤ n^2 and D = ⌈500n^2/m⌉, the surjectivity analysis tracks image growth using a coupon-collector-type martingale argument.The proof also bounds failure across disjoint blocks: Item (ii) by e^-m/400 and each block in Item (iii) by e^-n^2/400, then applies a union bound.Source: §4.3 · p. 22, §4.4 · p. 23

4.4.1 From martingale step to symbolic rank

  • For uniformly random L_t, E[X_t | W_t-1] ≥ ρ(W_t-1)/3, relating each martingale step to symbolic rank.The proof uses a nonzero determinant polynomial of degree at most 2ρ and a multiplicity Schwartz-Zippel bound.Source: §4.4.1 · p. 25

4.4.2 From symbolic rank to multiset shadow

  • For lower-bounding ρ(W), one may assume W is spanned by monomial coefficient functionals; this replacement reduces the task to counting monomials in a large family with ℬ-invariant span.Source: §4.4.2 · pp. 26–27

4.4.3 Shadow bounds and putting things together

  • For D ≥ 3 and h = dim(W), the symbolic rank satisfies ρ̄(W) ≥ (h/3)^(1−2/D), using a multiset-shadow bound.The proof also gives 0 ≤ X_t ≤ ρ(W_t-1) and E[X_t | ℱ_t-1] ≥ ρ(W_t-1)/3.Source: §4.4.3 · pp. 28–29

5 Classical average-case F𝑛

The section proves a deterministic classical algorithm for average-case Problem 1.9 that runs in poly(m) time with success probability at least 1 − 2^-Ω(n). Its approach constructs affine reducible vectors and uses them in a recursive solver that reduces dimension.

5 Classical average-case F𝑛

  • A deterministic poly(m)-time algorithm solves average-case Problem 1.9 with probability at least 1 − 2^-Ω(n).The section states that this quadratically improves the results in [KOW26].Source: §5 · p. 29

5.1 Affine reducible vector

  • Affine reducibility generalizes [KOW26] reducibility: every c + a·u must be expressible as a subset-sum of the input vectors.The condition is required for every a in Fq.Source: §5.1 · p. 30
  • From B·m_d independent uniform vectors, a deterministic poly(B, m_d, q)-time construction produces an affine reducible vector with failure probability at most q^2/2^B.The construction first quotients by u, combines disjoint signed-subset zero-sums in the smaller space, then pieces them together.Source: §5.1 · p. 30

5.2 The recursive algorithm

  • The recursive solver uses affine reducibility to reduce dimension, with a total attempt budget and martingale analysis controlling failure.It reserves initial vectors for a basis and recursively solves the target in quotient spaces before completing the subset-sum.Source: §5 · p. 29, §5.2 · pp. 31–32

6 Classical worst-case F𝑛

The section improves a classical worst-case subset-sum bound over larger fields and builds a zero-sum from structured disjoint subset-sums. Its algebraic identity uses rooted spanning trees and the matrix-tree theorem.

6 Classical worst-case F𝑛

  • The classical worst-case algorithm improves the n q log q bound in [IS17] [II24] [KOW26] to n q.The section states that the algorithm is deterministic.Source: §6 · p. 33
  • The algorithm constructs pairwise disjoint subset-sums whose weighted sum vanishes along every coordinate line.This specializes the equation array in [IS17] and simplifies the equation tree in [KOW26].Source: §6 · p. 33

6.1 A zero-sum identity over rooted trees

  • Rooted spanning trees provide the unsigned zero-sum identity, with vanishing guaranteed by the matrix-tree theorem [Cha82].Combining the identity with the disjoint subset-sums yields a nonempty zero-sum subset.Source: §6 · p. 34, §6.1 · p. 35

A Satisfiability of average-case F𝑛

The section establishes a satisfiability threshold for average-case Problem 1.1. Above κ⋆n the instance has a solution with high probability, while below κ⋆n the probability of any solution is exponentially small.

A Satisfiability of average-case F𝑛

C Degree-3 XL experiments

The appendix compares degree-3 XL experiments with a predicted sample threshold for recovering the unique secret. The tested success rates track the prediction, while the paper leaves the resulting conjecture unproved.

C Degree-3 XL experiments

  • Higher-degree XL systems grow too large for enough experiments to draw convincing conclusions, so the appendix focuses on degree 3.Source: C Degree-3 XL experiments · p. 43
  • Degree-3 XL linearizes the equations and their multiples over F3; full column rank is sufficient to recover the secret from the degree-1 coordinates.It performs Gaussian elimination on nonconstant reduced monomials of degree at most 3.Source: C Degree-3 XL experiments · p. 43
  • The predicted sample threshold is a necessary condition for full column rank, and the experiments were reported to align surprisingly well with that prediction.The condition follows from the number of independent rows supplied by the samples.Source: C Degree-3 XL experiments · p. 44
  • Above 99% success occurred at m_pred for tested n not congruent to ±1 mod 6; for n congruent to ±1 mod 6, rates were 69%–86%, and one extra sample yielded 100%.The latter cases occur exactly when n·m_pred = V(n), with no rounding in the prediction.Source: C Degree-3 XL experiments · p. 44
  • The authors conjecture at least 0.99 success at m_pred for n not congruent to ±1 mod 6, and at m_pred + 1 for n congruent to ±1 mod 6.The paper states that its techniques do not establish this conjecture, not even asymptotically at m ≥ (1+o(1))n^2/6.Source: C Degree-3 XL experiments · p. 44
Loading 2609.40321v1…