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