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

ABSTRACT

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 &sqrt;(ρ′ − ρ)² ≤ ε, 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 &subse; [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.

REFERENCES

• 1: Ambainis, A., Nayak, A., Ta-Shma, A., and Vazirani, U. 2002. Dense quantum coding and quantum finite automata. J. ACM 49, 4, 496--511.
• 2: Bar-Yehuda, R., Chor, B., Kushilevitz, E., and Orlitsky, A. 1993. Privacy, additional information, and communication. IEEE Trans. Info. Theory 39, 6, 1930--1943.
• 3: Bennett, C., Brassard, G., Crepeau, C., Jozsa, R., Peres, A., and Wootters, W. 1993. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Phys. Rev. Lett. 70, 1895--1899.
• 4: Bhatia, R. 1997. Matrix Analysis. Springer-Verlag, New York. (2000 Reprint).
• 5: Chakrabarti, A., and Regev, O. 2004. An optimal randomised cell probe lower bound for approximate nearest neighbour searching. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 473--482.
• 6: Chakrabarti, A., Shi, Y., Wirth, A., and Yao, A. 2001. Informational complexity and the direct sum problem for simultaneous message complexity. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 270--278.
• 7: Chor, B., Kushilevitz, E., Goldreich, O., and Sudan, M. 1998. Private information retrieval. J. ACM 45, 6, 965--981.
• 8: Cleve, R., van Dam, W., Nielsen, M., and Tapp, A. 1998. Quantum entanglement and the communication complexity of the inner product function. In Proceedings of the 1st NASA International Conference on Quantum Computing and Quantum Communications. Lecture Notes in Computer Science, vol. 1509. Springer-Verlag, Berlin, Germany, 61--74. (Also quant-ph/9708019).
• 9: Cover, T., and Thomas, J. 1991. Elements of Information Theory. Wiley Series in Telecommunications. Wiley, New York.
• 10: Fuchs, C., and Caves, C. 1995. Mathematical techniques for quantum communication theory. Open Syst. Inf. Dynam. 3, 3, 345--356. (Also quant-ph/9604001.)
• 11: Gavinsky, D., Kempe, J., Regev, O., and de Wolf, R. 2006. Bounded-error quantum state identification and exponential separations in communication complexity. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing. ACM, New York, 594--603. (Also quant-ph/0511013.)
• 12: Helstrom, C. 1976. Quantum detection and estimation theory. Math. Sci. Engin. 123.
• 13: Jain, R. 2006. Communication complexity of remote state preparation with entanglement. Quant. Info. Computat. 6, 4--5, 461--464.
• 14: Jain, R. 2008. New binding-concealing trade-offs for quantum string commitment. J. Crypt.
• 15: Jain, R., Klauck, H., and Nayak, A. 2008. Direct product theorems for classical communication complexity via subdistribution bounds. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing. ACM, New York, 599--608.
• 16: Jain, R., Radhakrishnan, J., and Sen, P. 2002. Privacy and interaction in quantum communication complexity and a theorem about relative entropy of quantum states. In Proceedings of the 43th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 429--438.
• 17: Jain, R., Radhakrishnan, J., and Sen, P. 2003. A direct sum theorem in communication complexity via message compression. In Proceedings of the 30th International Conference on Automata, Languages and Programming. 300--315.
• 18: Jain, R., Radhakrishnan, J., and Sen, P. 2005. Prior entanglement, message compression and privacy in quantum communication. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, CA, 285--296.
• 19: Jozsa, R. 1994. Fidelity for mixed quantum states. J. Mod. Optics 41, 12, 2315--2323.
• 20: Klauck, H. 2000. On quantum and probabilistic communication: Las Vegas and one-way protocols. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. ACM, New York, 644--651.
• 21: Klauck, H. 2002. On quantum and approximate privacy. In Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 2285. Springer-Verlag, New York, 335--346. (Also quant-ph/0110038.)
• 22: Klauck, H. 2007. One-way communication complexity and the Neciporuk lower bound on formula size. SIAM J. Comput. 37, 2, 552--583.
• 23: Klauck, H., Nayak, A., Ta-Shma, A., and Zuckerman, D. 2007. Interaction in quantum communication. IEEE Trans. Info. Theory 53, 6, 1970--1982.
• 24: Löwner, K. 1934. Über monotone Matrixfunktionen. Math. Zeits. 38, 177--216.
• 25: Miltersen, P. B., Nisan, N., Safra, S., and Wigderson, A. 1998. On data structures and asymmetric communication complexity. J. Comput. Syst. Sci. 57, 1, 37--49.
• 26: Nayak, A. 1999. Optimal lower bounds for quantum automata and random access codes. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 124--133.
• 27: Nielsen, M., and Chuang, I. 2000. Quantum Computation and Quantum Information. Cambridge University Press.
• 28: Nisan, N., and Wigderson, A. 1993. Rounds in communication complexity revisited. SIAM J. Comput. 22, 211--219.
• 29: Osborne, M., and Rubinstein, A. 1994. A course in game theory. MIT Press, Cambridge, MA.
• 30: Ponzio, S., Radhakrishnan, J., and Venkatesh, S. 2001. The communication complexity of pointer chasing. J. Comput. Syst. Sci. 62, 2, 323--355.
• 31: Renner, R. 2008. Extracting classical randomness in a quantum world. In Proceedings of the IEEE Information Theory Workshop. IEEE Computer Society Press, Los Alamitos, CA, 360--363.
• 32: Schumacher, B. 1995. Quantum coding. Phys. Rev. A 51, 2738--2747.
• 33: Uhlmann, A. 1976. The “transition probability” in the state space of a *-algebra. Rep. Math. Phys. 9, 2, 273--279.
• 34: Yao, A. C.-C. 1993. Quantum circuit complexity. In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 352--361.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Theory

Keywords:
Privacy, quantum communication complexity, quantum information theory