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

2-Fold Forrelation is in QAC0

  • Francisca Vasconcelos
Open at sourcePDFDOICite

Abstract

We show that 2-fold Forrelation with inverse-polylogarithmic promise gap can be solved, with bounded error, by polynomial-size QAC0 circuits. Unlike the standard oracle-based Forrelation algorithm, our circuits receive the input explicitly, in the same form as the AC0 circuits against which Forrelation is known to be hard. At constant gap, this yields a natural promise-problem separation between QAC0 and AC0.

Related

  1. Exponential quantum-classical query separations for cyclic Forrelation
    Yuxin Zhang, Changpeng Shao
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  2. Fold Catastrophes in a Hopf Texture Driven by a Navier--Stokes Blow-Up Analog
    Antti J. Niemi
    arXivPreprintCC BY 4.0Full textMathematical physicsAtomic, molecular & optical physicsarXiv
  3. Line operator indices of S-fold theories
    Yosuke Imamura, Masato Inoue, Akihiro Sei
    arXivPreprintCC BY 4.0Full textHigh-energy & particle physicsarXiv
  4. Resolving the Two-Fold Ambiguity in Tau Momentum Reconstruction via a Self-Consistent Weighting Method
    Rong-Gang Ping
    arXivPreprintCC BY-SA 4.0Full textHigh-energy & particle physicsarXiv
  5. Drying kinematics selects open honeycomb fold networks on solvent-extracted viscoelastic thin films and gels
    Fan Zhao, Surjyasish Mitra, Sunandan Tandon +3
    arXivPreprintCC BY-NC-ND 4.0Full textApplied physics & instrumentationCondensed matterarXiv

Cite

BibTeXRIS
BibTeX
@misc{vasconcelos20262fold,
  title = {{2-Fold Forrelation is in QAC$^0$}},
  author = {Francisca Vasconcelos},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.07060},
  eprint = {2609.07060},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.07060},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - 2-Fold Forrelation is in QAC^0
AU  - Francisca Vasconcelos
PY  - 2026
DA  - 2026/09/07
PB  - arXiv
DO  - 10.48550/arxiv.2609.07060
UR  - https://arxiv.org/abs/2609.07060
AB  - We show that 2-fold Forrelation with inverse-polylogarithmic promise gap can be solved, with bounded error, by polynomial-size QAC^0 circuits. Unlike the standard oracle-based Forrelation algorithm, our circuits receive the input explicitly, in the same form as the AC^0 circuits against which Forrelation is known to be hard. At constant gap, this yields a natural promise-problem separation between QAC^0 and AC^0.
ER  -