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

A new operational interpretation of relative entropy and trace distance between quantum states

Anurag Anshu, Rahul Jain, Priyanka Mukhopadhyay, Ala Shayeghi, Penghui Yao

Published Apr 4, 2014• 6 citations
OpenAlex

Abstract

In this paper we present a new operational interpretation of relative-entropy between quantum states in the form of the following protocol. P: Alice gets to know the eigen-decomposition of a quantum state $\rho$. Bob gets to know the eigen-decomposition of a quantum state $\sigma$. Both Alice and Bob know $c= S(\rho || \sigma)$, the relative entropy between $\rho$ and $\sigma$ and an error parameter $\epsilon$. Alice and Bob use shared entanglement and after communication of $O((c +1)/\epsilon^4)$ bits from Alice to Bob, Bob ends up with a quantum state $\rho'$ such that $F(\rho, \rho') \geq 1 - \epsilon$, where $F$ represents fidelity. This result can be considered as a non-commutative generalization of a result due to Braverman and Rao [2011] where they considered the special case when $\rho$ and $\sigma$ are classical probability distributions. We use protocol P 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, Radhakrishnan and Sen [2005, 2008]. 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 new operational meaning to trace distance between quantum states in the form of a protocol which can be viewed as a quantum analogue of the classical correlated-sampling protocol, which is widely used, for example by Holenstein [2007] in his proof of a parallel-repetition theorem for two-player one-round games. Recently Dinur, Steurer and Vidick [2013] have shown another version of a quantum correlated sampling protocol different from our protocol, and used it in their proof of a parallel-repetition theorem for two-prover one-round entangled projection games.

Related papers

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

Quantum Information Complexity and Amortized Communication

Dave Touchette

We define a new notion of information cost for quantum protocols, and a corresponding notion of quantum information complexity for bipartite quantum channels, and then investigate the properties of such quantities. These are the fully quantum generalizations of the analogous quantities for bipartite classical functions that have found many applications recently, in particular for proving communication complexity lower bounds. Our definition is strongly tied to the quantum state redistribution task. Previous attempts have been made to define such a quantity for quantum protocols, with particular applications in mind; our notion differs from these in many respects. First, it directly provides a lower bound on the quantum communication cost, independent of the number of rounds of the underlying protocol. Secondly, we provide an operational interpretation for quantum information complexity: we show that it is exactly equal to the amortized quantum communication complexity of a bipartite channel on a given state. This generalizes a result of Braverman and Rao to quantum protocols, and even strengthens the classical result in a bounded round scenario. Also, this provides an analogue of the Schumacher source compression theorem for interactive quantum protocols, and answers a question raised by Braverman. We also discuss some potential applications to quantum communication complexity lower bounds by specializing our definition for classical functions and inputs. Building on work of Jain, Radhakrishnan and Sen, we provide new evidence suggesting that the bounded round quantum communication complexity of the disjointness function is Ω(n/M + M), for M-message protocols. This would match the best known upper bound.

arXiv:1404.3733•Apr 14, 2014•16 citations

A property of quantum relative entropy with an application to privacy in quantum communication

Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen

We prove the following information-theoretic property about quantum states. Substate theorem: Let ρ and σ be quantum states in the same Hilbert space with relative entropy S (ρ ‖ σ) ≔ Tr ρ (log ρ - log σ) = c . Then for all ϵ > 0, there is a state ρ′ such that the trace distance ‖ρ′ - ρ‖ tr : Tr √(ρ′ - ρ) 2 ≤ ϵ, and ρ′/2 O ( c /ϵ 2 ) ≤ σ. It states that if the relative entropy of ρ and σ is small, then there is a state ρ′ close to ρ, i.e. with small trace distance ‖ρ′ - ρ‖ tr , that when scaled down by a factor 2 O ( c ) ‘sits inside’, or becomes a ‘substate’ of, σ. This result has several applications in quantum communication complexity and cryptography. Using the substate theorem, we derive a privacy trade-off for the set membership problem in the two-party quantum communication model. Here Alice is given a subset A ⊆ [ n ], Bob an input i ∈ [ n ], and they need to determine if i ∈ A . Privacy trade-off for set membership: In any two-party quantum communication protocol for the set membership problem, if Bob reveals only k bits of information about his input, then Alice must reveal at least n /2 O( k ) bits of information about her input. We also discuss relationships between various information theoretic quantities that arise naturally in the context of the substate theorem.

Journal of the ACM•Sep 1, 2009•44 citations

Short proofs of the Quantum Substate Theorem

Rahul Jain, Ashwin Nayak

The Quantum Substate Theorem due to Jain, Radhakrishnan, and Sen (2002) gives us a powerful operational interpretation of relative entropy, in fact, of the observational divergence of two quantum states, a quantity that is related to their relative entropy. Informally, the theorem states that if the observational divergence between two quantum states rho, sigma is small, then there is a quantum state rho' close to rho in trace distance, such that rho' when scaled down by a small factor becomes a substate of sigma. We present new proofs of this theorem. The resulting statement is optimal up to a constant factor in its dependence on observational divergence. In addition, the proofs are both conceptually simpler and significantly shorter than the earlier proof.

arXiv:1103.6067•Mar 31, 2011•3 citations

Continuity bounds on the quantum relative entropy — II

Koenraad M. R. Audenaert, Jens Eisert

The quantum relative entropy is frequently used as a distance measure between two quantum states, and inequalities relating it to other distance measures are important mathematical tools in many areas of quantum information theory. We have derived many such inequalities in previous work. The present paper is a follow-up on this, and provides a sharp upper bound on the relative entropy in terms of the trace norm distance and of the smallest eigenvalues of both states concerned. The result obtained here is more general than the corresponding one from our previous work. As a corollary, we obtain a sharp upper bound on the regularised relative entropy introduced by Lendi, Farhadmotamed, and van Wonderen.

arXiv:1105.2656•Journal of Mathematical Physics•Nov 1, 2011•62 citations

A Direct Product Theorem for One-Way Quantum Communication

Rahul Jain, Srijita Kundu

We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation $f\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$. For any $\varepsilon, ζ> 0$ and any $k\geq1$, we show that \[ \mathrm{Q}^1_{1-(1-\varepsilon)^{Ω(ζ^6k/\log|\mathcal{Z}|)}}(f^k) = Ω\left(k\left(ζ^5\cdot\mathrm{Q}^1_{\varepsilon + 12ζ}(f) - \log\log(1/ζ)\right)\right),\] where $\mathrm{Q}^1_{\varepsilon}(f)$ represents the one-way entanglement-assisted quantum communication complexity of $f$ with worst-case error $\varepsilon$ and $f^k$ denotes $k$ parallel instances of $f$. As far as we are aware, this is the first direct product theorem for quantum communication. Our techniques are inspired by the parallel repetition theorems for the entangled value of two-player non-local games, under product distributions due to Jain, Pereszlényi and Yao, and under anchored distributions due to Bavarian, Vidick and Yuen, as well as message-compression for quantum protocols due to Jain, Radhakrishnan and Sen. Our techniques also work for entangled non-local games which have input distributions anchored on any one side. In particular, we show that for any game $G = (q, \mathcal{X}\times\mathcal{Y}, \mathcal{A}\times\mathcal{B}, \mathsf{V})$ where $q$ is a distribution on $\mathcal{X}\times\mathcal{Y}$ anchored on any one side with anchoring probability $ζ$, then \[ ω^*(G^k) = \left(1 - (1-ω^*(G))^5\right)^{Ω\left(\frac{ζ^2 k}{\log(|\mathcal{A}|\cdot|\mathcal{B}|)}\right)}\] where $ω^*(G)$ represents the entangled value of the game $G$. This is a generalization of the result of Bavarian, Vidick and Yuen, who proved a parallel repetition theorem for games anchored on both sides, and potentially a simplification of their proof.

arXiv:2008.08963•Leibniz international proceedings in informatics•Aug 20, 2020•1 citation
In this paper we present a new operational interpretation of relative-entropy between quantum states in the form of the following protocol.
P: Alice gets to know the eigen-decomposition of a quantum state ρ\rhoρ. Bob gets to know the eigen-decomposition of a quantum state σ\sigmaσ. Both Alice and Bob know c=S(ρ∣∣σ)c= S(\rho || \sigma)c=S(ρ∣∣σ), the relative entropy between ρ\rhoρ and σ\sigmaσ and an error parameter ϵ\epsilonϵ. Alice and Bob use shared entanglement and after communication of O((c+1)/ϵ4)O((c +1)/\epsilon^4)O((c+1)/ϵ4) bits from Alice to Bob, Bob ends up with a quantum state ρ′\rho'ρ′ such that F(ρ,ρ′)≥1−ϵF(\rho, \rho') \geq 1 - \epsilonF(ρ,ρ′)≥1−ϵ, where FFF represents fidelity. This result can be considered as a non-commutative generalization of a result due to Braverman and Rao [2011] where they considered the special case when ρ\rhoρ and σ\sigmaσ are classical probability distributions. We use protocol P 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, Radhakrishnan and Sen [2005, 2008]. 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 new operational meaning to trace distance between quantum states in the form of a protocol which can be viewed as a quantum analogue of the classical correlated-sampling protocol, which is widely used, for example by Holenstein [2007] in his proof of a parallel-repetition theorem for two-player one-round games. Recently Dinur, Steurer and Vidick [2013] have shown another version of a quantum correlated sampling protocol different from our protocol, and used it in their proof of a parallel-repetition theorem for two-prover one-round entangled projection games.
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 define a new notion of information cost for quantum protocols, and a corresponding notion of quantum information complexity for bipartite quantum channels, and then investigate the properties of such quantities. These are the fully quantum generalizations of the analogous quantities for bipartite classical functions that have found many applications recently, in particular for proving communication complexity lower bounds. Our definition is strongly tied to the quantum state redistribution task. Previous attempts have been made to define such a quantity for quantum protocols, with particular applications in mind; our notion differs from these in many respects. First, it directly provides a lower bound on the quantum communication cost, independent of the number of rounds of the underlying protocol. Secondly, we provide an operational interpretation for quantum information complexity: we show that it is exactly equal to the amortized quantum communication complexity of a bipartite channel on a given state. This generalizes a result of Braverman and Rao to quantum protocols, and even strengthens the classical result in a bounded round scenario. Also, this provides an analogue of the Schumacher source compression theorem for interactive quantum protocols, and answers a question raised by Braverman. We also discuss some potential applications to quantum communication complexity lower bounds by specializing our definition for classical functions and inputs. Building on work of Jain, Radhakrishnan and Sen, we provide new evidence suggesting that the bounded round quantum communication complexity of the disjointness function is Ω(n/M + M), for M-message protocols. This would match the best known upper bound.
We prove the following information-theoretic property about quantum states. Substate theorem: Let ρ and σ be quantum states in the same Hilbert space with relative entropy S (ρ ‖ σ) ≔ Tr ρ (log ρ - log σ) = c . Then for all ϵ > 0, there is a state ρ′ such that the trace distance ‖ρ′ - ρ‖ tr : Tr √(ρ′ - ρ) 2 ≤ ϵ, and ρ′/2 O ( c /ϵ 2 ) ≤ σ. It states that if the relative entropy of ρ and σ is small, then there is a state ρ′ close to ρ, i.e. with small trace distance ‖ρ′ - ρ‖ tr , that when scaled down by a factor 2 O ( c ) ‘sits inside’, or becomes a ‘substate’ of, σ. This result has several applications in quantum communication complexity and cryptography. Using the substate theorem, we derive a privacy trade-off for the set membership problem in the two-party quantum communication model. Here Alice is given a subset A ⊆ [ n ], Bob an input i ∈ [ n ], and they need to determine if i ∈ A . Privacy trade-off for set membership: In any two-party quantum communication protocol for the set membership problem, if Bob reveals only k bits of information about his input, then Alice must reveal at least n /2 O( k ) bits of information about her input. We also discuss relationships between various information theoretic quantities that arise naturally in the context of the substate theorem.
The Quantum Substate Theorem due to Jain, Radhakrishnan, and Sen (2002) gives us a powerful operational interpretation of relative entropy, in fact, of the observational divergence of two quantum states, a quantity that is related to their relative entropy. Informally, the theorem states that if the observational divergence between two quantum states rho, sigma is small, then there is a quantum state rho' close to rho in trace distance, such that rho' when scaled down by a small factor becomes a substate of sigma. We present new proofs of this theorem. The resulting statement is optimal up to a constant factor in its dependence on observational divergence. In addition, the proofs are both conceptually simpler and significantly shorter than the earlier proof.
The quantum relative entropy is frequently used as a distance measure between two quantum states, and inequalities relating it to other distance measures are important mathematical tools in many areas of quantum information theory. We have derived many such inequalities in previous work. The present paper is a follow-up on this, and provides a sharp upper bound on the relative entropy in terms of the trace norm distance and of the smallest eigenvalues of both states concerned. The result obtained here is more general than the corresponding one from our previous work. As a corollary, we obtain a sharp upper bound on the regularised relative entropy introduced by Lendi, Farhadmotamed, and van Wonderen.
We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation f⊆X×Y×Zf\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}f⊆X×Y×Z. For any ε,ζ>0\varepsilon, ζ> 0ε,ζ>0 and any k≥1k\geq1k≥1, we show that Q1−(1−ε)Ω(ζ6k/log⁡∣Z∣)1(fk)=Ω(k(ζ5⋅Qε+12ζ1(f)−log⁡log⁡(1/ζ))), \mathrm{Q}^1_{1-(1-\varepsilon)^{Ω(ζ^6k/\log|\mathcal{Z}|)}}(f^k) = Ω\left(k\left(ζ^5\cdot\mathrm{Q}^1_{\varepsilon + 12ζ}(f) - \log\log(1/ζ)\right)\right),Q1−(1−ε)Ω(ζ6k/log∣Z∣)1​(fk)=Ω(k(ζ5⋅Qε+12ζ1​(f)−loglog(1/ζ))), where Qε1(f)\mathrm{Q}^1_{\varepsilon}(f)Qε1​(f) represents the one-way entanglement-assisted quantum communication complexity of fff with worst-case error ε\varepsilonε and fkf^kfk denotes kkk parallel instances of fff. As far as we are aware, this is the first direct product theorem for quantum communication. Our techniques are inspired by the parallel repetition theorems for the entangled value of two-player non-local games, under product distributions due to Jain, Pereszlényi and Yao, and under anchored distributions due to Bavarian, Vidick and Yuen, as well as message-compression for quantum protocols due to Jain, Radhakrishnan and Sen. Our techniques also work for entangled non-local games which have input distributions anchored on any one side. In particular, we show that for any game G=(q,X×Y,A×B,V)G = (q, \mathcal{X}\times\mathcal{Y}, \mathcal{A}\times\mathcal{B}, \mathsf{V})G=(q,X×Y,A×B,V) where qqq is a distribution on X×Y\mathcal{X}\times\mathcal{Y}X×Y anchored on any one side with anchoring probability ζζζ, then ω∗(Gk)=(1−(1−ω∗(G))5)Ω(ζ2klog⁡(∣A∣⋅∣B∣)) ω^*(G^k) = \left(1 - (1-ω^*(G))^5\right)^{Ω\left(\frac{ζ^2 k}{\log(|\mathcal{A}|\cdot|\mathcal{B}|)}\right)}ω∗(Gk)=(1−(1−ω∗(G))5)Ω(log(∣A∣⋅∣B∣)ζ2k​) where ω∗(G)ω^*(G)ω∗(G) represents the entangled value of the game GGG. This is a generalization of the result of Bavarian, Vidick and Yuen, who proved a parallel repetition theorem for games anchored on both sides, and potentially a simplification of their proof.