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/0004100

On rounds in quantum communication

Hartmut Klauck

Published Apr 26, 2000• 4 citations
arXivHTMLPDF

Abstract

We investigate the power of interaction in two player quantum communication protocols. Our main result is a rounds-communication hierarchy for the pointer jumping function $f_k$. We show that $f_k$ needs quantum communication $Ω(n)$ if Bob starts the communication and the number of rounds is limited to $k$ (for any constant $k$). Trivially, if Alice starts, $O(k\log n)$ communication in $k$ rounds suffices. The lower bound employs a result relating the relative von Neumann entropy between density matrices to their trace distance and uses a new measure of information. We also describe a classical probabilistic $k$ round protocol with communication $O(n/k\cdot(\log^{(k/2)}n+\log k)+k\log n)$ in which Bob starts the communication. Furthermore as a consequence of the lower bound for pointer jumping we show that any $k$ round quantum protocol for the disjointness problem needs communication $Ω(n^{1/k})$ for $k=O(1)$.

DOI
10.48550/arxiv.quant-ph/0004100

Related papers

Interaction in Quantum Communication

Hartmut Klauck, Ashwin Nayak, Amnon Ta‐Shma +1 more

In some scenarios there are ways of conveying information with many fewer, even exponentially fewer, qubits than possible classically. Moreover, some of these methods have a very simple structure-they involve only few message exchanges between the communicating parties. It is therefore natural to ask whether every classical protocol may be transformed to a "simpler" quantum protocol-one that has similar efficiency, but uses fewer message exchanges. We show that for any constant k, there is a problem such that its k+1 message classical communication complexity is exponentially smaller than its k message quantum communication complexity. This, in particular, proves a round hierarchy theorem for quantum communication complexity, and implies, via a simple reduction, an Omega(N1k/) lower bound for k message quantum protocols for Set Disjointness for constant k. Enroute, we prove information-theoretic lemmas, and define a related measure of correlation, the informational distance, that we believe may be of significance in other contexts as well

arXiv:quant-ph/0603135•IEEE Transactions on Information Theory•Jun 1, 2007•43 citations

Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states

Rahul Jain, Jaikumar Radhakrishnan, P. Sen

We prove a fundamental theorem about the relative entropy of quantum states, which roughly states that if the relative entropy, S(/spl rho//spl par//spl sigma/)/spl Delta/=Tr /spl rho/(log /spl rho/-log /spl sigma/), of two quantum states /spl rho/ and /spl sigma/ is at most c, then /spl rho//2/sup O(c)/ 'sits inside' /spl sigma/. Using this 'substate' theorem, we give tight lower bounds for the privacy loss of bounded error quantum communication protocols for the index function problem. We also use the 'substate' theorem to give tight lower bounds for the k-round bounded error quantum communication complexity of the pointer chasing problem, when the wrong player starts, and all the log n bits of the kth pointer are desired.

Annual Symposium on Foundations of Computer Science•Jun 26, 2003•72 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•8 citations

New One Shot Quantum Protocols With Application to Communication Complexity

Anurag Anshu, Rahul Jain, Priyanka Mukhopadhyay +2 more

In this paper, we present the following quantum compression protocol `P': Let ρ,σ be quantum states, such that S (ρ∥σ)def= Tr(ρ log ρ - ρ log σ), the relative entropy between ρ and σ, is finite. Alice gets to know the eigendecomposition of ρ. Bob gets to know the eigendecomposition of σ. Both Alice and Bob know S(ρ∥σ) and an error parameter ε. Alice and Bob use shared entanglement and after communication of O((S(ρ∥σ) + 1)/ε4) bits from Alice to Bob, Bob ends up with a quantum state ̃ρ̃, such that F(ρ, ρ̃) ≥ 1-5ε, where F(·) represents fidelity. This result can be considered as a non-commutative generalization of a result due to Braverman and Rao where they considered the special case when ρ and σ are classical probability distributions (or commute with each other) and use shared randomness instead of shared entanglement. We use? to obtain an alternate proof of a direct-sum result for entanglement assisted quantum one-way communication complexity for all relations, which was first shown by Jain et al.. We also present a variant of protocol? in which Bob has some side information about the state with Alice. We show that in such a case, the amount of communication can be further reduced, based on the side information that Bob has. Our second result provides a quantum analog of the widely used classical correlated-sampling protocol. For example, Holenstein used the classical correlated-sampling protocol in his proof of a parallel-repetition theorem for two-player one-round games.

arXiv:1404.1366•IEEE Transactions on Information Theory•Oct 10, 2016•13 citations

A lower bound for bounded round quantum communication complexity of set disjointness

Rahul Jain, Jaikumar Radhakrishnan, Sen, Pranab

We consider the class of functions whose value depends only on the intersection of the input X_1,X_2, ..., X_t; that is, for each F in this class there is an f_F: 2^{[n]} \to {0,1}, such that F(X_1,X_2, ..., X_t) = f_F(X_1 \cap X_2 \cap ... \cap X_t). We show that the t-party k-round communication complexity of F is Omega(s_m(f_F)/(k^2)), where s_m(f_F) stands for the `monotone sensitivity of f_F' and is defined by s_m(f_F) \defeq max_{S\subseteq [n]} |{i: f_F(S \cup {i}) \neq f_F(S)|. For two-party quantum communication protocols for the set disjointness problem, this implies that the two parties must exchange Omega(n/k^2) qubits. For k=1, our lower bound matches the Omega(n) lower bound observed by Buhrman and de Wolf (based on a result of Nayak, and for 2 <= k <= n^{1/4}, improves the lower bound of Omega(sqrt{n}) shown by Razborov. (For protocols with no restrictions on the number of rounds, we can conclude that the two parties must exchange Omega(n^{1/3}) qubits. This, however, falls short of the optimal Omega(sqrt{n}) lower bound shown by Razborov.)

arXiv:quant-ph/0303138•Mar 22, 2003•9 citations

The information cost of quantum memoryless protocols

André Chailloux, Iordanis Kerenidis, Mathieu Laurière

We consider memoryless quantum communication protocols, where the two parties do not possess any memory besides their classical input and they take turns performing unitary operations on a pure quantum state that they exchange between them. Most known quantum protocols are of this type and recently a deep connection between memoryless protocols and Bell inequality violations has been explored recently by Buhrman et al. We study the information cost of memoryless quantum protocols by looking at a canonical problem: bounded-round quantum communication protocols for the one-bit AND function. We prove directly a tight lower bound of $Θ(\log(k) / k)$ for the information cost of AND for $k$-round memoryless quantum protocols and for the input distribution needed for the Disjointness function. It is not clear if memoryless protocols allow for a reduction between AND and Disjointness, due to the absence of private workspaces. We enhance the model by allowing the players to keep in their private classical workspace apart from their input also some classical private coins. Surprisingly, we show that every quantum protocol can be transformed into an equivalent quantum protocol with private coins that is perfectly private, i.e. the players only learn the value of the function and nothing more. Last, we consider the model where the players are allowed to use one-shot coins, i.e. private coins that can be used only once during the protocol. While in the classical case, private coins and one-shot coins are equivalent, in the quantum case, we prove that they are not. More precisely, we show that every quantum memoryless protocol with one-bit inputs that uses one-shot coins can be transformed into a memoryless quantum protocol without private coins and without increasing too much its information cost. Hence, while private coins always allow for private quantum protocols, one-shot coins do not.

arXiv:1703.01061•Mar 3, 2017•4 citations
We investigate the power of interaction in two player quantum communication protocols. Our main result is a rounds-communication hierarchy for the pointer jumping function fkf_kfk​. We show that fkf_kfk​ needs quantum communication Ω(n)Ω(n)Ω(n) if Bob starts the communication and the number of rounds is limited to kkk (for any constant kkk). Trivially, if Alice starts, O(klog⁡n)O(k\log n)O(klogn) communication in kkk rounds suffices. The lower bound employs a result relating the relative von Neumann entropy between density matrices to their trace distance and uses a new measure of information. We also describe a classical probabilistic kkk round protocol with communication O(n/k⋅(log⁡(k/2)n+log⁡k)+klog⁡n)O(n/k\cdot(\log^{(k/2)}n+\log k)+k\log n)O(n/k⋅(log(k/2)n+logk)+klogn) in which Bob starts the communication. Furthermore as a consequence of the lower bound for pointer jumping we show that any kkk round quantum protocol for the disjointness problem needs communication Ω(n1/k)Ω(n^{1/k})Ω(n1/k) for k=O(1)k=O(1)k=O(1).
In some scenarios there are ways of conveying information with many fewer, even exponentially fewer, qubits than possible classically. Moreover, some of these methods have a very simple structure-they involve only few message exchanges between the communicating parties. It is therefore natural to ask whether every classical protocol may be transformed to a "simpler" quantum protocol-one that has similar efficiency, but uses fewer message exchanges. We show that for any constant k, there is a problem such that its k+1 message classical communication complexity is exponentially smaller than its k message quantum communication complexity. This, in particular, proves a round hierarchy theorem for quantum communication complexity, and implies, via a simple reduction, an Omega(N1k/) lower bound for k message quantum protocols for Set Disjointness for constant k. Enroute, we prove information-theoretic lemmas, and define a related measure of correlation, the informational distance, that we believe may be of significance in other contexts as well
We prove a fundamental theorem about the relative entropy of quantum states, which roughly states that if the relative entropy, S(/spl rho//spl par//spl sigma/)/spl Delta/=Tr /spl rho/(log /spl rho/-log /spl sigma/), of two quantum states /spl rho/ and /spl sigma/ is at most c, then /spl rho//2/sup O(c)/ 'sits inside' /spl sigma/. Using this 'substate' theorem, we give tight lower bounds for the privacy loss of bounded error quantum communication protocols for the index function problem. We also use the 'substate' theorem to give tight lower bounds for the k-round bounded error quantum communication complexity of the pointer chasing problem, when the wrong player starts, and all the log n bits of the kth pointer are desired.
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.
In this paper, we present the following quantum compression protocol `P': Let ρ,σ be quantum states, such that S (ρ∥σ)def= Tr(ρ log ρ - ρ log σ), the relative entropy between ρ and σ, is finite. Alice gets to know the eigendecomposition of ρ. Bob gets to know the eigendecomposition of σ. Both Alice and Bob know S(ρ∥σ) and an error parameter ε. Alice and Bob use shared entanglement and after communication of O((S(ρ∥σ) + 1)/ε4) bits from Alice to Bob, Bob ends up with a quantum state ̃ρ̃, such that F(ρ, ρ̃) ≥ 1-5ε, where F(·) represents fidelity. This result can be considered as a non-commutative generalization of a result due to Braverman and Rao where they considered the special case when ρ and σ are classical probability distributions (or commute with each other) and use shared randomness instead of shared entanglement. We use? to obtain an alternate proof of a direct-sum result for entanglement assisted quantum one-way communication complexity for all relations, which was first shown by Jain et al.. We also present a variant of protocol? in which Bob has some side information about the state with Alice. We show that in such a case, the amount of communication can be further reduced, based on the side information that Bob has. Our second result provides a quantum analog of the widely used classical correlated-sampling protocol. For example, Holenstein used the classical correlated-sampling protocol in his proof of a parallel-repetition theorem for two-player one-round games.
We consider the class of functions whose value depends only on the intersection of the input X_1,X_2, ..., X_t; that is, for each F in this class there is an f_F: 2^{[n]} \to {0,1}, such that F(X_1,X_2, ..., X_t) = f_F(X_1 \cap X_2 \cap ... \cap X_t). We show that the t-party k-round communication complexity of F is Omega(s_m(f_F)/(k^2)), where s_m(f_F) stands for the `monotone sensitivity of f_F' and is defined by s_m(f_F) \defeq max_{S\subseteq [n]} |{i: f_F(S \cup {i}) \neq f_F(S)|. For two-party quantum communication protocols for the set disjointness problem, this implies that the two parties must exchange Omega(n/k^2) qubits. For k=1, our lower bound matches the Omega(n) lower bound observed by Buhrman and de Wolf (based on a result of Nayak, and for 2 <= k <= n^{1/4}, improves the lower bound of Omega(sqrt{n}) shown by Razborov. (For protocols with no restrictions on the number of rounds, we can conclude that the two parties must exchange Omega(n^{1/3}) qubits. This, however, falls short of the optimal Omega(sqrt{n}) lower bound shown by Razborov.)
We consider memoryless quantum communication protocols, where the two parties do not possess any memory besides their classical input and they take turns performing unitary operations on a pure quantum state that they exchange between them. Most known quantum protocols are of this type and recently a deep connection between memoryless protocols and Bell inequality violations has been explored recently by Buhrman et al. We study the information cost of memoryless quantum protocols by looking at a canonical problem: bounded-round quantum communication protocols for the one-bit AND function. We prove directly a tight lower bound of Θ(log⁡(k)/k)Θ(\log(k) / k)Θ(log(k)/k) for the information cost of AND for kkk-round memoryless quantum protocols and for the input distribution needed for the Disjointness function. It is not clear if memoryless protocols allow for a reduction between AND and Disjointness, due to the absence of private workspaces. We enhance the model by allowing the players to keep in their private classical workspace apart from their input also some classical private coins. Surprisingly, we show that every quantum protocol can be transformed into an equivalent quantum protocol with private coins that is perfectly private, i.e. the players only learn the value of the function and nothing more. Last, we consider the model where the players are allowed to use one-shot coins, i.e. private coins that can be used only once during the protocol. While in the classical case, private coins and one-shot coins are equivalent, in the quantum case, we prove that they are not. More precisely, we show that every quantum memoryless protocol with one-bit inputs that uses one-shot coins can be transformed into a memoryless quantum protocol without private coins and without increasing too much its information cost. Hence, while private coins always allow for private quantum protocols, one-shot coins do not.