Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 6 min ago
PreprintCC BY 4.0arXiv

Exponential Quantum Advantage in Testing Fourier Dimensionality

  • Kenny Chen
Open at sourcePDFDOICite

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 ε-far from being so. We show that there is an O(k/√ε)-query quantum property tester for this problem, which we show to be almost optimal. Combined with Gopalan \etal's classical lower bound of Ω(2k/2), this demonstrates an exponential quantum advantage for this task. We complement this result with a Õ(2k/2/ε) 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 αε-close to having Fourier dimension at most k, or is ε-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 Õ(k/ε) quantum tester, and a Õ(2k/2/ε) classical tester.

Related

  1. Exponential advantage in continuous-variable quantum state learning
    Eugen Coroi, Changhun Oh
    npj Quantum InformationPeer-reviewedCC BY-NC-ND 4.0Full text1 citedQuantum physics & quantum informationCrossref
  2. An Exponential Sample-Complexity Advantage for Coherent Quantum Inference
    Zhaoyi Li, Elias Theil, Aram W. Harrow +1
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  3. Exponential Quantum Advantage in Numbers-on-Forehead Communication
    Haoyu Wang, Pei Wu, Guangxu Yang
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  4. Exponential Quantum Advantage in Stationary Signal Sensing
    Sojeong Park, Changhun Oh
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  5. Exponential Advantage of Quantum over Classical References in Leakage Detection
    Zheng An
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{chen2026exponential,
  title = {{Exponential Quantum Advantage in Testing Fourier Dimensionality}},
  author = {Kenny Chen},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.25816},
  eprint = {2609.25816},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.25816},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Exponential Quantum Advantage in Testing Fourier Dimensionality
AU  - Kenny Chen
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2609.25816
UR  - https://arxiv.org/abs/2609.25816
AB  - 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 ε-far from being so. We show that there is an O(k/√ε)-query quantum property tester for this problem, which we show to be almost optimal. Combined with Gopalan \etal's classical lower bound of Ω(2^k/2), this demonstrates an exponential quantum advantage for this task. We complement this result with a Õ(2^k/2/ε) 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 αε-close to having Fourier dimension at most k, or is ε-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 Õ(k/ε) quantum tester, and a Õ(2^k/2/ε) classical tester.
ER  -