{"id":"arxiv/2610.41694","url":"https://arxiv.org/abs/2610.41694","tags":["quant-ph","cs.CC"],"score":0,"title":"Exponential quantum-classical query separations for cyclic Forrelation","domain":"quant-ph","source":"arxiv","authors":["Yuxin Zhang","Changpeng Shao"],"reviews":0,"subject":"quant-ph","summary":"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,\\ldots,f_k:\\mathbb{F}_2^n\\to\\{-1,1\\}$, the goal is to estimate $T_k=N^{-1}\\operatorname{Tr}(D_{f_1}H^{\\otimes n}\\cdots D_{f_k}H^{\\otimes n}),$ where $D_{f_i}=\\operatorname{diag}(f_i(x):x\\in\\mathbb{F}_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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-30","reactions":{}}