{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T02:03:51Z","timestamp":1773540231627,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"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":[[2006,1]]},"abstract":"<jats:p>We revisit the problem of conveying classical messages by transmitting quantum states, and derive new, optimal bounds on the number of quantum bits required for this task. Much of the previous work on this problem, and on other communication tasks in the setting of bounded error entanglement-assisted communication, is based on sophisticated information theoretic arguments. Our results are derived from first principles, using a simple linear algebraic technique. A direct consequence is a tight lower bound for the Inner Product function that has found applications to privacy amplification in quantum key distribution protocols.<\/jats:p>","DOI":"10.1145\/1120582.1120587","type":"journal-article","created":{"date-parts":[[2006,5,8]],"date-time":"2006-05-08T16:09:20Z","timestamp":1147104560000},"page":"184-206","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Limits on the ability of quantum states to convey classical messages"],"prefix":"10.1145","volume":"53","author":[{"given":"Ashwin","family":"Nayak","sequence":"first","affiliation":[{"name":"Institute for Quantum Computing, University of Waterloo, and Perimeter Institute for Theoretical Physics, Waterloo, Ont., Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julia","family":"Salzman","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, California"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,1]]},"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.1137\/S009753979935476"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007379"},{"key":"e_1_2_1_4_1","unstructured":"Ben-Or M. 1999. Simple security proof for quantum key distribution. Unpublished. (See talk given during the MSRI special semester on quantum computation in 2002: http:\/\/www.msri.org\/publications\/ln\/msri\/2002\/qip\/ben-or\/1\/index.html.)]]  Ben-Or M. 1999. Simple security proof for quantum key distribution. Unpublished. (See talk given during the MSRI special semester on quantum computation in 2002: http:\/\/www.msri.org\/publications\/ln\/msri\/2002\/qip\/ben-or\/1\/index.html.)]]"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing. IEEE Computer Society","author":"Bennett C. H.","unstructured":"Bennett , C. H. , and Brassard , G . 1984. Quantum cryptography: Public key distribution and coin tossing . In Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing. IEEE Computer Society , Press, Los Alamitos, CA, 175.]] Bennett, C. H., and Brassard, G. 1984. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing. IEEE Computer Society, Press, Los Alamitos, CA, 175.]]"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.70.1895"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.720553"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.69.2881"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300921"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276713"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/872746.873136"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.56.1201"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 1st NASA International Conference. 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 Quantum Computing and Quantum Communications , Proceedings of the 1st NASA International Conference. Lecture Notes in Computer Science , vol. 1509 . Springer-Verlag, Heidelberg, Germany, 61--74.]] Cleve, R., van Dam, W., Nielsen, M., and Tapp, A. 1998. Quantum entanglement and the communication complexity of the inner product function. In Quantum Computing and Quantum Communications, Proceedings of the 1st NASA International Conference. Lecture Notes in Computer Science, vol. 1509. Springer-Verlag, Heidelberg, Germany, 61--74.]]"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Cover T. M. and Thomas J. A. 1991. Elements of Information Theory. Wiley Series in Telecommunications. Wiley New York.]]   Cover T. M. and Thomas J. A. 1991. Elements of Information Theory. Wiley Series in Telecommunications. Wiley New York.]]","DOI":"10.1002\/0471200611"},{"key":"e_1_2_1_15_1","unstructured":"de Wolf R. 2005. Lower bounds on matrix rigidity via a quantum argument. Tech. rep. Arxiv.org Preprint Archive. (Available at http:\/\/www.arxiv.org\/abs\/quant-ph\/0505188.)]]  de Wolf R. 2005. Lower bounds on matrix rigidity via a quantum argument. Tech. rep. Arxiv.org Preprint Archive. (Available at http:\/\/www.arxiv.org\/abs\/quant-ph\/0505188.)]]"},{"key":"e_1_2_1_17_1","first-page":"177","article-title":"Some estimates of the information transmitted by quantum communication channels","volume":"9","author":"Holevo A.","year":"1973","unstructured":"Holevo , A. 1973 . Some estimates of the information transmitted by quantum communication channels . Prob. Inf. Trans. 9 , 3, 177 -- 183 . (Russian version in Problemy Peredachi Informatsii 9 (1973), 3--11.)]] Holevo, A. 1973. Some estimates of the information transmitted by quantum communication channels. Prob. Inf. Trans. 9, 3, 177--183. (Russian version in Problemy Peredachi Informatsii 9 (1973), 3--11.)]]","journal-title":"Prob. Inf. Trans."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.007"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335396"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875559"},{"key":"e_1_2_1_21_1","unstructured":"Klauck H. 2001b. One-way communication complexity and the Neciporuk lower bound on formula size. Tech. rep. Arxiv.org Preprint Archive. (Available at http:\/\/www.arxiv.org\/abs\/cs.CC\/0111062.)]]  Klauck H. 2001b. One-way communication complexity and the Neciporuk lower bound on formula size. Tech. rep. Arxiv.org Preprint Archive. (Available at http:\/\/www.arxiv.org\/abs\/cs.CC\/0111062.)]]"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380786"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Kushilevitz E. and Nisan N. 1997. Communication Complexity. Cambridge University Press Cambridge UK.]]   Kushilevitz E. and Nisan N. 1997. Communication Complexity. Cambridge University Press Cambridge UK.]]","DOI":"10.1017\/CBO9780511574948"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.78.3410"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.78.3414"},{"key":"e_1_2_1_28_1","unstructured":"Nielsen M. A. and Chuang I. L. 2000. Quantum Computation and Quantum Information. Cambridge University Press Cambridge UK.]]   Nielsen M. A. and Chuang I. L. 2000. Quantum Computation and Quantum Information. Cambridge University Press Cambridge UK.]]"},{"key":"e_1_2_1_29_1","volume-title":"Quantum computation. Lecture Notes,","author":"Preskill J.","unstructured":"Preskill , J. 1998. Quantum computation. Lecture Notes, available at http:\/\/www.theory.caltech.edu\/people\/preskill\/ph229\/, California Institute of Technology , Pasadena, CA .]] Preskill, J. 1998. Quantum computation. Lecture Notes, available at http:\/\/www.theory.caltech.edu\/people\/preskill\/ph229\/, California Institute of Technology, Pasadena, CA.]]"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301343"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.62"},{"key":"e_1_2_1_32_1","first-page":"145","article-title":"Quantum communication complexity of symmetric predicates. Izvestiya","volume":"67","author":"Razborov A.","year":"2003","unstructured":"Razborov , A. 2003 . Quantum communication complexity of symmetric predicates. Izvestiya : Mathematics 67 , 1, 145 -- 159 . (Russian version in Izvestiya Rossiiskoi Academii Nauk (seriya matematicheskaya) 67 (2003), 1, 159--176.)]] Razborov, A. 2003. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics 67, 1, 145--159. (Russian version in Izvestiya Rossiiskoi Academii Nauk (seriya matematicheskaya) 67 (2003), 1, 159--176.)]]","journal-title":"Mathematics"},{"key":"e_1_2_1_33_1","unstructured":"van Dam W. and Hayden P. 2002. Renyi-entropic bounds on quantum communication. Tech. rep. Arxiv.org Preprint Archive. Available at http:\/\/www.arxiv.org\/abs\/quant-ph\/0204093.]]  van Dam W. and Hayden P. 2002. Renyi-entropic bounds on quantum communication. Tech. rep. Arxiv.org Preprint Archive. Available at http:\/\/www.arxiv.org\/abs\/quant-ph\/0204093.]]"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Yao A. C.-C.","year":"1993","unstructured":"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.]] 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.]]"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1120582.1120587","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1120582.1120587","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:13:56Z","timestamp":1750277636000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1120582.1120587"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1145\/1120582.1120587"],"URL":"https:\/\/doi.org\/10.1145\/1120582.1120587","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]},"assertion":[{"value":"2006-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}