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/0608156 · Physical Review A

Communication complexity protocols for qutrits

Boaz Tamir

Published Mar 28, 2007• 3 citations
arXivHTMLPDF

Abstract

Consider a function where its entries are distributed among many parties. Suppose each party is allowed to send only a limited amount of information to a referee. The referee can use a classical protocol to compute the value of the global function. Is there a quantum protocol improving the results of all classical protocols? In a recent work Brukner et al. showed the deep connection between such problems and the theory of Bell inequalities. Here we generalize the theory to trits. There, the best classical protocol fails whereas the quantum protocol yields the correct answer.

DOI
10.1103/physreva.75.032344

Related papers

Quantum Communication Complexity Protocol with Two Entangled Qutrits

Časlav Brukner, Marek Żukowski, Anton Zeilinger

We formulate a two-party communication complexity problem and present its quantum solution that exploits the entanglement between two qutrits. We prove that for a broad class of protocols the entangled state can enhance the efficiency of solving the problem in the quantum protocol over any classical one if and only if the state violates Bell's inequality for two qutrits.

arXiv:quant-ph/0205080•Physical Review Letters•Oct 18, 2002•190 citations

Higher-dimensional communication complexity problems: Classical protocols versus quantum ones based on Bell's theorem or prepare-transmit-measure schemes

Armin Tavakoli, Marek Żukowski

Communication complexity problems (CCPs) are tasks in which separated parties attempt to compute a function whose inputs are distributed among the parties. Their communication is limited so that not all inputs can be sent. We show that broad classes of Bell inequalities can be mapped to CCPs and that a quantum violation of a Bell inequality is a necessary and sufficient condition for an enhancement of the related CCP beyond its classical limitation. However, one can implement CCPs by transmitting a quantum system, encoding no more information than is allowed in the CCP, and extracting information by performing measurements. We show that for a large class of Bell inequalities, the improvement of the CCP associated with a quantum violation of a Bell inequality can be no greater than the improvement obtained from quantum prepare-transmit-measure strategies.

arXiv:1611.00977•Physical Review A•Apr 4, 2017•18 citations

Quantum versus Randomized Communication Complexity, with Efficient Players

Uma Girish, Ran Raz, Avishay Tal

We study a new type of separations between quantum and classical communication complexity, separations that are obtained using quantum protocols where all parties are efficient , in the sense that they can be implemented by small quantum circuits, with oracle access to their inputs. Our main result qualitatively matches the strongest known separation between quantum and classical communication complexity Gavinsky (2016) and is obtained using a quantum protocol where all parties are efficient. More precisely, we give an explicit partial Boolean function f over inputs of length N , such that: f can be computed by a simultaneous-message quantum protocol with communication complexity polylog( N ) (where at the beginning of the protocol Alice and Bob also have polylog( N ) entangled EPR pairs). Any classical randomized protocol for f , with any number of rounds, has communication complexity at least \(\tilde{\Omega}\left(N^{1/4}\right)\) . All parties in the quantum protocol of Item (1) (Alice, Bob and the referee) can be implemented by quantum circuits of size polylog( N ) (where Alice and Bob have oracle access to their inputs). Items (1), (2) qualitatively match the strongest known separation between quantum and classical communication complexity, proved by Gavinsky (2016). Item (3) is new. (Our result is incomparable to the one of Gavinsky. While he obtained a quantitatively better lower bound of \(\Omega\left(N^{1/2}\right)\) in the classical case, the referee in his quantum protocol is inefficient). Exponential separations of quantum and classical communication complexity have been studied in numerous previous works, but to the best of our knowledge the efficiency of the parties in the quantum protocol has not been addressed, and in most previous separations the quantum parties seem to be inefficient. The only separations that we know of that have efficient quantum parties are the recent separations that are based on lifting Göös et al. (2017), Chattopadhyay et al. (2019a). However, these separations seem to require quantum protocols with at least two rounds of communication, so they imply a separation of two-way quantum and classical communication complexity, but they do not give the stronger separations of simultaneous-message quantum communication complexity vs. two-way classical communication complexity (or even one-way quantum communication complexity vs. two-way classical communication complexity). Our proof technique is completely new, in the context of communication complexity, and is based on techniques from Raz & Tal (2019). Our function f is based on a lift of the forrelation problem, using xor as a gadget.

arXiv:1911.02218•Computational Complexity•Oct 28, 2022•14 citations

Feasible quantum communication complexity protocol

Ernesto F. Galvão

I show that a simple multiparty communication task can be performed more efficiently with quantum communication than with classical communication, even with low detection efficiency $\ensuremath{\eta}.$ The task is a communication complexity problem in which distant parties need to compute a function of the distributed inputs, while minimizing the amount of communication between them. A realistic quantum optical setup is suggested that can demonstrate a five-party quantum protocol with higher-than-classical performance, provided \ensuremath{\eta}>0.33.

arXiv:quant-ph/0106121•Physical Review A•Dec 13, 2001•34 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

A Quantum Approach For Reducing Communications in Classical Secure Computations with Long Outputs

Jiayu Zhang

How could quantum cryptography help us achieve what are not achievable in classical cryptography? In this work we study the classical cryptographic problem that two parties would like to perform secure computations with long outputs. As a basic primitive and example, we first consider the following problem which we call secure function sampling with long outputs: suppose $f:\{0,1\}^n\rightarrow \{0,1\}^m$ is a public, efficient classical function, where $m$ is big; Alice would like to sample $x$ from its domain and sends $f(x)$ to Bob; what Bob knows should be no more than $f(x)$ even if it behaves maliciously. Classical cryptography, like FHE and succinct arguments [Gen09,Kil92,HW15], allows us to achieve this task within communication complexity $O(n+m)$; could we achieve this task with communication complexity independent of $m$? In this work, we first design a quantum cryptographic protocol that achieves secure function sampling with approximate security, within $O(n)$ communication (omitting the dependency on the security parameter and error tolerance). We also prove the classical impossibility using techniques in [HW15], which means that our protocol indeed achieves a type of quantum advantage. Building on the secure function sampling protocol, we further construct protocols for general secure two-party computations [Yao86,GB01] with approximate security, with communication complexity only depending on the input length and the targeted security. In terms of the assumptions, we construct protocols for these problems assuming only the existence of collapsing hash functions [Unr16]; what's more, we also construct a classical-channel protocol for these problems additionally assuming the existence of noisy trapdoor claw-free functions [BCMVV,BKVV].

arXiv:2310.05213•Oct 8, 2023•0 citations
Consider a function where its entries are distributed among many parties. Suppose each party is allowed to send only a limited amount of information to a referee. The referee can use a classical protocol to compute the value of the global function. Is there a quantum protocol improving the results of all classical protocols? In a recent work Brukner et al. showed the deep connection between such problems and the theory of Bell inequalities. Here we generalize the theory to trits. There, the best classical protocol fails whereas the quantum protocol yields the correct answer.
Communication complexity problems (CCPs) are tasks in which separated parties attempt to compute a function whose inputs are distributed among the parties. Their communication is limited so that not all inputs can be sent. We show that broad classes of Bell inequalities can be mapped to CCPs and that a quantum violation of a Bell inequality is a necessary and sufficient condition for an enhancement of the related CCP beyond its classical limitation. However, one can implement CCPs by transmitting a quantum system, encoding no more information than is allowed in the CCP, and extracting information by performing measurements. We show that for a large class of Bell inequalities, the improvement of the CCP associated with a quantum violation of a Bell inequality can be no greater than the improvement obtained from quantum prepare-transmit-measure strategies.
We study a new type of separations between quantum and classical communication complexity, separations that are obtained using quantum protocols where all parties are efficient , in the sense that they can be implemented by small quantum circuits, with oracle access to their inputs. Our main result qualitatively matches the strongest known separation between quantum and classical communication complexity Gavinsky (2016) and is obtained using a quantum protocol where all parties are efficient. More precisely, we give an explicit partial Boolean function f over inputs of length N , such that: f can be computed by a simultaneous-message quantum protocol with communication complexity polylog( N ) (where at the beginning of the protocol Alice and Bob also have polylog( N ) entangled EPR pairs). Any classical randomized protocol for f , with any number of rounds, has communication complexity at least Ω~(N1/4)\tilde{\Omega}\left(N^{1/4}\right)Ω~(N1/4) . All parties in the quantum protocol of Item (1) (Alice, Bob and the referee) can be implemented by quantum circuits of size polylog( N ) (where Alice and Bob have oracle access to their inputs). Items (1), (2) qualitatively match the strongest known separation between quantum and classical communication complexity, proved by Gavinsky (2016). Item (3) is new. (Our result is incomparable to the one of Gavinsky. While he obtained a quantitatively better lower bound of Ω(N1/2)\Omega\left(N^{1/2}\right)Ω(N1/2) in the classical case, the referee in his quantum protocol is inefficient). Exponential separations of quantum and classical communication complexity have been studied in numerous previous works, but to the best of our knowledge the efficiency of the parties in the quantum protocol has not been addressed, and in most previous separations the quantum parties seem to be inefficient. The only separations that we know of that have efficient quantum parties are the recent separations that are based on lifting Göös et al. (2017), Chattopadhyay et al. (2019a). However, these separations seem to require quantum protocols with at least two rounds of communication, so they imply a separation of two-way quantum and classical communication complexity, but they do not give the stronger separations of simultaneous-message quantum communication complexity vs. two-way classical communication complexity (or even one-way quantum communication complexity vs. two-way classical communication complexity). Our proof technique is completely new, in the context of communication complexity, and is based on techniques from Raz & Tal (2019). Our function f is based on a lift of the forrelation problem, using xor as a gadget.
I show that a simple multiparty communication task can be performed more efficiently with quantum communication than with classical communication, even with low detection efficiency $\ensuremath{\eta}.$ The task is a communication complexity problem in which distant parties need to compute a function of the distributed inputs, while minimizing the amount of communication between them. A realistic quantum optical setup is suggested that can demonstrate a five-party quantum protocol with higher-than-classical performance, provided \ensuremath{\eta}>0.33.
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.
How could quantum cryptography help us achieve what are not achievable in classical cryptography? In this work we study the classical cryptographic problem that two parties would like to perform secure computations with long outputs. As a basic primitive and example, we first consider the following problem which we call secure function sampling with long outputs: suppose f:{0,1}n→{0,1}mf:\{0,1\}^n\rightarrow \{0,1\}^mf:{0,1}n→{0,1}m is a public, efficient classical function, where mmm is big; Alice would like to sample xxx from its domain and sends f(x)f(x)f(x) to Bob; what Bob knows should be no more than f(x)f(x)f(x) even if it behaves maliciously. Classical cryptography, like FHE and succinct arguments [Gen09,Kil92,HW15], allows us to achieve this task within communication complexity O(n+m)O(n+m)O(n+m); could we achieve this task with communication complexity independent of mmm? In this work, we first design a quantum cryptographic protocol that achieves secure function sampling with approximate security, within O(n)O(n)O(n) communication (omitting the dependency on the security parameter and error tolerance). We also prove the classical impossibility using techniques in [HW15], which means that our protocol indeed achieves a type of quantum advantage. Building on the secure function sampling protocol, we further construct protocols for general secure two-party computations [Yao86,GB01] with approximate security, with communication complexity only depending on the input length and the targeted security. In terms of the assumptions, we construct protocols for these problems assuming only the existence of collapsing hash functions [Unr16]; what's more, we also construct a classical-channel protocol for these problems additionally assuming the existence of noisy trapdoor claw-free functions [BCMVV,BKVV].