跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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 HH from nn bits to mm bits, almost all h∈Hh \in H require a quantum algorithm with at most SS qubits of memory to make Ω(nm/S)Ω(nm/S) queries to input xx in order to compute h(x)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 hh and its input xx. 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 nn numbers from [n2][n^2] using at most SS qubits of memory requires Ω(n4/3(log⁡log⁡n)/(S1/3log⁡n))Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n)) quantum queries to the input.

作者备注:48 pages, new version improves the arXiv abstract and modifies our theorem statements to apply to all space bounds

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v3,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 HH from nn bits to mm bits, almost all h∈Hh \in H require a quantum algorithm with at most SS qubits of memory to make Ω(nm/S)Ω(nm/S) queries to input xx in order to compute h(x)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 hh and its input xx. 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 nn numbers from [n2][n^2] using at most SS qubits of memory requires Ω(n4/3(log⁡log⁡n)/(S1/3log⁡n))Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n)) quantum queries to the input.

查看此版本解读 →查看此版本原文 ↗