Preprint
Sep 2026
Quantum Query Advantage Requires Space
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...
Minbo Gao, Zheng-Feng Ji, Zi-Yi Xie
· 0 citations