The Experts below are selected from a list of 315 Experts worldwide ranked by ideXlab platform
Rahul Jain - One of the best experts on this subject based on the ideXlab platform.
-
A Direct Product Theorem for One-Way Quantum Communication
arXiv: Computational Complexity, 2020Co-Authors: Rahul Jain, Srijita KunduAbstract:We prove a direct Product Theorem for the one-way entanglement-assisted quantum communication complexity of a general relation $f\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$. For any $\varepsilon, \zeta > 0$ and any $k\geq1$, we show that \[ \mathrm{Q}^1_{1-(1-\varepsilon)^{\Omega(\zeta^6k/\log|\mathcal{Z}|)}}(f^k) = \Omega\left(k\left(\zeta^5\cdot\mathrm{Q}^1_{\varepsilon + 12\zeta}(f) - \log\log(1/\zeta)\right)\right),\] where $\mathrm{Q}^1_{\varepsilon}(f)$ represents the one-way entanglement-assisted quantum communication complexity of $f$ with worst-case error $\varepsilon$ and $f^k$ denotes $k$ parallel instances of $f$. As far as we are aware, this is the first direct Product Theorem for quantum communication. Our techniques are inspired by the parallel repetition Theorems for the entangled value of two-player non-local games, under Product distributions due to Jain, Pereszlenyi and Yao, and under anchored distributions due to Bavarian, Vidick and Yuen, as well as message-compression for quantum protocols due to Jain, Radhakrishnan and Sen. Our techniques also work for entangled non-local games which have input distributions anchored on any one side. In particular, we show that for any game $G = (q, \mathcal{X}\times\mathcal{Y}, \mathcal{A}\times\mathcal{B}, \mathsf{V})$ where $q$ is a distribution on $\mathcal{X}\times\mathcal{Y}$ anchored on any one side with anchoring probability $\zeta$, then \[ \omega^*(G^k) = \left(1 - (1-\omega^*(G))^5\right)^{\Omega\left(\frac{\zeta^2 k}{\log(|\mathcal{A}|\cdot|\mathcal{B}|)}\right)}\] where $\omega^*(G)$ represents the entangled value of the game $G$. This is a generalization of the result of Bavarian, Vidick and Yuen, who proved a parallel repetition Theorem for games anchored on both sides, and potentially a simplification of their proof.
-
A Direct Product Theorem for Two-Party Bounded-Round Public-Coin Communication Complexity
Algorithmica, 2015Co-Authors: Rahul Jain, Attila Pereszlényi, Penghui YaoAbstract:A strong direct Product Theorem for a problem in a given model of computation states that, in order to compute k instances of the problem, if we provide resource which is less than k times the resource required for computing one instance of the problem with constant success probability, then the probability of correctly computing all the k instances together, is exponentially small in k. In this paper, we consider the model of two-party bounded-round public-coin randomized communication complexity. We show a direct Product Theorem for the communication complexity of any complete relation in this model. In particular, our result implies a strong direct Product Theorem for the two-party constant-round public-coin randomized communication complexity of all complete relations. As an immediate application of our result, we get a strong direct Product Theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols. Our result generalizes the result of Jain which can be regarded as the special case when the number of messages is one. Our result can be considered as an important progress towards settling the strong direct Product conjecture for two-party public-coin communication complexity, a major open question in this area. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used by Jain. One key tool used in our work and also by Jain is a message compression technique due to Braverman and Rao, who used it to show a direct sum Theorem in the same model of communication complexity as considered by us. Another important tool that we use is a correlated sampling protocol which, for example, has been used by Holenstein for proving a parallel repetition Theorem for two-prover games.
-
a strong direct Product Theorem for the tribes function via the smooth rectangle bound
Foundations of Software Technology and Theoretical Computer Science, 2013Co-Authors: Prahladh Harsha, Rahul JainAbstract:The main result of this paper is an optimal strong direct Product result for the two-party public-coin randomized communication complexity of the Tribes function. This is proved by providing an alternate proof of the optimal lower bound of Omega(n) for the randomised communication complexity of the Tribes function using the so-called smooth-rectangle bound, introduced by Jain and Klauck [CCC/2010]. The optimal Omega(n) lower bound for Tribes was originally proved by Jayram, Kumar and Sivakumar [STOC/2003], using a more powerful lower bound technique, namely the information complexity bound. The information complexity bound is known to be at least as strong a lower bound method as the smooth-rectangle bound [Kerenidis et al, 2012]. On the other hand, we are not aware of any function or relation for which the smooth-rectangle bound is (asymptotically) smaller than its public-coin randomized communication complexity. The optimal direct Product for Tribes is obtained by combining our smooth-rectangle bound for tribes with the strong direct Product result of Jain and Yao (2012) in terms of smooth-rectangle bound.
-
a strong direct Product Theorem for the tribes function via the smooth rectangle bound
arXiv: Computational Complexity, 2013Co-Authors: Prahladh Harsha, Rahul JainAbstract:The main result of this paper is an optimal strong direct Product result for the two-party public-coin randomized communication complexity of the Tribes function. This is proved by providing an alternate proof of the optimal lower bound of \Omega(n) for the randomised communication complexity of the Tribes function using the so-called smooth-rectangle bound, introduced by Jain and Klauck [JK10]. The optimal \Omega(n) lower bound for Tribes was originally proved by Jayram, Kumar and Sivakumar [JKS03], using a more powerful lower bound technique, namely the information complexity bound. The information complexity bound is known to be at least as strong a lower bound method as the smooth-rectangle bound [KLL+12]. On the other hand, we are not aware of any function or relation for which the smooth-rectangle bound is (asymptotically) smaller than its public-coin randomized communication complexity. The optimal direct Product for Tribes is obtained by combining our smooth-rectangle bound for tribes with the strong direct Product result of Jain and Yao [JY12] in terms of smooth-rectangle bound.
-
a direct Product Theorem for the two party bounded round public coin communication complexity
Foundations of Computer Science, 2012Co-Authors: Rahul Jain, Attila Pereszlényi, Penghui YaoAbstract:A strong direct Product Theorem for a problem in a given model of computation states that, in order to compute k instances of the problem, if we provide resource which is less than k times the resource required for computing one instance of the problem with constant success probability, then the probability of correctly computing all the k instances together, is exponentially small in k. In this paper, we consider the model of two-party bounded-round public-coin randomized communication complexity. We show a direct Product Theorem for the communication complexity of any relation in this model. In particular, our result implies a strong direct Product Theorem for the two-party constant-message public-coin randomized communication complexity of all relations. As an immediate application of our result, we get a strong direct Product Theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols. Our result generalizes the result of Jain [2011] which can be regarded as the special case when t=1. Our result can be considered as an important progress towards settling the strong direct Product conjecture for the two-party public-coin communication complexity, a major open question in this area. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used in Jain~\cite{Jain:2011}. %, where a strong direct Product Theorem for the %two-party one-way public-coin communication complexity of all %relations is shown (that is the special case of our result when $t=1$). One key tool used in our work and also in Jain~\cite{Jain:2011} is a message compression technique due to Braver man and Rao~\cite{Braverman2011}, who used it to show a {\em direct sum} Theorem in the same model of communication complexity as considered by us. Another important tool that we use is a correlated sampling protocol, which for example, has been used in Holenstein~\cite{Holenstein2007} for proving a parallel repetition Theorem for two-prover games.
Penghui Yao - One of the best experts on this subject based on the ideXlab platform.
-
A Direct Product Theorem for Two-Party Bounded-Round Public-Coin Communication Complexity
Algorithmica, 2015Co-Authors: Rahul Jain, Attila Pereszlényi, Penghui YaoAbstract:A strong direct Product Theorem for a problem in a given model of computation states that, in order to compute k instances of the problem, if we provide resource which is less than k times the resource required for computing one instance of the problem with constant success probability, then the probability of correctly computing all the k instances together, is exponentially small in k. In this paper, we consider the model of two-party bounded-round public-coin randomized communication complexity. We show a direct Product Theorem for the communication complexity of any complete relation in this model. In particular, our result implies a strong direct Product Theorem for the two-party constant-round public-coin randomized communication complexity of all complete relations. As an immediate application of our result, we get a strong direct Product Theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols. Our result generalizes the result of Jain which can be regarded as the special case when the number of messages is one. Our result can be considered as an important progress towards settling the strong direct Product conjecture for two-party public-coin communication complexity, a major open question in this area. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used by Jain. One key tool used in our work and also by Jain is a message compression technique due to Braverman and Rao, who used it to show a direct sum Theorem in the same model of communication complexity as considered by us. Another important tool that we use is a correlated sampling protocol which, for example, has been used by Holenstein for proving a parallel repetition Theorem for two-prover games.
-
a direct Product Theorem for the two party bounded round public coin communication complexity
Foundations of Computer Science, 2012Co-Authors: Rahul Jain, Attila Pereszlényi, Penghui YaoAbstract:A strong direct Product Theorem for a problem in a given model of computation states that, in order to compute k instances of the problem, if we provide resource which is less than k times the resource required for computing one instance of the problem with constant success probability, then the probability of correctly computing all the k instances together, is exponentially small in k. In this paper, we consider the model of two-party bounded-round public-coin randomized communication complexity. We show a direct Product Theorem for the communication complexity of any relation in this model. In particular, our result implies a strong direct Product Theorem for the two-party constant-message public-coin randomized communication complexity of all relations. As an immediate application of our result, we get a strong direct Product Theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols. Our result generalizes the result of Jain [2011] which can be regarded as the special case when t=1. Our result can be considered as an important progress towards settling the strong direct Product conjecture for the two-party public-coin communication complexity, a major open question in this area. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used in Jain~\cite{Jain:2011}. %, where a strong direct Product Theorem for the %two-party one-way public-coin communication complexity of all %relations is shown (that is the special case of our result when $t=1$). One key tool used in our work and also in Jain~\cite{Jain:2011} is a message compression technique due to Braver man and Rao~\cite{Braverman2011}, who used it to show a {\em direct sum} Theorem in the same model of communication complexity as considered by us. Another important tool that we use is a correlated sampling protocol, which for example, has been used in Holenstein~\cite{Holenstein2007} for proving a parallel repetition Theorem for two-prover games.
-
A strong direct Product Theorem in terms of the smooth rectangle bound
arXiv: Computational Complexity, 2012Co-Authors: Rahul Jain, Penghui YaoAbstract: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 \gamma_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].
-
A direct Product Theorem for bounded-round public-coin randomized communication complexity
arXiv: Computational Complexity, 2012Co-Authors: Rahul Jain, Attila Pereszlényi, Penghui YaoAbstract:A strong direct Product Theorem for a problem in a given model of computation states that, in order to compute k instances of the problem, if we provide resource which is less than k times the resource required for computing one instance of the problem with constant success probability, then the probability of correctly computing all the k instances together, is exponentially small in k. In this paper, we consider the model of two-party bounded-round public-coin randomized communication complexity. For a relation f ⊆ X ×Y×Z (X,Y,Z are finite sets), let R (t),pub " (f) denote the two-party t-message public-coin communication complexity of f with worst case error e. We show that for any relation f and integer k ≥ 1
-
FOCS - A Direct Product Theorem for the Two-Party Bounded-Round Public-Coin Communication Complexity
2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, 2012Co-Authors: Rahul Jain, Attila Pereszlényi, Penghui YaoAbstract:A strong direct Product Theorem for a problem in a given model of computation states that, in order to compute k instances of the problem, if we provide resource which is less than k times the resource required for computing one instance of the problem with constant success probability, then the probability of correctly computing all the k instances together, is exponentially small in k. In this paper, we consider the model of two-party bounded-round public-coin randomized communication complexity. We show a direct Product Theorem for the communication complexity of any relation in this model. In particular, our result implies a strong direct Product Theorem for the two-party constant-message public-coin randomized communication complexity of all relations. As an immediate application of our result, we get a strong direct Product Theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols. Our result generalizes the result of Jain [2011] which can be regarded as the special case when t=1. Our result can be considered as an important progress towards settling the strong direct Product conjecture for the two-party public-coin communication complexity, a major open question in this area. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used in Jain~\cite{Jain:2011}. %, where a strong direct Product Theorem for the %two-party one-way public-coin communication complexity of all %relations is shown (that is the special case of our result when $t=1$). One key tool used in our work and also in Jain~\cite{Jain:2011} is a message compression technique due to Braver man and Rao~\cite{Braverman2011}, who used it to show a {\em direct sum} Theorem in the same model of communication complexity as considered by us. Another important tool that we use is a correlated sampling protocol, which for example, has been used in Holenstein~\cite{Holenstein2007} for proving a parallel repetition Theorem for two-prover games.
Jeremie Roland - One of the best experts on this subject based on the ideXlab platform.
-
A strong direct Product Theorem for quantum query complexity
computational complexity, 2013Co-Authors: Troy Lee, Jeremie RolandAbstract:We show that quantum query complexity satisfies a strong direct Product Theorem. This means that computing k copies of a function with fewer 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 fewer 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.
-
a strong direct Product Theorem for quantum query complexity
Conference on Computational Complexity, 2012Co-Authors: Troy Lee, Jeremie RolandAbstract: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.
-
IEEE Conference on Computational Complexity - A Strong Direct Product Theorem for Quantum Query Complexity
2012 IEEE 27th Conference on Computational Complexity, 2012Co-Authors: Troy Lee, Jeremie RolandAbstract: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.
-
a strong direct Product Theorem for quantum query complexity
arXiv: Quantum Physics, 2011Co-Authors: Troy Lee, Jeremie RolandAbstract: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, is always at least as large as the additive adversary method, which is known to characterize quantum query complexity.
Troy Lee - One of the best experts on this subject based on the ideXlab platform.
-
A strong direct Product Theorem for quantum query complexity
computational complexity, 2013Co-Authors: Troy Lee, Jeremie RolandAbstract:We show that quantum query complexity satisfies a strong direct Product Theorem. This means that computing k copies of a function with fewer 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 fewer 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.
-
a strong direct Product Theorem for quantum query complexity
Conference on Computational Complexity, 2012Co-Authors: Troy Lee, Jeremie RolandAbstract: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.
-
IEEE Conference on Computational Complexity - A Strong Direct Product Theorem for Quantum Query Complexity
2012 IEEE 27th Conference on Computational Complexity, 2012Co-Authors: Troy Lee, Jeremie RolandAbstract: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.
-
a strong direct Product Theorem for quantum query complexity
arXiv: Quantum Physics, 2011Co-Authors: Troy Lee, Jeremie RolandAbstract: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, is always at least as large as the additive adversary method, which is known to characterize quantum query complexity.
-
a direct Product Theorem for discrepancy
Conference on Computational Complexity, 2008Co-Authors: Troy Lee, Adi Shraibman, Robert SpalekAbstract:Discrepancy is a versatile bound in communication complexity which can be used to show lower bounds in randomized, quantum, and even weakly-unbounded error models of communication. We show an optimal Product Theorem for discrepancy, namely that for any two Boolean functions f, g, disc(f odot g)=thetas(disc(f) disc(g)). As a consequence we obtain a strong direct Product Theorem for distributional complexity, and direct sum Theorems for worst-case complexity, for bounds shown by the discrepancy method. Our results resolve an open problem of Shaltiel (2003) who showed a weaker Product Theorem for discrepancy with respect to the uniform distribution, discUodot(fodotk)=O(discU(f))k/3. The main tool for our results is semidefinite programming, in particular a recent characterization of discrepancy in terms of a semidefinite programming quantity by Linial and Shraibman (2006).
R. De Wolf - One of the best experts on this subject based on the ideXlab platform.
-
A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs
Algorithmica, 2009Co-Authors: Andris Ambainis, Robert Spalek, R. De WolfAbstract:We give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and optimal strong direct Product Theorem for 2-sided error quantum algorithms computing k independent instances of a symmetric Boolean function: if the algorithm uses significantly less than k times the number of queries needed for one instance of the function, then its success probability is exponentially small in k . We also use the polynomial method to prove a direct Product Theorem for 1-sided error algorithms for k threshold functions with a stronger bound on the success probability. Finally, we present a quantum algorithm for evaluating solutions to systems of linear inequalities, and use our direct Product Theorems to show that the time-space tradeoff of this algorithm is close to optimal.
-
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs
SIAM Journal on Computing, 2007Co-Authors: Hartmut Klauck, Robert S Caron, Palek, R. De WolfAbstract: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.
-
STOC - A new quantum lower bound method,: with applications to direct Product Theorems and time-space tradeoffs
Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06, 2006Co-Authors: Andris Ambainis, Robert Spalek, R. De WolfAbstract:We give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and optimal strong direct Product Theorem for 2-sided error quantum algorithms computing k independent instances of a symmetric Boolean function: if the algorithm uses significantly less than k times the number of queries needed for one instance of the function, then its success probability is exponentially small in k. We also use the polynomial method to prove a direct Product Theorem for 1-sided error algorithms for k threshold functions with a stronger bound on the success probability. Finally, we present a quantum algorithm for evaluating solutions to systems of linear inequalities, and use our direct Product Theorems to show that the time-space tradeoff of this algorithm is close to optimal.
-
Quantum Direct Product Theorems for Symmetric Functions and Time-Space Tradeoffs
2005Co-Authors: Andris Ambainis, Robert Spalek, R. De WolfAbstract:A direct Product Theorem upper-bounds the overall success probability of algorithms for computing many independent instances of a computational problem. We prove a direct Product Theorem for 2-sided error algorithms for symmetric functions in the setting of quantum query complexity, and a stronger direct Product Theorem for 1-sided error algorithms for threshold functions. We also present a quantum algorithm for deciding systems of linear inequalities, and use our direct Product Theorems to show that the time-space tradeoff of this algorithm is close to optimal.
-
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs
arXiv: Quantum Physics, 2004Co-Authors: Hartmut Klauck, Robert Spalek, R. De WolfAbstract: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.
