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 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 prove the following theorem about relative entropy of quantum states. "Substate theorem: Let rho and sigma be quantum states in the same Hilbert space with relative entropy S(rho|sigma) = Tr rho (log rho - log sigma) = c. Then for all epsilon > 0, there is a state rho' such that the trace distance ||rho' - rho||_t = Tr sqrt{(rho' - rho)^2} <= epsilon, and rho'/2^{O(c/epsilon^2)} <= sigma." It states that if the relative entropy of rho and sigma is small, then there is a state rho' close to rho, i.e. with small trace distance ||rho' - rho||_t, that when scaled down by a factor 2^{O(c)} `sits inside', or becomes a `substate' of, sigma. 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 of [n], Bob an input i in [n], and they need to determine if i in 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.
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.
We prove a direct sum theorem for bounded round entanglement-assisted quantum communication complexity. To do so, we use the fully quantum definition for information cost and complexity that we recently introduced, and use both the fact that information is a lower bound on the communication, and the fact that a direct sum property holds for quantum information complexity. We then give a protocol for compressing a single copy of a protocol down to its quantum information cost, up to terms depending on the number of rounds and the allowed increase in error. Two important tools to derive this protocol are a smooth conditional min-entropy bound for a one-shot quantum state redistribution protocol, and the quantum substate theorem of Jain, Radhakrishnan and Sen (FOCS'02) to transform this bound into a von Neumann conditional entropy bound. This result further establishes the newly introduced notions of quantum information cost and complexity as the correct quantum generalisations of the classical ones in the standard communication complexity setting. Finding such a quantum generalization of information complexity was one of the open problem recently raised by Braverman (STOC'12).
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 Substate Theorem due to Jain (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 ρ, σ is small, then there is a quantum state ρ'close to ρ in trace distance, such that ρ'when scaled down by a small factor becomes a substate of σ. 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.
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 fk. We show that fk 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(klogn) 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⋅(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 k round quantum protocol for the disjointness problem needs communication Ω(n1/k) for k=O(1).