arXiv:2609.26678
Strong Selective and List-Decoding Direct Product Theorems for Quantum Query Complexity
Paul Beame, Niels Kornerup, Michael Whitmeyer
Abstract
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.
AI Summary
The paper asks whether quantum query strong direct-product theorems survive when an algorithm can choose which instances to answer, or output a list containing the correct answer vector. In the selective problem, it receives $m$ independent instances and must identify $k$ distinct instances together with correct outputs. In the list-decoding problem, it outputs at most $|Y|^{m-k}$ candidate vectors in $Y^m$. For every function $f$, including partial functions, the paper proves that selectively answering $k$ instances with success probability $\exp(-\Omega(k))$ requires $\Omega(kQ_{1/10}(f))$ queries, uniformly in $m\ge k$, for sufficiently large $k$. The analogous list-decoding theorem holds for every partial Boolean-valued function. Explicit bounds are also given for unique search, OR, and parity, with query scales $k\sqrt n$, $k\sqrt n$, and $kn$, respectively. An application gives a general quantum time-space lower bound $T=\Omega(n^{2.5}/S)$ and cumulative-memory lower bound $\Omega(n^{2.5})$ for matrix mapping. The proofs establish a selective tensor-product property for a relational multiplicative adversary method and convert negative-weight adversaries into matching multiplicative bounds, losing only constant factors. For Boolean outputs, a sharper conversion achieves the threshold parameter $\eta=1/2$ needed for list decoding. Fourth-moment bounds, proved through a hypercontractivity-style induction, control the probability captured by an output list without losses depending on $m/k$. The general list-decoding theorem for larger output alphabets remains open, as does an ordinary strong direct-product theorem for arbitrary relations. The paper also explains why these independent-input techniques do not directly remove output-oblivious restrictions from existing sorting and Boolean matrix-multiplication tradeoffs.
The idea of using 4-norms and the Cauchy-Schwarz inequality that is in the current argument is entirely the result of our interactions with ChatGPT 5.6.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 64 pages, 3 figures, submitted to QIP 2027