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=Θ̃(M), and randomized query complexity R=Θ(M21/20), whereas, for every fixed 0<η<1/100 and S≤ O(M1/100−η), its S-space quantum query complexity satisfies QS=ω(M21/20). Consequently, Q<R<QS, 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.
Related
- Parallel Quantum Advantage with Limited Adaptivity Requires Structure
- An exponential query advantage from access to Stinespring dilation unitaries in quantum channel learning
- Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries
- Exponential quantum space advantage in random data streams
- A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds
BibTeX
@misc{gao2026quantum,
title = {{Quantum Query Advantage Requires Space}},
author = {Minbo Gao and Zhengfeng Ji and Ziyi Xie},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.29497},
eprint = {2609.29497},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29497},
}
RIS
TY - UNPB
TI - Quantum Query Advantage Requires Space
AU - Minbo Gao
AU - Zhengfeng Ji
AU - Ziyi Xie
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2609.29497
UR - https://arxiv.org/abs/2609.29497
AB - 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=Θ̃(M), and randomized query complexity R=Θ(M^21/20), whereas, for every fixed 0<η<1/100 and S≤ O(M^1/100−η), its S-space quantum query complexity satisfies Q_S=ω(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.
ER -