Skip to content
Preprint

Exponential Quantum Advantage in Testing Fourier Dimensionality

Sep 2026 · 0 citations · 30 references
Physics Computer Science

TL;DR

This work considers the property testing task of determining whether a function has Fourier dimension at most $k, or is $\epsilon$-far from being so, and shows that there is an $O(k/\sqrt{\epsilon})$-query quantum property tester for this problem, which is shown to be almost optimal.

Abstract

A boolean function $f$ has Fourier dimension $k$ if its strings with nonzero Fourier coefficients span a subspace of dimension $k$. We first consider the property testing task of determining whether a function has Fourier dimension at most $k$, or is $\epsilon$-far from being so. We show that there is an $O(k/\sqrt{\epsilon})$-query quantum property tester for this problem, which we show to be almost optimal. Combined with Gopalan \etal's classical lower bound of $\Omega(2^{k/2})$, this demonstrates an exponential quantum advantage for this task. We complement this result with a $\tilde{O}(2^{k/2}/\epsilon)$ classical tester, giving a quadratic improvement over the previous best tester, and essentially settling the classical query complexity. We then introduce and study the tolerant version of this problem. That is, determining whether a function is $\alpha\epsilon$-close to having Fourier dimension at most $k$, or is $\epsilon$-far from being so. Perhaps surprisingly, we show that this tolerant version of the problem is essentially just as hard as the standard version of the problem. That is, we show this problem has a $\tilde{O}(k/\epsilon)$ quantum tester, and a $\tilde{O}(2^{k/2}/\epsilon)$ classical tester.

View source

Similar papers

Preprint Sep 2026

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

A deterministic classical algorithm for the binary-error Learning-with-Errors problem, which is of independent cryptographic interest, and a full sample--time tradeoff that interpolates between exponential and polynomial runtime is established.

Robin Kothari, Tony Metger, Ryan O'Donnell et al. · 0 citations
Preprint Nov 2026

Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs

We prove that any linear $3$-query locally correctable code $C \colon \mathbb{F}_2^k \to \mathbb{F}_2^n$ with constant correction radius must have length $n \geq 2^{\Omega(\sqrt{k})}$. This improves on the prior best lower bound of $2^{\Omega(\sqrt{k/\log k})}$, due to [AG24], and shows that the folklore construction o...

Oliver Janzer, P. Manohar · 1 citation
Preprint Oct 2026

Distributional Quantum Query Complexity

This work gives distributional joint computation lower bounds for the composition, direct sum, and direct product problems, and introduces some new tools for handling quantum query lower bounds, including a new ``Shaltiel-free''measure of quantum query complexity, which characterizes the composition behavior of distrib...

S. Ben-David, M. H. Ebtehaj · 0 citations
Preprint Oct 2026

Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions

We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most $k$ nonzero Fourier coefficients. We give a learner with near-optimal $\widetilde{O}(k)$ sample complexity independent of the input length $n$. The learner uses only separate measurements of individual examples. This...

Ze-Kun Ye · 0 citations
Preprint Sep 2026

Indistinguishability of Sum of Permutations: A Fourier Analytic Route to Classical and Quantum Security

A unified Fourier analytic treatment of Dinur's variable-output single-permutation construction, $\mathsf{LXoP}$, for every fixed output width, and derive its classical and quantum security bounds; for one- and two-block outputs, they give concrete quantum security bounds.

Ritam Bhaumik, Chun Guo, Xiao-Ning Guo et al. · 0 citations
Preprint Sep 2026

The quantum query complexity of the semigroup product problem

It is proved that for monoids with a stable partial order in which the identity is the minimum element, the bounded-error quantum query complexity is at most $\sqrt{n+1}((\beta+2)\log(n+2))^{O(\log(\beta+2))}$.

Troy Lee, M. Santha · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.