Exponential quantum-classical query separations for cyclic Forrelation

Abstract

We study the randomized classical query complexity of cyclic Forrelation, a cyclic analogue of k-Forrelation [AA15, STOC'15; BS21, STOC'21]. Given k Boolean functions f₁,…,f_k:𝔽₂ⁿ→{−1,1}, the goal is to estimate T_k=N⁻¹Tr(D_f₁H^{⊗ n}⋯ D_{f_k}H^{⊗ n}), where D_{f_i}=diag(f_i(x):x∈𝔽₂ⁿ), H is the Hadamard gate, and N=2ⁿ. This normalized-trace problem can be solved with k quantum queries in the DQC1 model. Its classical query complexity was left open in [JLS+26, FOCS'26], which conjectured a lower bound of Ω̃(N^1−2/k). We establish a nearly complete characterization of the nonadaptive classical query complexity of cyclic Forrelation. For even k≥ 4, we prove a tight bound of Θ_k(N^1−2/k) for constant additive error. For odd k≥ 5, we obtain a lower bound of Ω_k(N^{1−2/(k−1)}) and an upper bound of O_k(N^1−2/k). Surprisingly, k=3 admits a polylogarithmic-query nonadaptive classical algorithm, disproving the conjecture in this case. These results suggest an unexpected parity-dependent structure: the nonadaptive complexity may be governed by the independence number of the k-cycle, leading to the exponent 1−1/⌊ k/2⌋, rather than the previously conjectured 1−2/k, which was motivated by a Fourier-growth heuristic. Finally, allowing adaptivity, we prove a lower bound of Ω(N^1/4) for every k≥4. Although formally close to k-Forrelation, the cyclic structure leads to rather different classical behavior and requires different techniques. Our lower bounds are based on hidden-shift collision constructions, and our upper bounds follow from randomized sampling together with cycle-specific conditional-moment estimates. Our results provide a systematic understanding of its query advantages over classical computation.

Improved Separations between Quantum and Classical Communication Complexity of Total Functions
François Le Gall
arXiv5 Oct 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Optimal Quantum-Classical Separations for Exact Learning
Srinivasan Arunachalam, Amin Shiraz Gilani, Nikhil S. Mande
arXiv29 Sep 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
Exponential Advantage of Quantum over Classical References in Leakage Detection
Zheng An
arXiv29 Sep 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Exponential quantum speedup for 𝔽₃ⁿ-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
Robin Kothari, Tony Metger, Ryan O'Donnell +2
arXiv30 Sep 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Unlocking Exponential and Unbounded Robust Gains in Shannon Capacity of Classical Multiple Access Channels with Causal CSIT via Quantum Entanglement Assistance
Yuhang Yao, Syed A. Jafar
arXiv6 Sep 2026PreprintarXiv licenceFull textGeneral mathematics Quantum physics & quantum informationarXiv

Cite

BibTeX RIS

BibTeX

@misc{zhang2026exponential,
  title = {{Exponential quantum-classical query separations for cyclic Forrelation}},
  author = {Yuxin Zhang and Changpeng Shao},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.41694},
  eprint = {2610.41694},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41694},
}

RIS

TY  - UNPB
TI  - Exponential quantum-classical query separations for cyclic Forrelation
AU  - Yuxin Zhang
AU  - Changpeng Shao
PY  - 2026
DA  - 2026/10/30
PB  - arXiv
DO  - 10.48550/arxiv.2610.41694
UR  - https://arxiv.org/abs/2610.41694
AB  - We study the randomized classical query complexity of cyclic Forrelation, a cyclic analogue of k-Forrelation [AA15, STOC'15; BS21, STOC'21]. Given k Boolean functions f_1,…,f_k:𝔽_2^n→{−1,1}, the goal is to estimate T_k=N^−1Tr(D_f_1H^⊗ n⋯ D_f_kH^⊗ n), where D_f_i=diag(f_i(x):x∈𝔽_2^n), H is the Hadamard gate, and N=2^n. This normalized-trace problem can be solved with k quantum queries in the DQC1 model. Its classical query complexity was left open in [JLS+26, FOCS'26], which conjectured a lower bound of Ω̃(N^1−2/k). We establish a nearly complete characterization of the nonadaptive classical query complexity of cyclic Forrelation. For even k≥ 4, we prove a tight bound of Θ_k(N^1−2/k) for constant additive error. For odd k≥ 5, we obtain a lower bound of Ω_k(N^1−2/(k−1)) and an upper bound of O_k(N^1−2/k). Surprisingly, k=3 admits a polylogarithmic-query nonadaptive classical algorithm, disproving the conjecture in this case. These results suggest an unexpected parity-dependent structure: the nonadaptive complexity may be governed by the independence number of the k-cycle, leading to the exponent 1−1/⌊ k/2⌋, rather than the previously conjectured 1−2/k, which was motivated by a Fourier-growth heuristic. Finally, allowing adaptivity, we prove a lower bound of Ω(N^1/4) for every k≥4. Although formally close to k-Forrelation, the cyclic structure leads to rather different classical behavior and requires different techniques. Our lower bounds are based on hidden-shift collision constructions, and our upper bounds follow from randomized sampling together with cycle-specific conditional-moment estimates. Our results provide a systematic understanding of its query advantages over classical computation.
ER  -

Abstract

Related

Cite