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

The complexity of joint computation

Scott Aaronson, Andrew Drucker

Published Jan 1, 2012• 3 citations
OpenAlex

Abstract

Joint computation is the ubiquitous scenario in which a computer is presented with not one, but many computational tasks to perform.A fundamental question arises: when can we cleverly combine computations, to perform them with greater efficiency or reliability than by tackling them separately?This thesis investigates the power and, especially, the limits of efficient joint computation, in several computational models: query algorithms, circuits, and Turing machines.We significantly improve and extend past results on limits to efficient joint computation for multiple independent tasks; identify barriers to progress towards better circuit lower bounds for multiple-output operators; and begin an original line of inquiry into the complexity of joint computation.In more detail, we make contributions in the following areas:Improved direct product theorems for randomized query complexity: The "direct product problem" seeks to understand how the difficulty of computing a function on each of k independent inputs scales with k.We prove the following direct product theorem (DPT) for query complexity: if every T-query algorithm has success probability at most 1-e in computing the Boolean function f on input distribution p, then for a < 1, every aeTk-query algorithm has success probability at most (2 6(1 -E)) in computing the k-fold direct product f k correctly on k independent inputs from p.In light of examples due to Shaltiel, this statement gives an essentially optimal tradeoff between the query bound and the error probability.Using this DPT, we show that for an absolute constant a > 0, the worst-case success probability of any aR 2 (f)k-query randomized algorithm for f k falls exponentially with k.The best previous statement of this type, due to Klauck, Spalek, and de Wolf, required a query bound of O(bs(f)k).Our proof technique involves defining and analyzing a collection of martingales associated with an algorithm attempting to solve f*k.Our method is quite general This thesis was a long time in the making, and accordingly is indebted to many people.First of all, I would like to thank my advisor, Scott Aaronson, for the innumerable forms of support he has shown me over the years it's been my privilege to know him.Scott has always treated me as a colleague and an equal.He has always enthusiastically invited me to explore the many wonderful ideas that have excited him over the years, and has taught me a huge amount about computational complexity and allied fields.At the same time he has placed faith in me to plot my own course of research.My collaborations with Ronald de Wolf were in many ways akin to a second advisorship.In addition to sharing his scientific expertise, he generously shared his time to help me develop as a writer and editor.His formidable skills and work ethic have served as a model for me ever since.I am grateful to Russell Impagliazzo for his kind support and guidance during my first year of graduate study at UC San Diego.I thank Michael Sipser and Scott Aaronson for each giving me valuable teaching opportunities at MIT, and for leading by example with their own inspiring teaching.Fellow students have supported me and taught me a great deal over the years.Their guidance has come in many forms-from mathematical discussions, to practical advice about school and life.(I regard many of these talented individuals more as role models than as peers.)I have also valued their friendship and camaraderie through the academic process.A very partial list of fellow students who've given me valuable support and advice includes:

Related papers

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

Improved Direct Product Theorems for Randomized Query Complexity

Andrew Drucker

The "direct product problem" is a fundamental question in complexity theory which seeks to understand how the difficulty of computing a function on each of k independent inputs scales with k. We prove the following direct product theorem (DPT) for query complexity: if every T-query algorithm has success probability at most 1 - ε in computing the Boolean function f on input distribution μ, then for α ≤ 1, every αεTk-query algorithm has success probability at most (2αε(1 - ε))kin computing the fc-fold direct product f⊗kcorrectly on k independent inputs from μ. In light of examples due to Shaltiel, this statement gives an essentially optimal tradeoff between the query bound and the error probability. Using this DPT, we show that for an absolute constant α >; 0, the worst-case success probability of any αR2(f)k-query randomized algorithm for f⊗kfalls exponentially with k. The best previous statement of this type, due to Klauck, Spalek, and de Wolf, required a query bound of O(bs(f)k). Our proof technique involves defining and analyzing a collec tion of martingales associated with an algorithm attempting to solve f⊗k. Our method is quite general and yields a new XOR lemma and threshold DPT for the query model, as well as DPTs for the query complexity of learning tasks, search problems, and tasks involving interaction with dynamic entities. We also give a version of our DPT in which decision tree size is the resource of interest.

arXiv:1005.0644•IEEE Conference on Computational Complexity (CCC)•Jun 1, 2011•8 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

Direct Product Theorems for Randomized Query Complexity

Shalev Ben-David, Eric Blais

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.

Annual Symposium on Foundations of Computer Science•Dec 14, 2025•1 citation

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•5 citations

Quantum Computational Complexity Theory and Lower Bounds

Phillip Kaye, Raymond Laflamme, Michele Mosca

We have seen in the previous chapters that quantum computers seem to be more powerful than classical computers for certain problems. There are limits on the power of quantum computers, however. Since a classical computer can simulate a quantum computer, a quantum computer can only compute the same set of functions that a classical computer can. The advantage of using a quantum computer is that the amount of resources needed by a quantum algorithm might be much less than what is needed by the best classical algorithm. In Section 9.1 we briefly define some classical and quantum complexity classes and give some relationships between them. Most of the interesting questions relating classical and quantum complexity classes remain open. For example, we do not yet know if a quantum computer is capable of efficiently solving an NP-complete problem (defined later). One can prove upper bounds on the difficulty of a problem by providing an algorithm that solves that problem, and proving that it will work within in a given running time. But how does one prove a lower bound on the computational complexity of a problem? For example, if we wish to find the product of two n-bit numbers, computing the answer requires outputting roughly 2n bits and that requires Ω(n) steps (in any computing model with finite-sized gates). The best-known upper bound for integer multiplication is O(n log n log log n) steps. It has proved extremely difficult to derive non-trivial lower bounds on the computational complexity of a problem. Most of the known non-trivial lower bounds are in the ‘black-box’ model (for both classical and quantum computing), where we only query the input via a ‘black-box’ of a specific form. We discuss the black-box model in more detail in Section 9.2. We then sketch several approaches for proving black-box lower bounds. The first technique has been called the ‘hybrid method’ and was used to prove that quantum searching requires Ω(√n) queries to succeed with constant probability. The second technique is called the ‘polynomial method’. We then describe a technique based on ‘block sensitivity’, and conclude with a technique known as the ‘adversary method’.

Oxford University Press eBooks•Nov 16, 2006•0 citations
Joint computation is the ubiquitous scenario in which a computer is presented with not one, but many computational tasks to perform.A fundamental question arises: when can we cleverly combine computations, to perform them with greater efficiency or reliability than by tackling them separately?This thesis investigates the power and, especially, the limits of efficient joint computation, in several computational models: query algorithms, circuits, and Turing machines.We significantly improve and extend past results on limits to efficient joint computation for multiple independent tasks; identify barriers to progress towards better circuit lower bounds for multiple-output operators; and begin an original line of inquiry into the complexity of joint computation.In more detail, we make contributions in the following areas:Improved direct product theorems for randomized query complexity: The "direct product problem" seeks to understand how the difficulty of computing a function on each of k independent inputs scales with k.We prove the following direct product theorem (DPT) for query complexity: if every T-query algorithm has success probability at most 1-e in computing the Boolean function f on input distribution p, then for a < 1, every aeTk-query algorithm has success probability at most (2 6(1 -E)) in computing the k-fold direct product f k correctly on k independent inputs from p.In light of examples due to Shaltiel, this statement gives an essentially optimal tradeoff between the query bound and the error probability.Using this DPT, we show that for an absolute constant a > 0, the worst-case success probability of any aR 2 (f)k-query randomized algorithm for f k falls exponentially with k.The best previous statement of this type, due to Klauck, Spalek, and de Wolf, required a query bound of O(bs(f)k).Our proof technique involves defining and analyzing a collection of martingales associated with an algorithm attempting to solve f*k.Our method is quite general This thesis was a long time in the making, and accordingly is indebted to many people.First of all, I would like to thank my advisor, Scott Aaronson, for the innumerable forms of support he has shown me over the years it's been my privilege to know him.Scott has always treated me as a colleague and an equal.He has always enthusiastically invited me to explore the many wonderful ideas that have excited him over the years, and has taught me a huge amount about computational complexity and allied fields.At the same time he has placed faith in me to plot my own course of research.My collaborations with Ronald de Wolf were in many ways akin to a second advisorship.In addition to sharing his scientific expertise, he generously shared his time to help me develop as a writer and editor.His formidable skills and work ethic have served as a model for me ever since.I am grateful to Russell Impagliazzo for his kind support and guidance during my first year of graduate study at UC San Diego.I thank Michael Sipser and Scott Aaronson for each giving me valuable teaching opportunities at MIT, and for leading by example with their own inspiring teaching.Fellow students have supported me and taught me a great deal over the years.Their guidance has come in many forms-from mathematical discussions, to practical advice about school and life.(I regard many of these talented individuals more as role models than as peers.)I have also valued their friendship and camaraderie through the academic process.A very partial list of fellow students who've given me valuable support and advice includes:
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.
The "direct product problem" is a fundamental question in complexity theory which seeks to understand how the difficulty of computing a function on each of k independent inputs scales with k. We prove the following direct product theorem (DPT) for query complexity: if every T-query algorithm has success probability at most 1 - ε in computing the Boolean function f on input distribution μ, then for α ≤ 1, every αεTk-query algorithm has success probability at most (2αε(1 - ε))kin computing the fc-fold direct product f⊗kcorrectly on k independent inputs from μ. In light of examples due to Shaltiel, this statement gives an essentially optimal tradeoff between the query bound and the error probability. Using this DPT, we show that for an absolute constant α >; 0, the worst-case success probability of any αR2(f)k-query randomized algorithm for f⊗kfalls exponentially with k. The best previous statement of this type, due to Klauck, Spalek, and de Wolf, required a query bound of O(bs(f)k). Our proof technique involves defining and analyzing a collec tion of martingales associated with an algorithm attempting to solve f⊗k. Our method is quite general and yields a new XOR lemma and threshold DPT for the query model, as well as DPTs for the query complexity of learning tasks, search problems, and tasks involving interaction with dynamic entities. We also give a version of our DPT in which decision tree size is the resource of interest.
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.
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.
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 have seen in the previous chapters that quantum computers seem to be more powerful than classical computers for certain problems. There are limits on the power of quantum computers, however. Since a classical computer can simulate a quantum computer, a quantum computer can only compute the same set of functions that a classical computer can. The advantage of using a quantum computer is that the amount of resources needed by a quantum algorithm might be much less than what is needed by the best classical algorithm. In Section 9.1 we briefly define some classical and quantum complexity classes and give some relationships between them. Most of the interesting questions relating classical and quantum complexity classes remain open. For example, we do not yet know if a quantum computer is capable of efficiently solving an NP-complete problem (defined later). One can prove upper bounds on the difficulty of a problem by providing an algorithm that solves that problem, and proving that it will work within in a given running time. But how does one prove a lower bound on the computational complexity of a problem? For example, if we wish to find the product of two n-bit numbers, computing the answer requires outputting roughly 2n bits and that requires Ω(n) steps (in any computing model with finite-sized gates). The best-known upper bound for integer multiplication is O(n log n log log n) steps. It has proved extremely difficult to derive non-trivial lower bounds on the computational complexity of a problem. Most of the known non-trivial lower bounds are in the ‘black-box’ model (for both classical and quantum computing), where we only query the input via a ‘black-box’ of a specific form. We discuss the black-box model in more detail in Section 9.2. We then sketch several approaches for proving black-box lower bounds. The first technique has been called the ‘hybrid method’ and was used to prove that quantum searching requires Ω(√n) queries to succeed with constant probability. The second technique is called the ‘polynomial method’. We then describe a technique based on ‘block sensitivity’, and conclude with a technique known as the ‘adversary method’.