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

ON 3-VARIABLE EXPONENTIAL POLYNOMIALS AND QUANTUM ALGORITHMS

Yasuo Ohno, Yoshitaka Sasaki, Chika Yamazaki

•Jul 16, 2012•0 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

Robust Polynomials and Quantum Algorithms

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

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

Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler

Zhengfeng Ji, Zhihan Jin, Pinyan Lu

The algorithm and complexity of approximating the permanent of a matrix is an extensively studied topic. Recently, its connection with quantum supremacy and more specifically BosonSampling draws a special attention to the average-case approximation problem of the permanent of random matrices with zero or small mean value for each entry. Eldar and Mehraban (FOCS 2018) gave a quasi-polynomial time algorithm for random matrices with mean at least 1/polyloglog(n). In this paper, we improve the result by designing a deterministic quasi-polynomial time algorithm and a PTAS for random matrices whose module of mean is at least 1/ polylog(n). We note that if the algorithm can be further improved to work with a mean value that is a sufficiently small 1/poly(n), it will disprove a central conjecture for quantum supremacy. Our algorithm is also much simpler and has a better and flexible trade-off for running time. The running time can be quasi-polynomial in both n and 1/∊, or PTAS (polynomial in n but exponential in 1/∊), where ∊ is the approximation parameter.

arXiv:1911.11962•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2021•2 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).
The algorithm and complexity of approximating the permanent of a matrix is an extensively studied topic. Recently, its connection with quantum supremacy and more specifically BosonSampling draws a special attention to the average-case approximation problem of the permanent of random matrices with zero or small mean value for each entry. Eldar and Mehraban (FOCS 2018) gave a quasi-polynomial time algorithm for random matrices with mean at least 1/polyloglog(n). In this paper, we improve the result by designing a deterministic quasi-polynomial time algorithm and a PTAS for random matrices whose module of mean is at least 1/ polylog(n). We note that if the algorithm can be further improved to work with a mean value that is a sufficiently small 1/poly(n), it will disprove a central conjecture for quantum supremacy. Our algorithm is also much simpler and has a better and flexible trade-off for running time. The running time can be quasi-polynomial in both n and 1/∊, or PTAS (polynomial in n but exponential in 1/∊), where ∊ is the approximation parameter.