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:2609.40321

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

quant-phcs.CRcs.DSSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

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 $ε>0$, our quantum algorithm solves $\mathbb{F}_3$-subset sum in polynomial time with $m=ε\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).

Related papers

On learning linear functions from subset and its applications in quantum computing

Gábor Ivanyos, Anupam Prakash, Miklós Sántha

Let $\mathbb{F}_q$ be the finite field of size $q$ and let $\ell: \mathbb{F}_q^n \to \mathbb{F}_q$ be a linear function. We introduce the {\em Learning From Subset} problem LFS$(q,n,d)$ of learning $\ell$, given samples $u \in \mathbb{F}_q^n$ from a special distribution depending on $\ell$: the probability of sampling $u$ is a function of $\ell(u)$ and is non zero for at most $d$ values of $\ell(u)$. We provide a randomized algorithm for LFS$(q,n,d)$ with sample complexity $(n+d)^{O(d)}$ and running time polynomial in $\log q$ and $(n+d)^{O(d)}$. Our algorithm generalizes and improves upon previous results \cite{Friedl, Ivanyos} that had provided algorithms for LFS$(q,n,q-1)$ with running time $(n+q)^{O(q)}$. We further present applications of our result to the {\em Hidden Multiple Shift} problem HMS$(q,n,r)$ in quantum computation where the goal is to determine the hidden shift $s$ given oracle access to $r$ shifted copies of an injective function $f: \mathbb{Z}_q^n \to \{0, 1\}^l$, that is we can make queries of the form $f_s(x,h) = f(x-hs)$ where $h$ can assume $r$ possible values. We reduce HMS$(q,n,r)$ to LFS$(q,n, q-r+1)$ to obtain a polynomial time algorithm for HMS$(q,n,r)$ when $q=n^{O(1)}$ is prime and $q-r=O(1)$. The best known algorithms \cite{CD07, Friedl} for HMS$(q,n,r)$ with these parameters require exponential time.

arXiv:1806.09660•Jun 25, 2018•1 citation

No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore

Robin Kothari, Ryan O’Donnell, Kewen Wu

In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the average-case $\ell_\infty$-Short Integer Solution ($\mathrm{SIS}^\infty$) problem, in a parameter range outside the normal range of cryptographic interest, but still with no known efficient classical algorithm. This was particularly exciting since $\mathrm{SIS}^\infty$ is a simple problem without structure, and their algorithmic techniques were different from those used in prior exponential quantum speedups. We present efficient classical algorithms for all of the $\mathrm{SIS}^\infty$ and (more general) Constrained Integer Solution problems studied in their paper, showing there is no exponential quantum speedup anymore.

arXiv:2510.07515•Oct 8, 2025•0 citations

An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems

Allan Grønlund, Kasper Green Larsen

Achieving a provable exponential quantum speedup for an important machine learning task has been a central research goal since the seminal HHL quantum algorithm for solving linear systems and the subsequent quantum recommender systems algorithm by Kerenidis and Prakash. These algorithms were initially believed to be strong candidates for exponential speedups, but a lower bound ruling out similar classical improvements remained absent. In breakthrough work by Tang, it was demonstrated that this lack of progress in classical lower bounds was for good reasons. Concretely, she gave a classical counterpart of the quantum recommender systems algorithm, reducing the quantum advantage to a mere polynomial. Her approach is quite general and was named quantum-inspired classical algorithms. Since then, almost all the initially exponential quantum machine learning speedups have been reduced to polynomial via new quantum-inspired classical algorithms. From the current state-of-affairs, it is unclear whether we can hope for exponential quantum speedups for any natural machine learning task. In this work, we present the first such provable exponential separation between quantum and quantum-inspired classical algorithms for the basic problem of solving a linear system when the input matrix is well-conditioned and has sparse rows and columns.

arXiv:2411.02087•Nov 4, 2024•1 citation

Towards An Implementation of the Subset-sum Problem on the IBM Quantum Experience

David Gunter, Toks Adedoyin

In seeking out an algorithm to test out the capability of the IBM Quantum Experience quantum computer, we were given a review paper covering various algorithms for solving the subset-sum problem, including both classical and quantum algorithms. The paper went on to present a novel algorithm that beat the previous best algorithm known at the time. The complex nature of the algorithm made it difficult to see a path for implementation on the Quantum Experience machine and the exponential cost - only slightly better than the best classical algorithm - left us looking for a different approach for solving this problem. We present here a new quantum algorithm for solving the subset-sum problem that for many cases should lead to O(poly(n))-time to solution. The work is reminiscent of the verification procedure used in a polynomial-time algorithm for the quantum Arthur-Merlin games presented elsewhere, where the use of a quantum binary search to find a maximum eigenvalue in the final output stage has been adapted to the subset-sum problem as in another paper.

arXiv:1912.03254•Dec 4, 2019•1 citation

No Exponential Quantum Speedup for SIS∞ Anymore

Robin Kothari, Ryan O’Donnell, Kewen Wu

In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the average-case ℓ∞-Short Integer Solution (SIS∞) problem, in a parameter range outside the normal range of cryptographic interest, but still with no known efficient classical algorithm. This was particularly exciting since SIS∞ is a simple problem without structure, and their algorithmic techniques were different from those used in prior exponential quantum speedups.

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2026•1 citation

On Learning Linear Functions from Subset and Its Applications in Quantum Computing

Fernando G. S. L. Brandão, Kalev, Amir, Tongyang Li +3 more

Let F_{q} be the finite field of size q and let l: F_{q}^{n} -> F_{q} be a linear function. We introduce the Learning From Subset problem LFS(q,n,d) of learning l, given samples u in F_{q}^{n} from a special distribution depending on l: the probability of sampling u is a function of l(u) and is non zero for at most d values of l(u). We provide a randomized algorithm for LFS(q,n,d) with sample complexity (n+d)^{O(d)} and running time polynomial in log q and (n+d)^{O(d)}. Our algorithm generalizes and improves upon previous results [Friedl et al., 2014; Gábor Ivanyos, 2008] that had provided algorithms for LFS(q,n,q-1) with running time (n+q)^{O(q)}. We further present applications of our result to the Hidden Multiple Shift problem HMS(q,n,r) in quantum computation where the goal is to determine the hidden shift s given oracle access to r shifted copies of an injective function f: Z_{q}^{n} -> {0, 1}^{l}, that is we can make queries of the form f_{s}(x,h) = f(x-hs) where h can assume r possible values. We reduce HMS(q,n,r) to LFS(q,n, q-r+1) to obtain a polynomial time algorithm for HMS(q,n,r) when q=n^{O(1)} is prime and q-r=O(1). The best known algorithms [Andrew M. Childs and Wim van Dam, 2007; Friedl et al., 2014] for HMS(q,n,r) with these parameters require exponential time.

arXiv:1710.02581•Leibniz international proceedings in informatics•Oct 6, 2017•49 citations
Exponential quantum speedup for F3n\mathbb{F}_3^nF3n​-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
We study vector subset sum over F3n\mathbb{F}_3^nF3n​: given mmm random vectors from F3n\mathbb{F}_3^nF3n​, find a nonempty subset that sums to zero; the smaller mmm, 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≈n2/2m\approx n^2/2m≈n2/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≈n2/3m \approx n^2/3m≈n2/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 ε>0ε>0ε>0, our quantum algorithm solves F3\mathbb{F}_3F3​-subset sum in polynomial time with m=ε⋅n2m=ε\cdot n^2m=ε⋅n2 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).
Let Fq\mathbb{F}_qFq​ be the finite field of size qqq and let ℓ:Fqn→Fq\ell: \mathbb{F}_q^n \to \mathbb{F}_qℓ:Fqn​→Fq​ be a linear function. We introduce the {\em Learning From Subset} problem LFS(q,n,d)(q,n,d)(q,n,d) of learning ℓ\ellℓ, given samples u∈Fqnu \in \mathbb{F}_q^nu∈Fqn​ from a special distribution depending on ℓ\ellℓ: the probability of sampling uuu is a function of ℓ(u)\ell(u)ℓ(u) and is non zero for at most ddd values of ℓ(u)\ell(u)ℓ(u). We provide a randomized algorithm for LFS(q,n,d)(q,n,d)(q,n,d) with sample complexity (n+d)O(d)(n+d)^{O(d)}(n+d)O(d) and running time polynomial in log⁡q\log qlogq and (n+d)O(d)(n+d)^{O(d)}(n+d)O(d). Our algorithm generalizes and improves upon previous results \cite{Friedl, Ivanyos} that had provided algorithms for LFS(q,n,q−1)(q,n,q-1)(q,n,q−1) with running time (n+q)O(q)(n+q)^{O(q)}(n+q)O(q). We further present applications of our result to the {\em Hidden Multiple Shift} problem HMS(q,n,r)(q,n,r)(q,n,r) in quantum computation where the goal is to determine the hidden shift sss given oracle access to rrr shifted copies of an injective function f:Zqn→{0,1}lf: \mathbb{Z}_q^n \to \{0, 1\}^lf:Zqn​→{0,1}l, that is we can make queries of the form fs(x,h)=f(x−hs)f_s(x,h) = f(x-hs)fs​(x,h)=f(x−hs) where hhh can assume rrr possible values. We reduce HMS(q,n,r)(q,n,r)(q,n,r) to LFS(q,n,q−r+1)(q,n, q-r+1)(q,n,q−r+1) to obtain a polynomial time algorithm for HMS(q,n,r)(q,n,r)(q,n,r) when q=nO(1)q=n^{O(1)}q=nO(1) is prime and q−r=O(1)q-r=O(1)q−r=O(1). The best known algorithms \cite{CD07, Friedl} for HMS(q,n,r)(q,n,r)(q,n,r) with these parameters require exponential time.
No exponential quantum speedup for SIS∞\mathrm{SIS}^\inftySIS∞ anymore
In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the average-case ℓ∞\ell_\inftyℓ∞​-Short Integer Solution (SIS∞\mathrm{SIS}^\inftySIS∞) problem, in a parameter range outside the normal range of cryptographic interest, but still with no known efficient classical algorithm. This was particularly exciting since SIS∞\mathrm{SIS}^\inftySIS∞ is a simple problem without structure, and their algorithmic techniques were different from those used in prior exponential quantum speedups. We present efficient classical algorithms for all of the SIS∞\mathrm{SIS}^\inftySIS∞ and (more general) Constrained Integer Solution problems studied in their paper, showing there is no exponential quantum speedup anymore.
Achieving a provable exponential quantum speedup for an important machine learning task has been a central research goal since the seminal HHL quantum algorithm for solving linear systems and the subsequent quantum recommender systems algorithm by Kerenidis and Prakash. These algorithms were initially believed to be strong candidates for exponential speedups, but a lower bound ruling out similar classical improvements remained absent. In breakthrough work by Tang, it was demonstrated that this lack of progress in classical lower bounds was for good reasons. Concretely, she gave a classical counterpart of the quantum recommender systems algorithm, reducing the quantum advantage to a mere polynomial. Her approach is quite general and was named quantum-inspired classical algorithms. Since then, almost all the initially exponential quantum machine learning speedups have been reduced to polynomial via new quantum-inspired classical algorithms. From the current state-of-affairs, it is unclear whether we can hope for exponential quantum speedups for any natural machine learning task. In this work, we present the first such provable exponential separation between quantum and quantum-inspired classical algorithms for the basic problem of solving a linear system when the input matrix is well-conditioned and has sparse rows and columns.
In seeking out an algorithm to test out the capability of the IBM Quantum Experience quantum computer, we were given a review paper covering various algorithms for solving the subset-sum problem, including both classical and quantum algorithms. The paper went on to present a novel algorithm that beat the previous best algorithm known at the time. The complex nature of the algorithm made it difficult to see a path for implementation on the Quantum Experience machine and the exponential cost - only slightly better than the best classical algorithm - left us looking for a different approach for solving this problem. We present here a new quantum algorithm for solving the subset-sum problem that for many cases should lead to O(poly(n))-time to solution. The work is reminiscent of the verification procedure used in a polynomial-time algorithm for the quantum Arthur-Merlin games presented elsewhere, where the use of a quantum binary search to find a maximum eigenvalue in the final output stage has been adapted to the subset-sum problem as in another paper.
Let F_{q} be the finite field of size q and let l: F_{q}^{n} -> F_{q} be a linear function. We introduce the Learning From Subset problem LFS(q,n,d) of learning l, given samples u in F_{q}^{n} from a special distribution depending on l: the probability of sampling u is a function of l(u) and is non zero for at most d values of l(u). We provide a randomized algorithm for LFS(q,n,d) with sample complexity (n+d)^{O(d)} and running time polynomial in log q and (n+d)^{O(d)}. Our algorithm generalizes and improves upon previous results [Friedl et al., 2014; Gábor Ivanyos, 2008] that had provided algorithms for LFS(q,n,q-1) with running time (n+q)^{O(q)}. We further present applications of our result to the Hidden Multiple Shift problem HMS(q,n,r) in quantum computation where the goal is to determine the hidden shift s given oracle access to r shifted copies of an injective function f: Z_{q}^{n} -> {0, 1}^{l}, that is we can make queries of the form f_{s}(x,h) = f(x-hs) where h can assume r possible values. We reduce HMS(q,n,r) to LFS(q,n, q-r+1) to obtain a polynomial time algorithm for HMS(q,n,r) when q=n^{O(1)} is prime and q-r=O(1). The best known algorithms [Andrew M. Childs and Wim van Dam, 2007; Friedl et al., 2014] for HMS(q,n,r) with these parameters require exponential time.