Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.07503 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918326887776256 |
|---|---|
| author | Canonne, Clément L. Chen, Kenny Mestre, Julián |
| author_facet | Canonne, Clément L. Chen, Kenny Mestre, Julián |
| contents | We study the extremal Forrelation problem, where, provided with oracle access to Boolean functions $f$ and $g$ promised to satisfy either $\textrm{forr}(f,g)=1$ or $\textrm{forr}(f,g)=-1$, one must determine (with high probability) which of the two cases holds while performing as few oracle queries as possible. It is well known that this problem can be solved with \emph{one} quantum query; yet, Girish and Servedio (TQC 2025) recently showed this problem requires $\widetildeΩ(2^{n/4})$ classical queries, and conjectured that the optimal lower bound is $\widetildeΩ(2^{n/2})$. Through a completely different construction, we improve on their result and prove a lower bound of $Ω(2^{0.4999n})$, which matches the conjectured lower bound up to an arbitrarily small constant in the exponent. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_07503 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Quantumly Fast and the Classically Forrious Canonne, Clément L. Chen, Kenny Mestre, Julián Computational Complexity We study the extremal Forrelation problem, where, provided with oracle access to Boolean functions $f$ and $g$ promised to satisfy either $\textrm{forr}(f,g)=1$ or $\textrm{forr}(f,g)=-1$, one must determine (with high probability) which of the two cases holds while performing as few oracle queries as possible. It is well known that this problem can be solved with \emph{one} quantum query; yet, Girish and Servedio (TQC 2025) recently showed this problem requires $\widetildeΩ(2^{n/4})$ classical queries, and conjectured that the optimal lower bound is $\widetildeΩ(2^{n/2})$. Through a completely different construction, we improve on their result and prove a lower bound of $Ω(2^{0.4999n})$, which matches the conjectured lower bound up to an arbitrarily small constant in the exponent. |
| title | The Quantumly Fast and the Classically Forrious |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2602.07503 |