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:2305.04435 · Entropy

Communication Complexity of Entanglement-Assisted Multi-Party Computation

Ruoyu Meng, Aditya Ramamoorthy

Published Oct 23, 2024• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.3390/e26110896

Related papers

Two Bit Quantum Protocol for a Three Party Modular Function

Bhagaban Swain, Roy Sudipta

Communicational complexity problem among three parties for the calculation of a three party inner product modular function is discussed, where each party possess some of the function’s input. Classical communicational complexity of this function can be evaluated by three classical bits. In classical theory, the three party modular function can’t be evaluated by two classical bits, but using quantum entanglement in quantum theory two classical bits are sufficient to calculate the three party problem.

International Journal of Computer Applications•Dec 28, 2011•0 citations

Multiparty quantum communication complexity

Harry Buhrman, Wim van Dam, Peter Høyer +1 more

Quantum entanglement cannot be used to achieve direct communication between remote parties, but it can reduce the communication needed for some problems. Let each of $k$ parties hold some partial input data to some fixed $k$-variable function $f.$ The communication complexity of $f$ is the minimum number of classical bits required to be broadcasted for every party to know the value of $f$ on their inputs. We construct a function $G$ such that for the one-round communication model and three parties, $G$ can be computed with $n+1$ bits of communication when the parties share prior entanglement. We then show that without entangled particles, the one-round communication complexity of $G$ is $(3/2)n+1.$ Next we generalize this function to a function $F.$ We show that if the parties share prior quantum entanglement, then the communication complexity of $F$ is exactly $k.$ We also show that, if no entangled particles are provided, then the communication complexity of $F$ is roughly $k{\mathrm{log}}_{2}k.$ These two results prove communication complexity separations better than a constant number of bits.

arXiv:quant-ph/9710054•Physical Review A•Oct 1, 1999•121 citations

On communication over an entanglement-assisted quantum channel

Ashwin Nayak, Julia Salzman

Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding."The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 2002•28 citations

On communication over an entanglement-assisted quantum channel

Ashwin Nayak, Julia Salzman

Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as ``quantum teleportation'' and ``superdense coding.'' The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.

arXiv:quant-ph/0206122•Jun 19, 2002•4 citations

Clean Quantum and Classical Communication Protocols

Harry Buhrman, Matthias Christandl, Christopher Perry +1 more

By how much must the communication complexity of a function increase if we demand that the parties not only correctly compute the function but also return all registers (other than the one containing the answer) to their initial states at the end of the communication protocol? Protocols that achieve this are referred to as clean and the associated cost as the clean communication complexity. Here we present clean protocols for calculating the inner product of two n-bit strings, showing that (in the absence of preshared entanglement) at most n+3 qubits or n+O(sqrt[n]) bits of communication are required. The quantum protocol provides inspiration for obtaining the optimal method to implement distributed cnot gates in parallel while minimizing the amount of quantum communication. For more general functions, we show that nearly all Boolean functions require close to 2n bits of classical communication to compute and close to n qubits if the parties have access to preshared entanglement. Both of these values are maximal for their respective paradigms.

arXiv:1605.07948•Physical Review Letters•Dec 1, 2016•2 citations

A lower bound on entanglement-assisted quantum communication complexity

Ashley Montanaro, Andreas Winter

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.

arXiv:quant-ph/0610085•Oct 11, 2006•1 citation
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.
Communicational complexity problem among three parties for the calculation of a three party inner product modular function is discussed, where each party possess some of the function’s input. Classical communicational complexity of this function can be evaluated by three classical bits. In classical theory, the three party modular function can’t be evaluated by two classical bits, but using quantum entanglement in quantum theory two classical bits are sufficient to calculate the three party problem.
Quantum entanglement cannot be used to achieve direct communication between remote parties, but it can reduce the communication needed for some problems. Let each of kkk parties hold some partial input data to some fixed kkk-variable function f.f.f. The communication complexity of fff is the minimum number of classical bits required to be broadcasted for every party to know the value of fff on their inputs. We construct a function GGG such that for the one-round communication model and three parties, GGG can be computed with n+1n+1n+1 bits of communication when the parties share prior entanglement. We then show that without entangled particles, the one-round communication complexity of GGG is (3/2)n+1.(3/2)n+1.(3/2)n+1. Next we generalize this function to a function F.F.F. We show that if the parties share prior quantum entanglement, then the communication complexity of FFF is exactly k.k.k. We also show that, if no entangled particles are provided, then the communication complexity of FFF is roughly klog2k.k{\mathrm{log}}_{2}k.klog2​k. These two results prove communication complexity separations better than a constant number of bits.
Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding."The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.
Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as ``quantum teleportation'' and ``superdense coding.'' The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.
By how much must the communication complexity of a function increase if we demand that the parties not only correctly compute the function but also return all registers (other than the one containing the answer) to their initial states at the end of the communication protocol? Protocols that achieve this are referred to as clean and the associated cost as the clean communication complexity. Here we present clean protocols for calculating the inner product of two n-bit strings, showing that (in the absence of preshared entanglement) at most n+3 qubits or n+O(sqrt[n]) bits of communication are required. The quantum protocol provides inspiration for obtaining the optimal method to implement distributed cnot gates in parallel while minimizing the amount of quantum communication. For more general functions, we show that nearly all Boolean functions require close to 2n bits of classical communication to compute and close to n qubits if the parties have access to preshared entanglement. Both of these values are maximal for their respective paradigms.
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.