Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ZIYI XIE:
All reports by Author Ziyi Xie:

TR26-171 | 7th September 2026
Minbo Gao, Zhengfeng Ji, Ziyi Xie

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 quantum query complexity $Q=\widetilde{\Theta}(M)$, ... more >>>




ISSN 1433-8092 | Imprint