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=\tilde{\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.

21 pages