arXiv:2609.40334
A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds
Paul Beame, Blake Holman, Niels Kornerup
Abstract
Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. Yet, our tools for proving unconditional quantum tradeoffs between time and space are surprisingly limited. The first quantum time-space tradeoff lower bounds were proven for sorting by Klauck, Špalek and de Wolf. Unfortunately, their method is limited to proving output-oblivious lower bounds (i.e. the lower bounds only apply to algorithms with a non-adaptive output schedule) and other methods have yielded nothing beyond output-oblivious lower bounds for sorting. Here, we prove the first fully general quantum time-space tradeoff lower bound for sorting. We do so by introducing a novel method based on the noise operator to add to the analysis toolkit for proving quantum query and time-space tradeoff lower bounds. By combining our resulting quantum noise stability bound with quantum recording query methods, we prove an $Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n))$ lower bound on the number of queries that a fully general quantum algorithm with at most $S$ qubits of memory requires to sort $n$ numbers from $[n^2]$. Applying our noise operator argument involves purely classical reasoning, which makes it particularly simple to use. We also use it to prove that, for any strongly universal (pairwise independent) hash function family $H$ from $n$ bits to $m$ bits, almost all hash functions in $H$ require any algorithm with at most $S$ qubits of memory to make $Ω(nm/S)$ quantum queries to input $x$ in order to compute $h(x)$, even with very small success probability. Previously, Mansour, Nisan, and Tiwari had shown a matching classical lower bound for computing $h(x)$ with both $h$ and $x$ as inputs using their hash mixing lemma. Our noise operator method allows us to use a related property of hash functions to prove our quantum lower bounds.
AI Summary
The paper addresses quantum time–space tradeoff lower bounds, particularly sorting when an algorithm’s output schedule may be adaptive. Earlier quantum tradeoff bounds for sorting applied only to output-oblivious algorithms. The stated sorting result removes that restriction. The method introduces a noise-operator approach to quantum query lower bounds. It derives a quantum noise-stability bound whose application uses purely classical reasoning, then combines it with quantum recording-query methods. For sorting $n$ numbers from $[n^2]$, the resulting lower bound is $\Omega\!\left(n^{4/3}\log\log n/(S^{1/3}\log n)\right)$ queries for a fully general quantum algorithm using at most $S$ qubits of memory. A second application concerns strongly universal, or pairwise-independent, hash families $H$ mapping $n$-bit inputs to $m$-bit outputs. For almost all $h\in H$, computing $h(x)$ with at most $S$ qubits requires $\Omega(nm/S)$ quantum queries to $x$, even with very small success probability. The argument uses a hash-function property related to the hash mixing lemma, which previously established a matching classical bound in a formulation where both $h$ and $x$ are inputs. The stated results concern query complexity under a quantum-memory bound, rather than general gate-count lower bounds. The sorting theorem is stated for the specified input range, and the hashing theorem applies to almost all functions in each such family, not every function. Only the abstract is available; precise parameter regimes and success-probability thresholds are not specified there.
Written by gpt-6.1-sol from the abstract only. Automated: it can be wrong.
- Comments
- 46 pages, submitted to QIP 2027. New version fixes the displayed abstract and makes some minor corrections to fix the parameters used in results