{"id":"arxiv/2609.03628","url":"https://arxiv.org/abs/2609.03628","tags":["cs.CC","quant-ph"],"score":0,"title":"Random Garbage Separates XOR from Forward-Only Queries","domain":"cs.CC","source":"arxiv","authors":["Khaled Elbassioni","Rishikesh Gajjala","Saurabh Ray"],"reviews":0,"subject":"cs.CC","summary":"We give exponential quantum query separations between the standard XOR interface and two forward-only interfaces that supply neither an adjoint nor an inverse oracle. Let $X=\\F_2^n$, $N=|X|$, and $f_{h,r}(x)=(h(x),x,r_x)$, where $h:X\\to X$ is promised to be either a permutation or a Simon two-to-one function, and $r$ is a fixed table of $n$-bit tags, unrestricted by the promise and reused on every query. The resulting problem is solvable with at most $n+2$ standard XOR queries, but has forward-erasing query complexity $Θ(\\sqrt N)$. This answers affirmatively open question 11 in [Scott…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-03","reactions":{}}