Strong Selective and List-Decoding Direct Product Theorems for Quantum Query ComplexityResearch Paper
A direct product theorem says that solving independent instances of a problem is times as hard as solving one, and that an algorithm with fewer resources fails on the -fold problem with probability exponentially close to in . The second, "strong" form is what lower-bound applications need. Time-space tradeoffs in the style of Borodin and Cook cut a…