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:quant-ph/0610085

A lower bound on entanglement-assisted quantum communication complexity

Ashley Montanaro, Andreas Winter

Published Oct 11, 2006• 0 citations
arXivHTMLPDF

Abstract

We prove a general lower bound on the bounded-error entanglement-assisted quantum communication complexity of Boolean functions. The bound is based on the concept that any classical or quantum protocol to evaluate a function on distributed inputs can be turned into a quantum communication protocol. As an application of this bound, we give a very simple proof of the statement that almost all Boolean functions on n+n bits have linear communication complexity, even in the presence of unlimited entanglement.

DOI
10.48550/arxiv.quant-ph/0610085

Related papers

Lower Bounds for Quantum Communication Complexity

Hartmut Klauck

We prove lower bounds on the bounded error quantum communication complexity. Our methods are based on the Fourier transform of the considered functions. First we generalize a method for proving classical communication complexity lower bounds developed by Raz [Comput. Complexity, 5 (1995), pp. 205–221] to the quantum case. Applying this method, we give an exponential separation between bounded error quantum communication complexity and nondeterministic quantum communication complexity. We develop several other lower bound methods based on the Fourier transform, notably showing that $\sqrt{\bar{s}(f)/\log n}$, for the average sensitivity $\bar{s}(f)$ of a function f, yields a lower bound on the bounded error quantum communication complexity of $f((x \wedge y)\oplus z)$, where x is a Boolean word held by Alice and $y,z$ are Boolean words held by Bob. We then prove the first large lower bounds on the bounded error quantum communication complexity of functions, for which a polynomial quantum speedup is possible. For all the functions we investigate, the only previously applied general lower bound method based on discrepancy yields bounds that are $O(\log n)$.

SIAM Journal on Computing•Jan 1, 2007•68 citations

Communication complexity lower bounds by polynomials

Harry Buhrman, Ronald de Wolf

The quantum version of communication complexity allows the two communicating parties to exchange qubits and/or to make use of prior entanglement (shared EPR-pairs). Some lower bound techniques are available for qubit communication complexity, but except for the inner product function, no bounds are known for the model with unlimited prior entanglement. We show that the "log rank" lower bound extends to the strongest variant of quantum communication complexity (qubit communication+unlimited prior entanglement). By relating the rank of the communication matrix to properties of polynomials, we are able to derive some strong bounds for exact protocols. In particular, we prove both the "log rank conjecture" and the polynomial equivalence of quantum and classical communication complexity for various classes of functions. We also derive some weaker bounds for bounded-error quantum protocols.

arXiv:cs/9910010•IEEE Conference on Computational Complexity (CCC)•Nov 13, 2002•127 citations

Lower bounds for quantum communication complexity

Hartmut Klauck

We prove new lower bounds for bounded error quantum communication complexity. Our methods are based on the Fourier transform of the considered functions. First we generalize a method for proving classical communication complexity lower bounds developed by Raz to the quantum case. Applying this method we give an exponential separation between bounded error quantum communication complexity and nondeterministic quantum communication complexity. We develop several other lower bound methods based on the Fourier transform, notably showing that \sqrt{\bar{s}(f)/\log n}, for the average sensitivity \bar{s}(f) of a function f, yields a lower bound on the bounded error quantum communication complexity of f(x AND y XOR z), where x is a Boolean word held by Alice and y,z are Boolean words held by Bob. We then prove the first large lower bounds on the bounded error quantum communication complexity of functions, for which a polynomial quantum speedup is possible. For all the functions we investigate, the only previously applied general lower bound method based on discrepancy yields bounds that are O(\log n).

arXiv:quant-ph/0106160•Jun 28, 2001•44 citations

Renyi-entropic bounds on quantum communication

Wim van Dam, Patrick M. Hayden

In this article we establish new bounds on the quantum communication complexity of distributed problems. Specifically, we consider the amount of communication that is required to transform a bipartite state into another, typically more entangled, state. We obtain lower bounds in this setting by studying the Renyi entropy of the marginal density matrices of the distributed system. The communication bounds on quantum state transformations also imply lower bounds for the model of communication complexity where the task consists of the the distributed evaluation of a function f(x,y). Our approach encapsulates several known lower bound methods that use the log-rank or the von Neumann entropy of the density matrices involved. The technique is also effective for proving lower bounds on problems involving a promise or for which the "hard" distributions of inputs are correlated. As examples, we show how to prove a nearly tight bound on the bounded-error quantum communication complexity of the inner product function in the presence of unlimited amounts of EPR-type entanglement and a similarly strong bound on the complexity of the shifted quadratic character problem.

arXiv:quant-ph/0204093•Apr 17, 2002•27 citations

Communication Complexity of Entanglement-Assisted Multi-Party Computation

Ruoyu Meng, Aditya Ramamoorthy

We consider a quantum and a classical version of a multi-party function computation problem with n players, where players 2,…,n need to communicate appropriate information to player 1 so that a “generalized” inner product function with an appropriate promise can be calculated. In the quantum version of the protocol, the players have access to entangled qudits but the communication is still classical. The communication complexity of a given protocol is the total number of classical bits that need to be communicated. When n is prime, and for our chosen function, we exhibit a quantum protocol (with complexity (n−1)(logn) bits) and a classical protocol (with complexity ((n−1)2(logn2) bits)). Furthermore, we present an integer linear programming formulation for determining a lower bound on the classical communication complexity. This demonstrates that our quantum protocol is strictly better than classical protocols.

arXiv:2305.04435•Entropy•Oct 23, 2024•1 citation

Lower bounds for quantum communication complexity

Hartmut Klauck

We prove new lower bounds for bounded error quantum communication complexity. Our methods are based on the Fourier transform of the considered functions. First we generalize a method for proving classical communication complexity lower bounds developed by R. Raz (1995) to the quantum case. Applying this method we give an exponential separation between bounded error quantum communication complexity and nondeterministic quantum communication complexity. We develop several other Fourier based lower bound methods, notably showing that /spl radic/(s~(f)/log n) n, for the average sensitivity s~(f) of a function f, yields a lower bound on the bounded error quantum communication complexity of f (x/spl and/y/spl oplus/yz), where x is a Boolean word held by Alice and y, z are Boolean words held by Bob. We then prove the first large lower bounds on the bounded error quantum communication complexity of functions, for which a polynomial quantum speedup is possible. For all the functions we investigate, only the previously applied general lower bound method based on discrepancy yields bounds that are O(log n).

Annual Symposium on Foundations of Computer Science•Jan 1, 2001•30 citations
We prove a general lower bound on the bounded-error entanglement-assisted quantum communication complexity of Boolean functions. The bound is based on the concept that any classical or quantum protocol to evaluate a function on distributed inputs can be turned into a quantum communication protocol. As an application of this bound, we give a very simple proof of the statement that almost all Boolean functions on n+n bits have linear communication complexity, even in the presence of unlimited entanglement.
We prove lower bounds on the bounded error quantum communication complexity. Our methods are based on the Fourier transform of the considered functions. First we generalize a method for proving classical communication complexity lower bounds developed by Raz [Comput. Complexity, 5 (1995), pp. 205–221] to the quantum case. Applying this method, we give an exponential separation between bounded error quantum communication complexity and nondeterministic quantum communication complexity. We develop several other lower bound methods based on the Fourier transform, notably showing that sˉ(f)/log⁡n\sqrt{\bar{s}(f)/\log n}sˉ(f)/logn​, for the average sensitivity sˉ(f)\bar{s}(f)sˉ(f) of a function f, yields a lower bound on the bounded error quantum communication complexity of f((x∧y)⊕z)f((x \wedge y)\oplus z)f((x∧y)⊕z), where x is a Boolean word held by Alice and y,zy,zy,z are Boolean words held by Bob. We then prove the first large lower bounds on the bounded error quantum communication complexity of functions, for which a polynomial quantum speedup is possible. For all the functions we investigate, the only previously applied general lower bound method based on discrepancy yields bounds that are O(log⁡n)O(\log n)O(logn).
The quantum version of communication complexity allows the two communicating parties to exchange qubits and/or to make use of prior entanglement (shared EPR-pairs). Some lower bound techniques are available for qubit communication complexity, but except for the inner product function, no bounds are known for the model with unlimited prior entanglement. We show that the "log rank" lower bound extends to the strongest variant of quantum communication complexity (qubit communication+unlimited prior entanglement). By relating the rank of the communication matrix to properties of polynomials, we are able to derive some strong bounds for exact protocols. In particular, we prove both the "log rank conjecture" and the polynomial equivalence of quantum and classical communication complexity for various classes of functions. We also derive some weaker bounds for bounded-error quantum protocols.
We prove new lower bounds for bounded error quantum communication complexity. Our methods are based on the Fourier transform of the considered functions. First we generalize a method for proving classical communication complexity lower bounds developed by Raz to the quantum case. Applying this method we give an exponential separation between bounded error quantum communication complexity and nondeterministic quantum communication complexity. We develop several other lower bound methods based on the Fourier transform, notably showing that \sqrt{\bar{s}(f)/\log n}, for the average sensitivity \bar{s}(f) of a function f, yields a lower bound on the bounded error quantum communication complexity of f(x AND y XOR z), where x is a Boolean word held by Alice and y,z are Boolean words held by Bob. We then prove the first large lower bounds on the bounded error quantum communication complexity of functions, for which a polynomial quantum speedup is possible. For all the functions we investigate, the only previously applied general lower bound method based on discrepancy yields bounds that are O(\log n).
In this article we establish new bounds on the quantum communication complexity of distributed problems. Specifically, we consider the amount of communication that is required to transform a bipartite state into another, typically more entangled, state. We obtain lower bounds in this setting by studying the Renyi entropy of the marginal density matrices of the distributed system. The communication bounds on quantum state transformations also imply lower bounds for the model of communication complexity where the task consists of the the distributed evaluation of a function f(x,y). Our approach encapsulates several known lower bound methods that use the log-rank or the von Neumann entropy of the density matrices involved. The technique is also effective for proving lower bounds on problems involving a promise or for which the "hard" distributions of inputs are correlated. As examples, we show how to prove a nearly tight bound on the bounded-error quantum communication complexity of the inner product function in the presence of unlimited amounts of EPR-type entanglement and a similarly strong bound on the complexity of the shifted quadratic character problem.
We consider a quantum and a classical version of a multi-party function computation problem with n players, where players 2,…,n need to communicate appropriate information to player 1 so that a “generalized” inner product function with an appropriate promise can be calculated. In the quantum version of the protocol, the players have access to entangled qudits but the communication is still classical. The communication complexity of a given protocol is the total number of classical bits that need to be communicated. When n is prime, and for our chosen function, we exhibit a quantum protocol (with complexity (n−1)(logn) bits) and a classical protocol (with complexity ((n−1)2(logn2) bits)). Furthermore, we present an integer linear programming formulation for determining a lower bound on the classical communication complexity. This demonstrates that our quantum protocol is strictly better than classical protocols.
We prove new lower bounds for bounded error quantum communication complexity. Our methods are based on the Fourier transform of the considered functions. First we generalize a method for proving classical communication complexity lower bounds developed by R. Raz (1995) to the quantum case. Applying this method we give an exponential separation between bounded error quantum communication complexity and nondeterministic quantum communication complexity. We develop several other Fourier based lower bound methods, notably showing that /spl radic/(s~(f)/log n) n, for the average sensitivity s~(f) of a function f, yields a lower bound on the bounded error quantum communication complexity of f (x/spl and/y/spl oplus/yz), where x is a Boolean word held by Alice and y, z are Boolean words held by Bob. We then prove the first large lower bounds on the bounded error quantum communication complexity of functions, for which a polynomial quantum speedup is possible. For all the functions we investigate, only the previously applied general lower bound method based on discrepancy yields bounds that are O(log n).