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

arXiv:1011.4935 · SIAM Journal on Computing

Strong Direct Product Theorems for Quantum Communication and Query Complexity

Alexander A. Sherstov

Published Jun 6, 2011• 82 citations
arXivHTMLPDF

Abstract

A strong direct product theorem (SDPT) states that solving n instances of a problem requires Omega(n) times the resources for a single instance, even to achieve success probability 2-Ω(n). We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by the generalized discrepancy method, the strongest technique in that model. We prove that quantum query complexity obeys an SDPT whenever the query lower bound for a single instance is proved by the polynomial method, one of the two main techniques in that model. In both models, we prove the corresponding XOR lemmas and threshold direct product theorems.

DOI
10.1137/110842661

Related papers

Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs

Hartmut Klauck, Robert Špalek, Ronald de Wolf

A strong direct product theorem says that if we want to compute k independent instances of a function, using less than k times the resources needed for one instance, then our overall success probability will be exponentially small in k. We establish such theorems for the classical as well as quantum query complexity of the OR function. This implies slightly weaker direct product results for all total functions. We prove a similar result for quantum communication protocols computing k instances of the Disjointness function. Our direct product theorems imply a time-space tradeoff T^2*S=Omega(N^3) for sorting N items on a quantum computer, which is optimal up to polylog factors. They also give several tight time-space and communication-space tradeoffs for the problems of Boolean matrix-vector multiplication and matrix multiplication.

arXiv:quant-ph/0402123•Electronic colloquium on computational complexity•Feb 18, 2004•23 citations

Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs

Hartmut Klauck, Robert Špalek, Ronald de Wolf

A strong direct product theorem says that if we want to compute k independent instances of a function, using less than k times the resources needed for one instance, then our overall success probability is exponentially small in k. We establish such theorems for the classical as well as quantum query complexity of the OR function. This implies slightly weaker direct product results for all total functions. We prove a similar result for quantum communication protocols computing k instances of the disjointness function. These results imply a time-space tradeoff T/sup 2/S = /spl Omega/(N/sup 3/) for sorting N items on a quantum computer, which is optimal up to polylog factors. They also give several tight time-space and communication-space tradeoffs for the problems of Boolean matrix-vector multiplication and matrix multiplication.

Annual Symposium on Foundations of Computer Science•Dec 23, 2004•32 citations

A strong direct product theorem in terms of the smooth rectangle bound

Rahul Jain, Penghui Yao

A strong direct product theorem states that, in order to solve k instances of a problem, if we provide less than k times the resource required to compute one instance, then the probability of overall success is exponentially small in k. In this paper, we consider the model of two-way public-coin communication complexity and show a strong direct product theorem for all relations in terms of the smooth rectangle bound, introduced by Jain and Klauck as a generic lower bound method in this model. Our result therefore uniformly implies a strong direct product theorem for all relations for which an (asymptotically) optimal lower bound can be provided using the smooth rectangle bound, for example Inner Product, Greater-Than, Set-Disjointness, Gap-Hamming Distance etc. Our result also implies near optimal direct product results for several important functions and relations used to show exponential separations between classical and quantum communication complexity, for which near optimal lower bounds are provided using the rectangle bound, for example by Raz [1999], Gavinsky [2008] and Klartag and Regev [2011]. In fact we are not aware of any relation for which it is known that the smooth rectangle bound does not provide an optimal lower bound. This lower bound subsumes many of the other lower bound methods, for example the rectangle bound (a.k.a the corruption bound), the smooth discrepancy bound (a.k.a the γ_2 bound) which in turn subsumes the discrepancy bound, the subdistribution bound and the conditional min-entropy bound. We show our result using information theoretic arguments. A key tool we use is a sampling protocol due to Braverman [2012], in fact a modification of it used by Kerenidis, Laplante, Lerays, Roland and Xiao [2012].

arXiv:1209.0263•Sep 3, 2012•19 citations

A Strong Direct Product Theorem for Quantum Query Complexity

Troy Lee, Jérémie Roland

We show that quantum query complexity satisfies a strong direct product theorem. This means that computing $k$ copies of a function with less than $k$ times the quantum queries needed to compute one copy of the function implies that the overall success probability will be exponentially small in $k$. For a boolean function $f$ we also show an XOR lemma -- computing the parity of $k$ copies of $f$ with less than $k$ times the queries needed for one copy implies that the advantage over random guessing will be exponentially small. We do this by showing that the multiplicative adversary method, which inherently satisfies a strong direct product theorem, characterizes bounded-error quantum query complexity. In particular, we show that the multiplicative adversary bound is always at least as large as the additive adversary bound, which is known to characterize bounded-error quantum query complexity.

arXiv:1104.4468•IEEE Conference on Computational Complexity (CCC)•Jun 1, 2012•6 citations

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

Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs

Hartmut Klauck, Robert Špalek, Ronald de Wolf

A strong direct product theorem says that if we want to compute k independent instances of a function, using less than k times the resources needed for one instance, then our overall success probability will be exponentially small in k. We establish such theorems for the classical as well as quantum query complexity of the OR‐function. This implies slightly weaker direct product results for all total functions. We prove a similar result for quantum communication protocols computing k instances of the disjointness function. Our direct product theorems imply a time‐space tradeoff $T^2S=\Om{N^3}$ for sorting N items on a quantum computer, which is optimal up to polylog factors. They also give several tight time‐space and communication‐space tradeoffs for the problems of Boolean matrix‐vector multiplication and matrix multiplication.

SIAM Journal on Computing•Jan 1, 2007•94 citations
A strong direct product theorem (SDPT) states that solving n instances of a problem requires Omega(n) times the resources for a single instance, even to achieve success probability 2-Ω(n). We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by the generalized discrepancy method, the strongest technique in that model. We prove that quantum query complexity obeys an SDPT whenever the query lower bound for a single instance is proved by the polynomial method, one of the two main techniques in that model. In both models, we prove the corresponding XOR lemmas and threshold direct product theorems.
A strong direct product theorem says that if we want to compute k independent instances of a function, using less than k times the resources needed for one instance, then our overall success probability will be exponentially small in k. We establish such theorems for the classical as well as quantum query complexity of the OR function. This implies slightly weaker direct product results for all total functions. We prove a similar result for quantum communication protocols computing k instances of the Disjointness function. Our direct product theorems imply a time-space tradeoff T^2*S=Omega(N^3) for sorting N items on a quantum computer, which is optimal up to polylog factors. They also give several tight time-space and communication-space tradeoffs for the problems of Boolean matrix-vector multiplication and matrix multiplication.
A strong direct product theorem says that if we want to compute k independent instances of a function, using less than k times the resources needed for one instance, then our overall success probability is exponentially small in k. We establish such theorems for the classical as well as quantum query complexity of the OR function. This implies slightly weaker direct product results for all total functions. We prove a similar result for quantum communication protocols computing k instances of the disjointness function. These results imply a time-space tradeoff T/sup 2/S = /spl Omega/(N/sup 3/) for sorting N items on a quantum computer, which is optimal up to polylog factors. They also give several tight time-space and communication-space tradeoffs for the problems of Boolean matrix-vector multiplication and matrix multiplication.
A strong direct product theorem states that, in order to solve k instances of a problem, if we provide less than k times the resource required to compute one instance, then the probability of overall success is exponentially small in k. In this paper, we consider the model of two-way public-coin communication complexity and show a strong direct product theorem for all relations in terms of the smooth rectangle bound, introduced by Jain and Klauck as a generic lower bound method in this model. Our result therefore uniformly implies a strong direct product theorem for all relations for which an (asymptotically) optimal lower bound can be provided using the smooth rectangle bound, for example Inner Product, Greater-Than, Set-Disjointness, Gap-Hamming Distance etc. Our result also implies near optimal direct product results for several important functions and relations used to show exponential separations between classical and quantum communication complexity, for which near optimal lower bounds are provided using the rectangle bound, for example by Raz [1999], Gavinsky [2008] and Klartag and Regev [2011]. In fact we are not aware of any relation for which it is known that the smooth rectangle bound does not provide an optimal lower bound. This lower bound subsumes many of the other lower bound methods, for example the rectangle bound (a.k.a the corruption bound), the smooth discrepancy bound (a.k.a the γ_2 bound) which in turn subsumes the discrepancy bound, the subdistribution bound and the conditional min-entropy bound. We show our result using information theoretic arguments. A key tool we use is a sampling protocol due to Braverman [2012], in fact a modification of it used by Kerenidis, Laplante, Lerays, Roland and Xiao [2012].
We show that quantum query complexity satisfies a strong direct product theorem. This means that computing kkk copies of a function with less than kkk times the quantum queries needed to compute one copy of the function implies that the overall success probability will be exponentially small in kkk. For a boolean function fff we also show an XOR lemma -- computing the parity of kkk copies of fff with less than kkk times the queries needed for one copy implies that the advantage over random guessing will be exponentially small. We do this by showing that the multiplicative adversary method, which inherently satisfies a strong direct product theorem, characterizes bounded-error quantum query complexity. In particular, we show that the multiplicative adversary bound is always at least as large as the additive adversary bound, which is known to characterize bounded-error quantum query complexity.
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.
A strong direct product theorem says that if we want to compute k independent instances of a function, using less than k times the resources needed for one instance, then our overall success probability will be exponentially small in k. We establish such theorems for the classical as well as quantum query complexity of the OR‐function. This implies slightly weaker direct product results for all total functions. We prove a similar result for quantum communication protocols computing k instances of the disjointness function. Our direct product theorems imply a time‐space tradeoff $T^2S=\Om{N^3}$ for sorting N items on a quantum computer, which is optimal up to polylog factors. They also give several tight time‐space and communication‐space tradeoffs for the problems of Boolean matrix‐vector multiplication and matrix multiplication.