We give two quantum algorithms for computing (twisted) Kloosterman sums attached to a finite field $\mathbf{F}$ of $q$ elements. The first algorithm computes a quantum state containing, as its coefficients with respect to the standard basis, all Kloosterman sums for $\mathbf{F}$ twisted by a given multiplicative character, and runs in time polynomial in $\log q$. The second algorithm computes a single Kloosterman sum to a prescribed precision, and runs in time quasi-linear in $\sqrt{q}$.
We give two quantum algorithms for computing (twisted) Kloosterman sums attached to a finite field F of q elements. The first algorithm computes a quantum state containing, as its coefficients with respect to the standard basis, all Kloosterman sums for F twisted by a given multiplicative character, and runs in time polynomial in logq. The second algorithm computes a single Kloosterman sum to a prescribed precision, and runs in time quasi-linear in q.
We present an efficient quantum algorithm for estimating Gauss sums over finite fields and finite rings. This is a natural problem as the description of a Gauss sum can be done without reference to a black box function. With a reduction from the discrete logarithm problem to Gauss sum estimation we also give evidence that this problem is hard for classical algorithms. The workings of the quantum algorithm rely on the interaction between the additive characters of the Fourier transform and the multiplicative characters of the Gauss sum.
We study the approximation of the number of solutions of Laurent polynomials over finite fields. For a Laurent polynomial f(x)=∑j=1sajxuj∈Fq[x1±1,…,xn±1], let U be its augmented support matrix whose columns are (1,uj) with rank ρ and N(f):=#{x∈(Fq×)n∣f(x)=0} be its torus point count. Our first main result is a quantum algorithm that outputs N(f) satisfying ∣N(f)−N(f)∣≤εqn+s/2−ρ with success probability 1−δ. Provided that ρ and ∥U∥∞ are bounded, the algorithm runs in both classical bit and quantum gate complexity poly(n,s,logq,1/ε,log(1/δ)). It provides finer resolution than relative-error approximations in general settings. To the best of our knowledge, in the explicit finite-field input model considered here, no previous algorithm achieves this additive accuracy with running time polynomial in logq. Van Dam (arXiv:quant-ph/0405081) conjectured the existence of such an algorithm under the assumption of an oracle reflecting the algebraic properties of the polynomial. In contrast, by exploiting a point-counting formula derived from character sums over finite fields, we develop an alternative approach that efficiently approximates the number of points without assuming the existence of such an oracle. As a second main result, we prove that the same approximation problem becomes #P-hard under randomized polynomial-time Turing reductions when the support matrix U varies freely as part of the input. Thus, taken together, our results clarify how the effectiveness of the quantum approach depends on the tradeoff between the accuracy scale and the support parameters of the input polynomial.
The Subset Sum problem asks whether, given n integers and a target, some subset of the integers sums to the target. Its best known worst-case running time is O∗(2n/2) (Horowitz and Sahni, 1974), whereas the best quantum upper bound is O∗(2n/3) (Bernstein, Jeffery, Lange, and Meurer, 2013). The k-SUM problem is a parameterized version of Subset Sum asking whether there are k integers that sum to the target. The best classical upper bound for it is O(n⌈k/2⌉), whereas the best quantum running time is O(nk/3) (Tani, 2009). For random instances, a quantum algorithm with running time O(nΦk) is known, where Φk=62k−⌊k/7⌋−⌊(k+3)/7⌋ (Schrottenloher, 2021). We present a new quantum algorithm solving worst-case k-SUM in time O(nΨk), where Ψk=Φk−9[k≡3mod7]−18[k≡6mod7]. The algorithm is not only faster for all k congruent to 3 or 6 modulo 7, but also gives a worst-case guarantee rather than a guarantee restricted to single-solution random instances. Combining our algorithm for 7-SUM with the standard block reduction technique yields an O∗(22n/7) quantum algorithm for Subset Sum, improving the previously known O∗(2n/3) algorithm.
Two manuscripts on the de-oracleization of Forrelation, with the complete supporting material: the Lean 4 formalization (Mathlib), the exact computational certificates with their recorded outputs, and the records of the adversarial reviews. Paper 1 — Three Barriers to De-oracleizing Forrelation: Truth Tables, Seeds, and Restricted Models (barriers.pdf, source barriers-source.tar.gz). Forrelation separates quantum from classical query complexity maximally. The paper studies the ladder of intermediate goals between the oracle separation and an unconditional separation of uniform decision classes and shows that three natural formalizations of its rungs are either trivial (truth-table collapse: quasi-linear time by the fast Walsh–Hadamard transform), false for every family (seed-compression barrier: any family generated from fewer seed bits than queries is distinguished from random by a fixed query set, and the computational variant is equivalent to one-way functions), or a restatement of a classical question (restricted-model trap: an explicit universal family whose label is any prescribed function of the seed, with exact Forrelation atoms and a proof of invariance). In the equal-footing model, where the restricted class evaluates the family itself, the trap dissolves for the whole orbit of the quadratic base pair under linear changes of variables and twists, by a derivative attack; a Kloosterman-sum family outside that orbit is constructed with provable atoms for every n ≥ 7 (fourth-moment identity, translation Parseval), on which the same-seed attacks of the paper are at chance; a uniform choice of the NO translation is open and stated as a conjecture supported by exact computation up to n = 25. Paper 2 — Low-Degree Instantiations of Forrelation Are Easy: Hidden Subspaces from Queries, Block Structure from Coefficients (whitebox.pdf, source whitebox-source.tar.gz). For the hidden Maiorana–McFarland family of Girish and Servedio with a polynomial h of constant degree whose top-degree form has trivial radical, O(4^d n^2) queries to f recover the hidden subspace as the radical of the top-degree form of f, after which the dual is evaluated by linear algebra; the low-degree instantiation is therefore easy already in the black-box model, and for d = 3 the radical hypothesis can be dropped. For the self-Forrelation proposal of Gheorghiu, Bravyi and Temme (as described in Gheorghiu's talk), the block decomposition of a sum of non-degenerate cubic blocks scrambled by an orthogonal matrix is recovered from the coefficient list by linear algebra through the symmetry algebra of the cubic form; degenerate blocks, a constant fraction of the self-dual bent cubics the proposal uses, defeat this algorithm, and the obstruction and the failure rate are given. Reproducibility archive (forrelation-barriers.tar.gz): the Lean 4 project (41 files in Forrelation/ plus a vendored subset of the OpenAI Math Release library for constant-depth circuits, Apache 2.0), every theorem depending only on the standard axioms; 35 certificate scripts with run_all.sh and the recorded results; the review records (several rounds of adversarial panel review per paper, three reviewers per round, syntheses, and an evidence audit of the citations against primary sources); and the project report. The analysis, code, Lean proofs, reviews and text were produced with large language models operated by the author, who checked every statement and certificate (see the AI disclosure sections of the papers).