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.
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.
This work settles this conjecture for parallel quantum algorithms, showing that every $t-query $d-round quantum algorithm can be simulated on most inputs with $t^{O(d^2)}$ classical queries, suggesting that for unstructured problems, superpolynomial speedups would require quantum circuits of superconstant depth, and ex...
Guy Blanc, Jordan Docter, Carmen Strassle et al.· 2 citations· ⚡1
We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification ($\mathsf{BMPV}$), answering a longstanding open question in quantum query complexity. For $n\times n$ matrices, our upper bound is $\widetilde O(n^{17/12})$, improving on the standard $O(n^{3/2})$ bound o...
Amin Shiraz Gilani, François Le Gall, Xing-Yu Zhou· 0 citations
It is proved that for monoids with a stable partial order in which the identity is the minimum element, the bounded-error quantum query complexity is at most $\sqrt{n+1}((\beta+2)\log(n+2))^{O(\log(\beta+2))}$.
The argument reduces any $N$-query circuit to the approximation of $e^{it\theta}$ by a trigonometric polynomial with degree bounded by $O(N)$ by a trigonometric polynomial with degree bounded by $O(N)$ together with Remez inequality to establish a matching lower bound for arbitrary query algorithms.
A. Liu, Adam Wesołowski, Jayne Thompson et al.· 0 citations
We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation...
A. Ambainis, A. Gilyén, M. Kokainis· 2 citations· ⚡1
This work gives distributional joint computation lower bounds for the composition, direct sum, and direct product problems, and introduces some new tools for handling quantum query lower bounds, including a new ``Shaltiel-free''measure of quantum query complexity, which characterizes the composition behavior of distrib...
S. Ben-David, M. H. Ebtehaj· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.