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 generation. The proofs of these results use a version of the multiplicative adversary method that does not naturally extend to relations. Standard strong direct-product theorems apply when algorithms must correctly answer every given question. Prior work extended them to equivalent threshold direct-product theorems, which require answers to all questions but only require that most answers are correct. We focus on two further generalizations. Strong selective direct-products apply to algorithms that adaptively choose, based on what they learn from queries, which questions from a large list to answer. This generalization is relational and useful for proving time-space tradeoffs. We prove a quantum strong selective direct-product theorem for all functions using a relational formulation of the multiplicative adversary method by Jeffery and Zur which we prove, via an equivalent formulation, satisfies a strong selective direct product property and captures any query lower bound for functions proven by negative-weights adversaries. The second generalization is list-decoding direct product problems introduced by Ben-David and Blais for classical query complexity. These allow an algorithm to produce a large list of possible output vectors such that one of them is fully correct. They proved that such theorems hold for randomized complexity of all Boolean functions. We prove a quantum analogue of this theorem for all partial Boolean-valued functions. We show that strong list-decoding direct-product theorems are implied by a special case of multiplicative adversaries which we show, via a new reduction, can be obtained from negative-weights adversaries for any Boolean-valued function.
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 $H$ from $n$ bits to $m$ bits, almost all $h \in H$ require a quantum algorithm with at most $S$ qubits of memory to make $Ω(nm/S)$ queries to input $x$ in order to compute $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 $h$ and its input $x$. 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 $n$ numbers from $[n^2]$ using at most $S$ qubits of memory requires $Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n))$ quantum queries to the input.