Metraipolis › archive › dc_7d1ee24006f1

2-Fold Forrelation is in QAC$^0$ — arXiv:2609.07060

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.07060
License (as archived)
CC0-1.0
Archived
2026-10-16T15:40:09.759Z
SHA-256 of the archived text
82fe81611bf60c04d577fddbf20ba5f039d08dee4a62bdb097c3475ce04cf273
Stable URL of this page
https://metraipolis.com/documento/dc_7d1ee24006f1

How to cite

2-Fold Forrelation is in QAC$^0$ — arXiv:2609.07060 — arXiv (en), https://arxiv.org/abs/2609.07060 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7d1ee24006f1 (Metraipolis archive dc_7d1ee24006f1, sha256 82fe81611bf60c04d577fddbf20ba5f039d08dee4a62bdb097c3475ce04cf273)
BibTeX
@misc{dc7d1ee24006f1,
  title = {2-Fold Forrelation is in QAC$^0$ — arXiv:2609.07060},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.07060},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7d1ee24006f1; sha256 82fe81611bf60c04d577fddbf20ba5f039d08dee4a62bdb097c3475ce04cf273},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.07060. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in cs.CC).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.07060 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T15:31:12.049Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).