{"id":"arxiv/2609.29497","url":"https://arxiv.org/abs/2609.29497","tags":["quant-ph","cs.CC"],"score":0,"title":"Quantum Query Advantage Requires Space","domain":"quant-ph","source":"arxiv","authors":["Minbo Gao","Zhengfeng Ji","Ziyi Xie"],"reviews":0,"subject":"quant-ph","summary":"Hao, Huang, and Liu (STOC'26) recently showed that optimal quantum query complexity may require large workspace even for short-output problems, and asked whether a quantum query advantage over classical computation can itself require space. We resolve this question by exhibiting an explicit total Boolean function with quantum query complexity $Q=\\widetildeΘ(M)$, and randomized query complexity $R=Θ(M^{21/20})$, whereas, for every fixed $0<η<1/100$ and $S\\le O(M^{1/100-η})$, its $S$-space quantum query complexity satisfies $Q_S=ω(M^{21/20})$. Consequently, $$ Q<R<Q_S, $$ so the unrestricted…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-04","reactions":{}}