Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-171 | 7th September 2026 11:48

Quantum Query Advantage Requires Space

RSS-Feed




TR26-171
Authors: Minbo Gao, Zhengfeng Ji, Ziyi Xie
Publication: 7th September 2026 14:51
Downloads: 20
Keywords: 


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.



ISSN 1433-8092 | Imprint