{"id":"arxiv/2609.40334","url":"https://arxiv.org/abs/2609.40334","tags":["cs.CC","quant-ph"],"score":0,"title":"A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds","domain":"cs.CC","source":"arxiv","authors":["Paul Beame","Blake Holman","Niels Kornerup"],"reviews":0,"subject":"cs.CC","summary":"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,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}