Complexity Beyond Classical Limits: A Study of Quantum Query and Communication Models

A fundamental question in computer science is: Is it harder to solve $n$ instances independently than to solve them simultaneously? This question, known as the direct sum question or direct sum theorem, has been paid much attention in several research fields. Despite its importance, however, little has been discovered in many other research fields. In this paper, we introduce a novel framework that extends to classical/quantum query complexity, PAC-learning for machine learning, statistical estimation theory, and more. Within this framework, we establish several fundamental direct sum theorems. The main contributions of this paper include: (i) establishing a complete characterization of the amortized query/oracle complexities, and (ii) proving tight direct sum theorems when the error is small. Note that in our framework, every oracle access needs to be performed \emph{classically} even in the quantum setting. This can be thought of one limitation of this work. As a direct consequence of our results, we obtain the following: (A) The first known asymptotic separation of the randomized query complexity. Specifically, we show that there is a function $f: \{0, 1\}^k \to \{0, 1\}$ and small error $\varepsilon > 0$ such that solving $n$ instances simultaneously requires the query complexity $\tilde{O}(n\sqrt{k})$ but solving one instance with the same error has the complexity $\tildeΩ(k)$ . In communication complexity this type of separation was previously given in~Feder, Kushilevitz, Naor and Nisan (1995). (B) The query complexity counterpart of the ``information = amortized communication" relation, one of the most influential results in communication complexity shown by Braverman and Rao (2011) and further investigated by Braverman (2015). We hope that our results will provide further interesting applications in the future.A fundamental question in computer science is: Is it harder to solve $n$ instances independently than to solve them simultaneously? This question, known as the direct sum question or direct sum theorem, has been paid much attention in several research fields. Despite its importance, however, little has been discovered in many other research fields. In this paper, we introduce a novel framework that extends to classical/quantum query complexity, PAC-learning for machine learning, statistical estimation theory, and more. Within this framework, we establish several fundamental direct sum theorems. The main contributions of this paper include: (i) establishing a complete characterization of the amortized query/oracle complexities, and (ii) proving tight direct sum theorems when the error is small. Note that in our framework, every oracle access needs to be performed \emph{classically} even in the quantum setting. This can be thought of one limitation of this work. As a direct consequence of our results, we obtain the following: (A) The first known asymptotic separation of the randomized query complexity. Specifically, we show that there is a function $f: \{0, 1\}^k \to \{0, 1\}$ and small error $\varepsilon > 0$ such that solving $n$ instances simultaneously requires the query complexity $\tilde{O}(n\sqrt{k})$ but solving one instance with the same error has the complexity $\tildeΩ(k)$. In communication complexity this type of separation was previously given in~Feder, Kushilevitz, Naor and Nisan (1995). (B) The query complexity counterpart of the ``information = amortized communication" relation, one of the most influential results in communication complexity shown by Braverman and Rao (2011) and further investigated by Braverman (2015). We hope that our results will provide further interesting applications in the future.

arXiv:2408.15570Aug 28, 20240 citations

Quantum Computing and Communication Complexity

Ronald de Wolf

Sep 1, 200165 citations

On the power of quantum proofs

Ran Raz, Amir Shpilka

We study the power of quantum proofs, or more precisely, the power of quantum Merlin-Arthur (QMA) protocols, in two well studied models of quantum computation: the black box model and the communication complexity model. Our main results are obtained for the communication complexity model. For this model, we identify a complete promise problem for QMA protocols, the linear sub-spaces distance problem. The problem is of geometrical nature: each player gets a linear subspace of R/sup m/ and considers the sphere of unit vectors in that subspace. Their goal is to output 1 if the distance between the two spheres is very small (say, smaller than 0.1 /spl middot/ /spl radic/2) and 0 if the distance is very large (say, larger than 0.9 /spl middot/ /spl radic/2). We show that: 1. The QMA communication complexity of the problem is O(logm). 2. The (classical) MA communication complexity of the problem is /spl Omega/(m/sup /spl epsi//) (for some /spl epsi/ > 0). 3. The (standard) quantum communication complexity of the problem is /spl Omega/(/spl radic/m). In particular, this gives an exponential separation between QMA communication complexity and MA communication complexity. For the black box model we give several observations. First, we observe that the block sensitivity method, as well as the polynomial method for proving lower bounds for the number of queries, can both be extended to QMA protocols. We use these methods to obtain lower bounds for the QMA black box complexity of functions. In particular, we obtain a tight lower bound of /spl Omega/(N) for the QMA black box complexity of a random function, and a tight lower bound of /spl Omega/(/spl radic/N) for the QMA black box query complexity of NOR(X/sub 1/,..., X/sub n/). In particular, this shows that any attempt to give short quantum proofs for the class of languages Co - NP have to go beyond black box arguments. We also observe that for any Boolean function G(X/sub 1/,..., X/sub n/), if for both G and 7minus;G there are QMA black box protocols that make at most T queries to the black box, then there is a classical deterministic black box protocol for G that makes 0(T/sup 6/) queries to the black box. In particular, this shows that in the black box model QMA /spl cap/ Co - QMA = P. On the positive side, we observe that any (total or partial) Boolean function G(X/sub 1/,..., X/sub n/) has a QMA black box protocol with proofs of length N that makes only 0(/spl radic/N) queries to the black box. Finally, we observe a very simple proof for the exponential separation (for promise problems) between QMA black box complexity and (classical) MA black box complexity (first obtained by Watrous).We study the power of quantum proofs, or more precisely, the power of quantum Merlin-Arthur (QMA) protocols, in two well studied models of quantum computation: the black box model and the communication complexity model. Our main results are obtained for the communication complexity model. For this model, we identify a complete promise problem for QMA protocols, the linear sub-spaces distance problem. The problem is of geometrical nature: each player gets a linear subspace of R/sup m/ and considers the sphere of unit vectors in that subspace. Their goal is to output 1 if the distance between the two spheres is very small (say, smaller than 0.1 /spl middot/ /spl radic/2) and 0 if the distance is very large (say, larger than 0.9 /spl middot/ /spl radic/2). We show that: 1. The QMA communication complexity of the problem is O(logm). 2. The (classical) MA communication complexity of the problem is /spl Omega/(m/sup /spl epsi//) (for some /spl epsi/ > 0). 3. The (standard) quantum communication complexity of the problem is /spl Omega/(/spl radic/m). In particular, this gives an exponential separation between QMA communication complexity and MA communication complexity. For the black box model we give several observations. First, we observe that the block sensitivity method, as well as the polynomial method for proving lower bounds for the number of queries, can both be extended to QMA protocols. We use these methods to obtain lower bounds for the QMA black box complexity of functions. In particular, we obtain a tight lower bound of /spl Omega/(N) for the QMA black box complexity of a random function, and a tight lower bound of /spl Omega/(/spl radic/N) for the QMA black box query complexity of NOR(X/sub 1/,..., X/sub n/). In particular, this shows that any attempt to give short quantum proofs for the class of languages Co - NP have to go beyond black box arguments. We also observe that for any Boolean function G(X/sub 1/,..., X/sub n/), if for both G and 7minus;G there are QMA black box protocols that make at most T queries to the black box, then there is a classical deterministic black box protocol for G that makes 0(T/sup 6/) queries to the black box. In particular, this shows that in the black box model QMA /spl cap/ Co - QMA = P. On the positive side, we observe that any (total or partial) Boolean function G(X/sub 1/,..., X/sub n/) has a QMA black box protocol with proofs of length N that makes only 0(/spl radic/N) queries to the black box. Finally, we observe a very simple proof for the exponential separation (for promise problems) between QMA black box complexity and (classical) MA black box complexity (first obtained by Watrous).

IEEE Conference on Computational Complexity (CCC)Nov 12, 200412 citations

Query-to-Communication Lifting for BPP

Mika Göös, Toniann Pitassi, Thomas W. Watson

For any $n$ -bit boolean function $f$ , we show that the randomized communication complexity of the composed function $f\circ g^n$ , where $g$ is an index gadget, is characterized by the randomized decision tree complexity of $f$ . In particular, this means that many query complexity separations involving randomized models (e.g., classical vs. quantum) automatically imply analogous separations in communication complexity.For any $n$-bit boolean function $f$, we show that the randomized communication complexity of the composed function $f\circ g^n$, where $g$ is an index gadget, is characterized by the randomized decision tree complexity of $f$. In particular, this means that many query complexity separations involving randomized models (e.g., classical vs. quantum) automatically imply analogous separations in communication complexity.

arXiv:1703.07666Annual Symposium on Foundations of Computer ScienceOct 1, 201754 citations

A fundamental question in computer science is: Is it harder to solve

n

instances independently than to solve them simultaneously? This question, known as the direct sum question or direct sum theorem, has been paid much attention in several research fields. Despite its importance, however, little has been discovered in many other research fields. In this paper, we introduce a novel framework that extends to classical/quantum query complexity, PAC-learning for machine learning, statistical estimation theory, and more. Within this framework, we establish several fundamental direct sum theorems. The main contributions of this paper include: (i) establishing a complete characterization of the amortized query/oracle complexities, and (ii) proving tight direct sum theorems when the error is small. Note that in our framework, every oracle access needs to be performed \emph{classically} even in the quantum setting. This can be thought of one limitation of this work. As a direct consequence of our results, we obtain the following: (A) The first known asymptotic separation of the randomized query complexity. Specifically, we show that there is a function

f: \{0, 1\}^k \to \{0, 1\}

and small error

\varepsilon > 0

such that solving

n

instances simultaneously requires the query complexity

\tilde{O}(n\sqrt{k})

but solving one instance with the same error has the complexity

\tildeΩ(k)

. In communication complexity this type of separation was previously given in~Feder, Kushilevitz, Naor and Nisan (1995). (B) The query complexity counterpart of the ``information = amortized communication" relation, one of the most influential results in communication complexity shown by Braverman and Rao (2011) and further investigated by Braverman (2015). We hope that our results will provide further interesting applications in the future.

For any

n

-bit boolean function

f

, we show that the randomized communication complexity of the composed function

f\circ g^n

, where

g

is an index gadget, is characterized by the randomized decision tree complexity of

f

. In particular, this means that many query complexity separations involving randomized models (e.g., classical vs. quantum) automatically imply analogous separations in communication complexity.