291 citations · 445 across the 25 of their papers we have counts for
Showing 2026 · cs.CCShow all
2 papers · 2 filters
cs.CC2026
A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds
Paul Beame, Blake Holman, Niels Kornerup
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 tradeo…
cs.CC2026
Strong Selective and List-Decoding Direct Product Theorems for Quantum Query Complexity
Paul Beame, Niels Kornerup, Michael Whitmeyer
Quantum strong direct-product theorems for specific functions have been known for nearly two decades. These have been extended to general results for function computation and state…