← 研踪 PaperTrailarXiv:2609.40334 · v3
A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds
首次提交 2026-10-01 01:57
版本更新 2026-11-18 17:49
雷达观测 2026-11-19 15:04
摘要
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 from bits to bits, almost all require a quantum algorithm with at most qubits of memory to make queries to input in order to compute , 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 and its input . 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 numbers from using at most qubits of memory requires quantum queries to the input.
作者备注:48 pages, new version improves the arXiv abstract and modifies our theorem statements to apply to all space bounds
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-18 17:49 · 最新观测版本
A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds
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 from bits to bits, almost all require a quantum algorithm with at most qubits of memory to make queries to input in order to compute , 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 and its input . 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 numbers from using at most qubits of memory requires quantum queries to the input.
查看此版本解读 →查看此版本原文 ↗