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 pure...