Quantum Query Advantage Requires Space

Abstract

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{\Theta}(M)$, and randomized query complexity $R=\Theta(M^{21/20})$, whereas, for every fixed $0<\eta<1/100$ and $S\le O(M^{1/100-\eta})$, its $S$-space quantum query complexity satisfies $Q_S=\omega(M^{21/20})$. Consequently, $$ Q<R<Q_S, $$ so the unrestricted quantum query advantage disappears under sufficiently small workspace. The separation is obtained through a one-bit filtered-parity construction and a space-sensitive quantum lower bound based on compressed-oracle capacity and a new parity-to-capacity inequality, which may be of independent interest.