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/0205080 · Physical Review Letters

Quantum Communication Complexity Protocol with Two Entangled Qutrits

Časlav Brukner, Marek Żukowski, Anton Zeilinger

Published Oct 18, 2002• 190 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevlett.89.197901

Related papers

QUANTUM COMMUNICATION COMPLEXITY PROTOCOLS BASED ON HIGHER-DIMENSIONAL ENTANGLED SYSTEMS

Časlav Brukner, Tomasz Paterek, Marek Żukowski

We introduce new communication complexity problems whose quantum solution exploits entanglement between higher-dimensional systems. We show that the quantum solution is more efficient than the broad class of classical ones. The difference between the efficiencies for the quantum and classical protocols grows with the dimensionality of the entangled systems.

International Journal of Quantum Information•Dec 1, 2003•14 citations

Bell’s Inequalities and Quantum Communication Complexity

Časlav Brukner, Marek Żukowski, Jian-Wei Pan +1 more

We prove that for every Bell's inequality, including those which are not yet known, there always exists a communication complexity problem, for which a protocol assisted by states which violate the inequality is more efficient than any classical protocol. Violation of Bell's inequalities is the necessary and sufficient condition for quantum protocol to beat the classical ones.

arXiv:quant-ph/0210114•Physical Review Letters•Mar 22, 2004•274 citations

Communication complexity protocols for qutrits

Boaz Tamir

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.

arXiv:quant-ph/0608156•Physical Review A•Mar 28, 2007•3 citations

Preparation of engineered multidimensional entangled states for optimal quantum information

Juan P. Torres, Yana Deyanova, Lluís Torner +1 more

Generation of maximally entangled states with different phase distributions and quantum states that can violate Bell's inequality stronger than a maximally entangled state are reported. The scheme can be used to enhance the efficiency of the quantum solution of a two- party communication complexity problem over any classical protocol by using two qutrit that violates Bell's inequality. Spatial amplitude profile of the pump beam that generates a maximally entangled qu-quart is given.

European Quantum Electronics Conference (EQEC)•Nov 15, 2004•0 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

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
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.
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.
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.