{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T07:28:49Z","timestamp":1771486129900,"version":"3.50.1"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T00:00:00Z","timestamp":1251763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,9]]},"abstract":"<jats:p>We prove the following information-theoretic property about quantum states.<\/jats:p>\n          <jats:p>\n            <jats:italic>Substate theorem:<\/jats:italic>\n            Let \u03c1 and \u03c3 be quantum states in the same Hilbert space with relative entropy\n            <jats:italic>S<\/jats:italic>\n            (\u03c1 \u2016 \u03c3) \u2254 Tr \u03c1 (log \u03c1 - log \u03c3) =\n            <jats:italic>c<\/jats:italic>\n            . Then for all \u03f5 &gt; 0, there is a state \u03c1\u2032 such that the trace distance \u2016\u03c1\u2032 - \u03c1\u2016\n            <jats:sub>tr<\/jats:sub>\n            : Tr \u221a(\u03c1\u2032 - \u03c1)\n            <jats:sup>2<\/jats:sup>\n            \u2264 \u03f5, and \u03c1\u2032\/2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>c<\/jats:italic>\n              \/\u03f5\n              <jats:sup>2<\/jats:sup>\n              )\n            <\/jats:sup>\n            \u2264 \u03c3.\n          <\/jats:p>\n          <jats:p>\n            It states that if the relative entropy of \u03c1 and \u03c3 is small, then there is a state \u03c1\u2032 close to \u03c1, i.e. with small trace distance \u2016\u03c1\u2032 - \u03c1\u2016\n            <jats:sub>tr<\/jats:sub>\n            , that when scaled down by a factor 2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>c<\/jats:italic>\n              )\n            <\/jats:sup>\n            \u2018sits inside\u2019, or becomes a \u2018substate\u2019 of, \u03c3. This result has several applications in quantum communication complexity and cryptography. Using the substate theorem, we derive a privacy trade-off for the\n            <jats:italic>set membership problem<\/jats:italic>\n            in the two-party quantum communication model. Here Alice is given a subset\n            <jats:italic>A<\/jats:italic>\n            \u2286 [\n            <jats:italic>n<\/jats:italic>\n            ], Bob an input\n            <jats:italic>i<\/jats:italic>\n            \u2208 [\n            <jats:italic>n<\/jats:italic>\n            ], and they need to determine if\n            <jats:italic>i<\/jats:italic>\n            \u2208\n            <jats:italic>A<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            <jats:italic>Privacy trade-off for set membership:<\/jats:italic>\n            In any two-party quantum communication protocol for the set membership problem, if Bob reveals only\n            <jats:italic>k<\/jats:italic>\n            bits of information about his input, then Alice must reveal at least\n            <jats:italic>n<\/jats:italic>\n            \/2\n            <jats:sup>\n              O(\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            bits of information about her input.\n          <\/jats:p>\n          <jats:p>We also discuss relationships between various information theoretic quantities that arise naturally in the context of the substate theorem.<\/jats:p>","DOI":"10.1145\/1568318.1568323","type":"journal-article","created":{"date-parts":[[2009,9,8]],"date-time":"2009-09-08T12:53:03Z","timestamp":1252414383000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["A property of quantum relative entropy with an application to privacy in quantum communication"],"prefix":"10.1145","volume":"56","author":[{"given":"Rahul","family":"Jain","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaikumar","family":"Radhakrishnan","sequence":"additional","affiliation":[{"name":"Tata Institute of Fundamental Research, Mumbai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pranab","family":"Sen","sequence":"additional","affiliation":[{"name":"Tata Institute of Fundamental Research, Mumbai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,9,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/581771.581773"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.265501"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.70.1895"},{"key":"e_1_2_1_4_1","volume-title":"Matrix Analysis","author":"Bhatia R.","year":"2000","unstructured":"Bhatia , R. 1997. Matrix Analysis . Springer-Verlag , New York . ( 2000 Reprint). Bhatia, R. 1997. Matrix Analysis. Springer-Verlag, New York. (2000 Reprint)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.12"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Chakrabarti A.","unstructured":"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. 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."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293350"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 1st NASA International Conference on Quantum Computing and Quantum Communications. Lecture Notes in Computer Science","volume":"1509","author":"Cleve R.","unstructured":"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). 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)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Cover T. and Thomas J. 1991. Elements of Information Theory. Wiley Series in Telecommunications. Wiley New York.   Cover T. and Thomas J. 1991. Elements of Information Theory. Wiley Series in Telecommunications. Wiley New York.","DOI":"10.1002\/0471200611"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02228997"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132602"},{"key":"e_1_2_1_12_1","unstructured":"Helstrom C. 1976. Quantum detection and estimation theory. Math. Sci. Engin. 123.  Helstrom C. 1976. Quantum detection and estimation theory. Math. Sci. Engin. 123."},{"key":"e_1_2_1_13_1","first-page":"4","article-title":"Communication complexity of remote state preparation with entanglement","volume":"6","author":"Jain R.","year":"2006","unstructured":"Jain , R. 2006 . Communication complexity of remote state preparation with entanglement . Quant. Info. Computat. 6 , 4 -- 5 , 461--464. Jain, R. 2006. Communication complexity of remote state preparation with entanglement. Quant. Info. Computat. 6, 4--5, 461--464.","journal-title":"Quant. Info. Computat."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-008-9025-y"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374462"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 43th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Jain R.","unstructured":"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. 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."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 30th International Conference on Automata, Languages and Programming. 300--315","author":"Jain R.","unstructured":"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 . 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."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2005.24"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/09500349414552171"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335396"},{"key":"e_1_2_1_21_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science","author":"Klauck H.","unstructured":"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.) 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.)"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970140004X"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.896888"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01170633"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1577"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796491"},{"key":"e_1_2_1_27_1","unstructured":"Nielsen M. and Chuang I. 2000. Quantum Computation and Quantum Information. Cambridge University Press.   Nielsen M. and Chuang I. 2000. Quantum Computation and Quantum Information. Cambridge University Press."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222016"},{"key":"e_1_2_1_29_1","unstructured":"Osborne M. and Rubinstein A. 1994. A course in game theory. MIT Press Cambridge MA.  Osborne M. and Rubinstein A. 1994. A course in game theory. MIT Press Cambridge MA."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1731"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITW.2008.4578686"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.51.2738"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0034-4877(76)90060-4"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366852"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1568318.1568323","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1568318.1568323","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:49Z","timestamp":1750253929000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1568318.1568323"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["10.1145\/1568318.1568323"],"URL":"https:\/\/doi.org\/10.1145\/1568318.1568323","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9]]},"assertion":[{"value":"2007-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-09-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}