A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds
Paul Beame, Blake Holman, Niels Kornerup
原文摘要
We introduce a novel method based on the noise operator for showing that time-bounded quantum query algorithms only have exponentially small success probability. We use this to prove strong quantum time-space tradeoff lower bounds that seem out of reach by other methods. Applying our noise operator method involves purely classical arguments, making it straightforward to use. We use our quantum noise stability bound to prove that, for any pairwise independent hash function family $H$ from $n$ bits to $m$ bits, almost all $h \in H$ require a quantum algorithm with at most $S$ qubits of memory to make $Ω(nm/S)$ queries to input $x$ in order to compute $h(x)$, even with very small success probability. Such a lower bound was not previously known even for classical algorithms. Previously, Mansour, Nisan, and Tiwari had used their hash mixing lemma to show the same quantitative bound for classical algorithms that have as input both a description of $h$ and its input $x$. Our noise operator method allows us to use a related but simpler property of hash functions to prove our bounds. As one consequence of this lower bound we derive the first optimal time-space tradeoff lower bounds for quantum algorithms computing integer multiplication. We also use this method to prove the first nontrivial fully general quantum time-space tradeoff lower bound for sorting. All previous quantum time-space tradeoff lower bounds for sorting are limited to proving output-oblivious lower bounds (i.e. the lower bounds only apply to algorithms with a non-adaptive output schedule). By combining our quantum noise stability bound with quantum recording query methods, we prove that every quantum algorithm that sorts $n$ numbers from $[n^2]$ using at most $S$ qubits of memory requires $Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n))$ quantum queries to the input.
cs.CC · quant-ph