Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Annual Symposium on Foundations of Computer Science

Direct Product Theorems for Randomized Query Complexity

Shalev Ben-David, Eric Blais

Published Dec 14, 2025• 0 citations
Publisher

Abstract

We establish two new direct product theorems for the randomized query complexity of Boolean functions. The first shows that computing n copies of a function f, even with a small success probability of $\gamma^{n}$, requires $\Theta(n)$ times the maximum distributional query complexity of f with success parameter $\gamma$. This result holds for all success parameters $\gamma$, even when $\gamma$ is very close to 1/2 or to 1. As a result, it unifies and generalizes Drucker’s direct product theorem (2012) for $\gamma$ bounded away from $\frac{1}{2}$ and 1 as well as the strong direct sum theorem of Blais and Brody (2019) for $\gamma \approx 1-1 / n$. The second establishes a general list decoding direct product theorem that captures many different variants of “partial computation” tasks related to the function $f^{n}$ consisting of n copies of f. Notably, our list decoding direct product theorem yields a new threshold direct product theorem and other new variants such as the labelled-threshold direct product theorem. Both of these direct product theorems are obtained by taking a new approach. Instead of directly analyzing the query complexity of algorithms, we introduce a new measure of complexity of functions that we call discounted score. We show that this measure satisfies a number of useful structural properties, including tensorization, that make it particularly suitable for the study of direct product questions.

DOI
10.1109/focs63196.2025.00038

Related papers

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

cs.CCCross-listedarXiv:2609.26678•Sep 23, 2026•0 citations

Direct Product Theorems for Randomized Query Complexity

Shalev Ben-David, Blais, Eric

We establish two new direct product theorems for the randomized query complexity of Boolean functions. The first shows that computing $n$ copies of a function $f$, even with a small success probability of $γ^n$, requires $Θ(n)$ times the "maximum distributional" query complexity of $f$ with success parameter $γ$. This result holds for all success parameters $γ$, even when $γ$ is very close to $1/2$ or to $1$. As a result, it unifies and generalizes Drucker's direct product theorem (2012) for $γ$ bounded away from $\frac12$ and $1$ as well as the strong direct sum theorem of Blais and Brody (2019) for $γ\approx 1-1/n$. The second establishes a general "list decoding" direct product theorem that captures many different variants of partial computation tasks related to the function $f^n$ consisting of $n$ copies of $f$. Notably, our list decoding direct product theorem yields a new threshold direct product theorem and other new variants such as the labelled-threshold direct product theorem. Both of these direct product theorems are obtained by taking a new approach. Instead of directly analyzing the query complexity of algorithms, we introduce a new measure of complexity of functions that we call "discounted score". We show that this measure satisfies a number of useful structural properties, including tensorization, that make it particularly suitable for the study of direct product questions.

arXiv:2512.08268•Dec 9, 2025•0 citations

Distributional Quantum Query Complexity

Shalev Ben-David, M. H. Ebtehaj

Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting $Q(f\circ g)=Θ(Q(f)Q(g))$ for all Boolean functions $f$ and $g$; a direct sum theorem asserting that computing $k$ copies of a function (or search problem) costs $Ω(k)$ times as much as the cost of computing one copy; and a direct product theorem asserting that for Boolean functions, even succeeding at the direct sum problem with exponentially small probability still requires $Ω(k)$ times the cost of computing one copy to bounded error. However, all of these results are strictly for worst-case quantum query complexity. For example, if we have a fixed distribution $μ$ over inputs, the direct sum theorem says nothing about the quantum query complexity of computing $k$ copies of $f$ when the input comes from the product distribution $μ^k$ instead of being worst-case. (Note that while a standard Yao-type minimax theorem guarantees a hard distribution for the direct sum problem, there's no guarantee that this hard distribution is a product distribution.) A similar problem occurs for the direct product theorem and the composition theorem: none of these results respect distributions. In this work, we give distributional joint computation lower bounds for the composition, direct sum, and direct product problems. Along the way, we introduce some new tools for handling quantum query lower bounds, including (a) a new ``multiplicative'' variant of the $γ_2$ norm (which we use in place of the multiplicative adversary method for proving the direct product theorem), and (b) a new ``Shaltiel-free'' measure of quantum query complexity, which we show characterizes the composition behavior of distributional quantum query complexity and satisfies pleasing properties.

quant-pharXiv:2610.06835•Oct 6, 2026•0 citations

A strong direct sum theorem for distributional query complexity

Guy Blanc, Caleb Koch, Carmen Strassle +1 more

Consider the expected query complexity of computing the k-fold direct product $$f^{\otimes k}$$ of a function f to error $$\varepsilon $$ with respect to a distribution $$\mu ^k$$ . One strategy is to sequentially compute each of the k copies to error $$\varepsilon /k$$ with respect to $$\mu $$ and apply the union bound. We prove a strong direct sum theorem showing that this naive strategy is essentially optimal. In particular, computing a direct product necessitates a blowup in both query complexity and error. Strong direct sum theorems contrast with results that only show a blowup in query complexity or error but not both. There has been a long line of such results for distributional query complexity, dating back to (Impagliazzo, Raz, Wigderson 1994) and (Nisan, Rudich, Saks 1994), but a strong direct sum theorem had been elusive. A key idea in our work is the first use of the Hardcore Theorem (Impagliazzo 1995) in the context of query complexity. We prove a new “resilience lemma" that accompanies it, showing that the hardcore of $$f^{\otimes k}$$ is likely to remain dense under arbitrary partitions of the input space.

arXiv:2405.16340•Computational Complexity•May 5, 2026•1 citation

A Strong XOR Lemma for Randomized Query Complexity

Brody, Joshua, Jae Tak Kim, Peem Lerdputtipongporn +1 more

We give a strong direct sum theorem for computing $xor \circ g$. Specifically, we show that for every function g and every $k\geq 2$, the randomized query complexity of computing the xor of k instances of g satisfies $\overline{R}_\eps(xor\circ g) = Θ(k \overline{R}_{\eps/k}(g))$. This matches the naive success amplification upper bound and answers a conjecture of Blais and Brody (CCC19). As a consequence of our strong direct sum theorem, we give a total function g for which $R(xor \circ g) = Θ(k \log(k)\cdot R(g))$, answering an open question from Ben-David et al.(arxiv:2006.10957v1).

arXiv:2007.05580•Jul 10, 2020•4 citations

Randomized query composition and sabotage complexity

Swagato Sanyal

Let \(\mathsf {R}_\epsilon\) denote the randomized query complexity for error probability ε, and \(\mathsf {R}:=\mathsf {R}_{1/3}\) . In this work, we investigate whether a perfect composition theorem \(\mathsf {R}(f \circ g^n)=\Omega (\mathsf {R}(f)\cdot \mathsf {R}(g))\) holds for a relation \(f \subseteq \lbrace 0,1\rbrace ^n \times \mathcal {S}\) and a total inner function \(g:\lbrace 0,1\rbrace ^m \rightarrow \lbrace 0,1\rbrace\) . Ben-David and Kothari (ICALP 2016, TOC 2018) showed that \(\mathsf {R}(f \circ g^n)=\Omega (\mathsf {R}(f)\cdot \mathsf {RS}(g))\) , where \(\mathsf {RS}\) is the sabotage complexity, a measure that they defined. Their result holds even when f is any relation and g is any partial function. Ben-David and Kothari asked in their article whether Sabotage complexity \(\mathsf {RS}\) is asymptotically equivalent to \(\mathsf {R}\) for total Boolean functions. In this article, we show that \(\mathsf {RS}\) is asymptotically at least the maximum distributional query complexity for any product distribution (i.e., probability distribution where the individual bits are independently distributed). In light of the minimax theorem, which states that \(\mathsf {R}\) is the maximum distributional query complexity for any distribution, our result makes progress toward answering the composition question. We prove our result by introducing a novel complexity measure called \(\mathsf {R}_{}^{\mathsf {prod}}\) , and proving it to be equivalent to \(\mathsf {RS}\) up to a logarithmic factor. How tight is our bound? We show that our bound is polynomially loose for the complete binary NAND tree function, for which \(\mathsf {RS}\) is polynomially larger than the distributional query complexity for any product distribution. Our result also confirms that \(\mathsf {RS}\) and \(\mathsf {R}\) are asymptotically equivalent for this function. We thus also show a polynomial separation between \(\mathsf {R}\) and the maximum distributional query complexity for any product distribution which, to our knowledge, was not known prior to our work.

ACM Transactions on Computation Theory•Jul 15, 2025•0 citations
We establish two new direct product theorems for the randomized query complexity of Boolean functions. The first shows that computing n copies of a function f, even with a small success probability of γn\gamma^{n}γn, requires Θ(n)\Theta(n)Θ(n) times the maximum distributional query complexity of f with success parameter γ\gammaγ. This result holds for all success parameters γ\gammaγ, even when γ\gammaγ is very close to 1/2 or to 1. As a result, it unifies and generalizes Drucker’s direct product theorem (2012) for γ\gammaγ bounded away from 12\frac{1}{2}21​ and 1 as well as the strong direct sum theorem of Blais and Brody (2019) for γ≈1−1/n\gamma \approx 1-1 / nγ≈1−1/n. The second establishes a general list decoding direct product theorem that captures many different variants of “partial computation” tasks related to the function fnf^{n}fn consisting of n copies of f. Notably, our list decoding direct product theorem yields a new threshold direct product theorem and other new variants such as the labelled-threshold direct product theorem. Both of these direct product theorems are obtained by taking a new approach. Instead of directly analyzing the query complexity of algorithms, we introduce a new measure of complexity of functions that we call discounted score. We show that this measure satisfies a number of useful structural properties, including tensorization, that make it particularly suitable for the study of direct product questions.
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 establish two new direct product theorems for the randomized query complexity of Boolean functions. The first shows that computing nnn copies of a function fff, even with a small success probability of γnγ^nγn, requires Θ(n)Θ(n)Θ(n) times the "maximum distributional" query complexity of fff with success parameter γγγ. This result holds for all success parameters γγγ, even when γγγ is very close to 1/21/21/2 or to 111. As a result, it unifies and generalizes Drucker's direct product theorem (2012) for γγγ bounded away from 12\frac1221​ and 111 as well as the strong direct sum theorem of Blais and Brody (2019) for γ≈1−1/nγ\approx 1-1/nγ≈1−1/n. The second establishes a general "list decoding" direct product theorem that captures many different variants of partial computation tasks related to the function fnf^nfn consisting of nnn copies of fff. Notably, our list decoding direct product theorem yields a new threshold direct product theorem and other new variants such as the labelled-threshold direct product theorem. Both of these direct product theorems are obtained by taking a new approach. Instead of directly analyzing the query complexity of algorithms, we introduce a new measure of complexity of functions that we call "discounted score". We show that this measure satisfies a number of useful structural properties, including tensorization, that make it particularly suitable for the study of direct product questions.
Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting Q(f∘g)=Θ(Q(f)Q(g))Q(f\circ g)=Θ(Q(f)Q(g))Q(f∘g)=Θ(Q(f)Q(g)) for all Boolean functions fff and ggg; a direct sum theorem asserting that computing kkk copies of a function (or search problem) costs Ω(k)Ω(k)Ω(k) times as much as the cost of computing one copy; and a direct product theorem asserting that for Boolean functions, even succeeding at the direct sum problem with exponentially small probability still requires Ω(k)Ω(k)Ω(k) times the cost of computing one copy to bounded error. However, all of these results are strictly for worst-case quantum query complexity. For example, if we have a fixed distribution μμμ over inputs, the direct sum theorem says nothing about the quantum query complexity of computing kkk copies of fff when the input comes from the product distribution μkμ^kμk instead of being worst-case. (Note that while a standard Yao-type minimax theorem guarantees a hard distribution for the direct sum problem, there's no guarantee that this hard distribution is a product distribution.) A similar problem occurs for the direct product theorem and the composition theorem: none of these results respect distributions. In this work, we give distributional joint computation lower bounds for the composition, direct sum, and direct product problems. Along the way, we introduce some new tools for handling quantum query lower bounds, including (a) a new ``multiplicative'' variant of the γ2γ_2γ2​ norm (which we use in place of the multiplicative adversary method for proving the direct product theorem), and (b) a new ``Shaltiel-free'' measure of quantum query complexity, which we show characterizes the composition behavior of distributional quantum query complexity and satisfies pleasing properties.
Consider the expected query complexity of computing the k-fold direct product f⊗kf^{\otimes k}f⊗k of a function f to error ε\varepsilon ε with respect to a distribution μk\mu ^kμk . One strategy is to sequentially compute each of the k copies to error ε/k\varepsilon /kε/k with respect to μ\mu μ and apply the union bound. We prove a strong direct sum theorem showing that this naive strategy is essentially optimal. In particular, computing a direct product necessitates a blowup in both query complexity and error. Strong direct sum theorems contrast with results that only show a blowup in query complexity or error but not both. There has been a long line of such results for distributional query complexity, dating back to (Impagliazzo, Raz, Wigderson 1994) and (Nisan, Rudich, Saks 1994), but a strong direct sum theorem had been elusive. A key idea in our work is the first use of the Hardcore Theorem (Impagliazzo 1995) in the context of query complexity. We prove a new “resilience lemma" that accompanies it, showing that the hardcore of f⊗kf^{\otimes k}f⊗k is likely to remain dense under arbitrary partitions of the input space.
We give a strong direct sum theorem for computing xor∘gxor \circ gxor∘g. Specifically, we show that for every function g and every k≥2k\geq 2k≥2, the randomized query complexity of computing the xor of k instances of g satisfies $\overline{R}_\eps(xor\circ g) = Θ(k \overline{R}_{\eps/k}(g))$. This matches the naive success amplification upper bound and answers a conjecture of Blais and Brody (CCC19). As a consequence of our strong direct sum theorem, we give a total function g for which R(xor∘g)=Θ(klog⁡(k)⋅R(g))R(xor \circ g) = Θ(k \log(k)\cdot R(g))R(xor∘g)=Θ(klog(k)⋅R(g)), answering an open question from Ben-David et al.(arxiv:2006.10957v1).
Let Rϵ\mathsf {R}_\epsilonRϵ​ denote the randomized query complexity for error probability ε, and R:=R1/3\mathsf {R}:=\mathsf {R}_{1/3}R:=R1/3​ . In this work, we investigate whether a perfect composition theorem R(f∘gn)=Ω(R(f)⋅R(g))\mathsf {R}(f \circ g^n)=\Omega (\mathsf {R}(f)\cdot \mathsf {R}(g))R(f∘gn)=Ω(R(f)⋅R(g)) holds for a relation f⊆{0,1}n×Sf \subseteq \lbrace 0,1\rbrace ^n \times \mathcal {S}f⊆{0,1}n×S and a total inner function g:{0,1}m→{0,1}g:\lbrace 0,1\rbrace ^m \rightarrow \lbrace 0,1\rbraceg:{0,1}m→{0,1} . Ben-David and Kothari (ICALP 2016, TOC 2018) showed that R(f∘gn)=Ω(R(f)⋅RS(g))\mathsf {R}(f \circ g^n)=\Omega (\mathsf {R}(f)\cdot \mathsf {RS}(g))R(f∘gn)=Ω(R(f)⋅RS(g)) , where RS\mathsf {RS}RS is the sabotage complexity, a measure that they defined. Their result holds even when f is any relation and g is any partial function. Ben-David and Kothari asked in their article whether Sabotage complexity RS\mathsf {RS}RS is asymptotically equivalent to R\mathsf {R}R for total Boolean functions. In this article, we show that RS\mathsf {RS}RS is asymptotically at least the maximum distributional query complexity for any product distribution (i.e., probability distribution where the individual bits are independently distributed). In light of the minimax theorem, which states that R\mathsf {R}R is the maximum distributional query complexity for any distribution, our result makes progress toward answering the composition question. We prove our result by introducing a novel complexity measure called Rprod\mathsf {R}_{}^{\mathsf {prod}}Rprod​ , and proving it to be equivalent to RS\mathsf {RS}RS up to a logarithmic factor. How tight is our bound? We show that our bound is polynomially loose for the complete binary NAND tree function, for which RS\mathsf {RS}RS is polynomially larger than the distributional query complexity for any product distribution. Our result also confirms that RS\mathsf {RS}RS and R\mathsf {R}R are asymptotically equivalent for this function. We thus also show a polynomial separation between R\mathsf {R}R and the maximum distributional query complexity for any product distribution which, to our knowledge, was not known prior to our work.