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:0908.1657 · Quantum Information Processing

On zeros of exponential polynomials and quantum algorithms

Yoshitaka Sasaki

Published Oct 21, 2009• 4 citations
arXivHTMLPDF
DOI
10.1007/s11128-009-0148-3

Related papers

Exponential speedup of quantum newton optimization algorithm for general polynomials

Heng Fan

Science China Physics Mechanics and Astronomy•Aug 27, 2021•3 citations

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 +2 more

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).

quant-pharXiv:2609.40321•Oct 1, 2026•1 citation

On exponential polynomials and quantum computing

Yasuo Ohno, Yoshitaka Sasaki, Chika Yamazaki

We calculate the zeros of an exponential polynomial of three variables by a classical algorithm and quantum algorithms which are based on the method of van Dam and Shparlinski, they treated the case of two variables, and compare with the time complexity of those cases. Further we compare the case of van Dam and Shparlinski with our case by considering the ratio (classical/quantum) of the time complexity. Then we can observe the ratio decreases.

arXiv:0908.1027•Aug 7, 2009•1 citation

ON 3-VARIABLE EXPONENTIAL POLYNOMIALS AND QUANTUM ALGORITHMS

Yasuo Ohno, Yoshitaka Sasaki, Chika Yamazaki

•Jul 16, 2012•0 citations

Robust Polynomials and Quantum Algorithms

Harry Buhrman, Ilan Newman, Hein Röhrig +1 more

Lecture notes in computer science•Jan 1, 2005•16 citations

Robust Polynomials and Quantum Algorithms

Harry Buhrman, Ilan Newman, Hein Röhrig +1 more

arXiv:quant-ph/0309220•Theory of Computing Systems•Jun 1, 2007•67 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).