{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T00:04:23Z","timestamp":1783641863496,"version":"3.55.0"},"reference-count":42,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2019,6,28]],"date-time":"2019-06-28T00:00:00Z","timestamp":1561680000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>We show that any classical two-way communication protocol with shared randomness that can approximately simulate the result of applying an arbitrary measurement (held by one party) to a quantum state of <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><\/mml:math> qubits (held by another), up to constant accuracy, must transmit at least <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">\u03a9<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:msup><mml:mn>2<\/mml:mn><mml:mi>n<\/mml:mi><\/mml:msup><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> bits. This lower bound is optimal and matches the complexity of a simple protocol based on discretisation using an <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03f5<\/mml:mi><\/mml:math>-net. The proof is based on a lower bound on the classical communication complexity of a distributed variant of the Fourier sampling problem. We obtain two optimal quantum-classical separations as easy corollaries. First, a sampling problem which can be solved with one quantum query to the input, but which requires <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">\u03a9<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>N<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> classical queries for an input of size <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>N<\/mml:mi><\/mml:math>. Second, a nonlocal task which can be solved using <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><\/mml:math> Bell pairs, but for which any approximate classical solution must communicate <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">\u03a9<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:msup><mml:mn>2<\/mml:mn><mml:mi>n<\/mml:mi><\/mml:msup><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> bits.<\/jats:p>","DOI":"10.22331\/q-2019-06-28-154","type":"journal-article","created":{"date-parts":[[2019,6,28]],"date-time":"2019-06-28T03:51:38Z","timestamp":1561693898000},"page":"154","source":"Crossref","is-referenced-by-count":6,"title":["Quantum states cannot be transmitted efficiently classically"],"prefix":"10.22331","volume":"3","author":[{"given":"Ashley","family":"Montanaro","sequence":"first","affiliation":[{"name":"School of Mathematics, University of Bristol, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2019,6,28]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"S. Aaronson. The learnability of quantum states. Proc. Roy. Soc. Ser. A, 463: 2088, 2007. 10.1098\/rspa.2007.0113. quant-ph\/0608142.","DOI":"10.1098\/rspa.2007.0113"},{"key":"1","doi-asserted-by":"publisher","unstructured":"S. Aaronson and A. Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. In Proc. 47th Annual ACM Symp. Theory of Computing, pages 307-316, 2015. 10.1145\/2746539.2746547. arXiv:1411.5729.","DOI":"10.1145\/2746539.2746547"},{"key":"2","doi-asserted-by":"publisher","unstructured":"S. Aaronson and L. Chen. Complexity-theoretic foundations of quantum supremacy experiments. In Proc. 32nd Annual IEEE Conf. Computational Complexity, 2017. 10.4230\/LIPIcs.CCC.2017.22. arXiv:1612.05903.","DOI":"10.4230\/LIPIcs.CCC.2017.22"},{"key":"3","doi-asserted-by":"publisher","unstructured":"A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani. Dense quantum coding and quantum finite automata. J. ACM, 49 (4): 496-511, 2002. 10.1145\/581771.581773. quant-ph\/9804043.","DOI":"10.1145\/581771.581773"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Z. Bar-Yossef, T. S. Jayram, and I. Kerenidis. Exponential separation of quantum and classical one-way communication complexity. SIAM J. Comput., 38 (1): 366-384, 2008. 10.1137\/060651835.","DOI":"10.1137\/060651835"},{"key":"5","doi-asserted-by":"publisher","unstructured":"P. Beame, T. Pitassi, N. Segerlind, and A. Wigderson. A strong direct product theorem for corruption and the multiparty communication complexity of disjointness. Computational Complexity, 15: 391-432, 2007. 10.1007\/s00037-007-0220-2.","DOI":"10.1007\/s00037-007-0220-2"},{"key":"6","doi-asserted-by":"publisher","unstructured":"C. H. Bennett, P. Hayden, D. Leung, P. Shor, and A. Winter. Remote preparation of quantum states. IEEE Trans. Inform. Theory, 51 (1): 56-74, 2005. 10.1109\/TIT.2004.839476. quant-ph\/0307100.","DOI":"10.1109\/TIT.2004.839476"},{"key":"7","doi-asserted-by":"publisher","unstructured":"E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM J. Comput., 26 (5): 1411-1473, 1997. 10.1137\/S0097539796300921.","DOI":"10.1137\/S0097539796300921"},{"key":"8","doi-asserted-by":"publisher","unstructured":"G. Brassard, R. Cleve, and A. Tapp. Cost of exactly simulating quantum entanglement with classical communication. Phys. Rev. Lett., 83 (9): 1874-1877, 1999. 10.1103\/PhysRevLett.83.1874. quant-ph\/9901035.","DOI":"10.1103\/PhysRevLett.83.1874"},{"key":"9","doi-asserted-by":"publisher","unstructured":"S. Brierley, A. Kosowski, M. Markiewicz, T. Paterek, and A. Przysiezna. Non-classicality of temporal correlations. Phys. Rev. Lett., 115: 120404, 2015. 10.1103\/PhysRevLett.115.120404. arXiv:1501.03505.","DOI":"10.1103\/PhysRevLett.115.120404"},{"key":"10","doi-asserted-by":"publisher","unstructured":"N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner. Bell nonlocality. Rev. Mod. Phys., 86: 419, 2014. 10.1103\/RevModPhys.86.419. arXiv:1303.2849.","DOI":"10.1103\/RevModPhys.86.419"},{"key":"11","doi-asserted-by":"publisher","unstructured":"H. Buhrman, R. Cleve, and A. Wigderson. Quantum vs. classical communication and computation. In Proc. 30th Annual ACM Symp. Theory of Computing. ACM Press, 1998. 10.1145\/276698.276713. quant-ph\/9802040.","DOI":"10.1145\/276698.276713"},{"key":"12","doi-asserted-by":"publisher","unstructured":"H. Buhrman, R. Cleve, S. Massar, and R. de Wolf. Non-locality and communication complexity. Rev. Mod. Phys., 82 (1): 665-698, 2010. 10.1103\/RevModPhys.82.665. arXiv:0907.3584.","DOI":"10.1103\/RevModPhys.82.665"},{"key":"13","doi-asserted-by":"publisher","unstructured":"N. Cerf, N. Gisin, and S. Massar. Classical teleportation of a quantum bit. Phys. Rev. Lett., 84: 2521, 1999. 10.1103\/PhysRevLett.84.2521. quant-ph\/9906105.","DOI":"10.1103\/PhysRevLett.84.2521"},{"key":"14","doi-asserted-by":"publisher","unstructured":"A. Chakrabarti and O. Regev. An optimal lower bound on the communication complexity of Gap-Hamming-Distance. SIAM J. Comput., 41 (5): 1299-1317, 2012. 10.1137\/120861072. arXiv:1009.3460.","DOI":"10.1137\/120861072"},{"key":"15","doi-asserted-by":"publisher","unstructured":"A. Chakrabarti, R. Kondapally, and Z. Wang. Information complexity versus corruption and applications to orthogonality and Gap-Hamming. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2012), pages 483-494, 2012. 10.1007\/978-3-642-32512-0_41. arXiv:1205.0968.","DOI":"10.1007\/978-3-642-32512-0_41"},{"key":"16","doi-asserted-by":"publisher","unstructured":"D. Deutsch and R. Jozsa. Rapid solution of problems by quantum computation. Proc. Roy. Soc. London Ser. A, 439 (1907): 553-558, 1992. 10.1098\/rspa.1992.0167.","DOI":"10.1098\/rspa.1992.0167"},{"key":"17","doi-asserted-by":"publisher","unstructured":"E. Galv\u00e3o and L. Hardy. Substituting a qubit for an arbitrarily large number of classical bits. Phys. Rev. Lett., 90: 087902, 2003. 10.1103\/PhysRevLett.90.087902. quant-ph\/0110166.","DOI":"10.1103\/PhysRevLett.90.087902"},{"key":"18","doi-asserted-by":"publisher","unstructured":"D. Gavinsky. Classical interaction cannot replace a quantum message. In Proc. 40th Annual ACM Symp. Theory of Computing, pages 95-102, 2008. 10.1145\/1374376.1374393. quant-ph\/0703215.","DOI":"10.1145\/1374376.1374393"},{"key":"19","doi-asserted-by":"publisher","unstructured":"D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, and R. de Wolf. Exponential separations for one-way quantum communication complexity, with applications to cryptography. SIAM J. Comput., 38 (5): 1695-1708, 2008. 10.1137\/070706550. quant-ph\/0611209.","DOI":"10.1137\/070706550"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Mika G\u00f6\u00f6s and Thomas Watson. Communication complexity of set-disjointness for all probabilities. Theory of Computing, 12 (9): 1-23, 2016. 10.4086\/toc.2016.v012a009.","DOI":"10.4086\/toc.2016.v012a009"},{"key":"21","doi-asserted-by":"publisher","unstructured":"P. Hayden, D. Leung, P. Shor, and A. Winter. Randomizing quantum states: Constructions and applications. Comm. Math. Phys., 250 (2): 371-391, 2004. 10.1007\/s00220-004-1087-6. quant-ph\/0307104.","DOI":"10.1007\/s00220-004-1087-6"},{"key":"22","unstructured":"A. S. Holevo. Bounds for the quantity of information transmitted by a quantum communication channel. Problemy Peredachi Informatsii, 9 (3): 3-11, 1973. English translation Problems of Information Transmission, vol. 9, pp. 177-183, 1973."},{"key":"23","doi-asserted-by":"publisher","unstructured":"R. Jain and H. Klauck. The partition bound for classical communication complexity and query complexity. In Proc. 25th Annual IEEE Conf. Computational Complexity, pages 247-258, 2010. 10.1109\/CCC.2010.31. arXiv:0910.4266.","DOI":"10.1109\/CCC.2010.31"},{"key":"24","doi-asserted-by":"publisher","unstructured":"B. Klartag and O. Regev. Quantum one-way communication can be exponentially stronger than classical communication. In Proc. 43rd Annual ACM Symp. Theory of Computing, pages 31-40, 2011. 10.1145\/1993636.1993642. arXiv:1009.3640.","DOI":"10.1145\/1993636.1993642"},{"key":"25","doi-asserted-by":"publisher","unstructured":"H. Klauck. Rectangle size bounds and threshold covers in communication complexity. In Proc. 18th Annual IEEE Conf. Computational Complexity, pages 118-134, 2003. 10.1109\/CCC.2003.1214415. cs\/0208006.","DOI":"10.1109\/CCC.2003.1214415"},{"key":"26","unstructured":"I. Kremer. Quantum communication. Master's thesis, Hebrew University, 1995."},{"key":"27","doi-asserted-by":"publisher","unstructured":"I. Kremer, N. Nisan, and D. Ron. On randomized one-round communication complexity. Computational Complexity, 8: 21-49, 1999. 10.1007\/s000370050018.","DOI":"10.1007\/s000370050018"},{"key":"28","doi-asserted-by":"publisher","unstructured":"E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997. 10.1016\/S0065-2458(08)60342-3.","DOI":"10.1016\/S0065-2458(08)60342-3"},{"key":"29","doi-asserted-by":"publisher","unstructured":"S. Laplante, M. Lauri\u00e8re, A. Nolin, J. Roland, and G. Senno. Robust Bell inequalities from communication complexity. Quantum, 2: 72, 2018. 10.22331\/q-2018-06-07-72. arXiv:1606.09514.","DOI":"10.22331\/q-2018-06-07-72"},{"key":"30","unstructured":"F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland, Amsterdam, 1983."},{"key":"31","doi-asserted-by":"publisher","unstructured":"A. Montina. Exponential communication gap between weak and strong classical simulations of quantum communication. Phys. Rev. A, 87: 042331, 2013. 10.1103\/PhysRevA.87.042331. arXiv:1301.3452.","DOI":"10.1103\/PhysRevA.87.042331"},{"key":"32","doi-asserted-by":"publisher","unstructured":"A. Montina and S. Wolf. Lower bounds on the communication complexity of two-party (quantum) processes. In Proc. 2014 IEEE International Symp. on Information Theory, pages 1484-1488, 2014. 10.1109\/ISIT.2014.6875080. arXiv:1401.4126.","DOI":"10.1109\/ISIT.2014.6875080"},{"key":"33","doi-asserted-by":"publisher","unstructured":"A. Montina, M. Pfaffhauser, and S. Wolf. Communication complexity of channels in general probabilistic theories. Phys. Rev. Lett., 111: 160502, 2013. 10.1103\/PhysRevLett.111.160502. arXiv:1301.4441.","DOI":"10.1103\/PhysRevLett.111.160502"},{"key":"34","doi-asserted-by":"publisher","unstructured":"A. Nayak. Optimal lower bounds for quantum automata and random access codes. In Proc. 40th Annual Symp. Foundations of Computer Science, pages 369-376, 1999. 10.1109\/SFFCS.1999.814608.","DOI":"10.1109\/SFFCS.1999.814608"},{"key":"35","doi-asserted-by":"publisher","unstructured":"R. Raz. Exponential separation of quantum and classical communication complexity. In Proc. 31st Annual ACM Symp. Theory of Computing, pages 358-367, 1999. 10.1145\/301250.301343.","DOI":"10.1145\/301250.301343"},{"key":"36","doi-asserted-by":"publisher","unstructured":"A. Sherstov. The communication complexity of gap Hamming distance. Theory of Computing, 8: 197-208, 2012. 10.4086\/toc.2012.v008a008.","DOI":"10.4086\/toc.2012.v008a008"},{"key":"37","doi-asserted-by":"publisher","unstructured":"S. S\u00fdkora. Quantum theory and the Bayesian inference problems. J. Stat. Phys., 11 (1): 17-27, 1974. 10.1007\/BF01019475.","DOI":"10.1007\/BF01019475"},{"key":"38","doi-asserted-by":"publisher","unstructured":"B. Toner and D. Bacon. Communication cost of simulating Bell correlations. Phys. Rev. Lett., 91: 187904, 2003. 10.1103\/PhysRevLett.91.187904. quant-ph\/0304076.","DOI":"10.1103\/PhysRevLett.91.187904"},{"key":"39","doi-asserted-by":"publisher","unstructured":"T. Vidick. A concentration inequality for the overlap of a vector on a large set, with application to the communication complexity of the gap-Hamming-distance problem. Chicago J. Theoret. Comput. Sci., 2012 (1): 1-12, 2012. 10.4086\/cjtcs.2012.001.","DOI":"10.4086\/cjtcs.2012.001"},{"key":"40","doi-asserted-by":"publisher","unstructured":"J. Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. 10.1017\/9781316848142. https:\/\/cs.uwaterloo.ca\/ watrous\/TQI\/.","DOI":"10.1017\/9781316848142"},{"key":"41","doi-asserted-by":"publisher","unstructured":"A. Yao. Lower bounds by probabilistic arguments. In Proc. 24th Annual Symp. Foundations of Computer Science, pages 420-428, 1983. 10.1109\/SFCS.1983.30.","DOI":"10.1109\/SFCS.1983.30"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2019-06-28-154\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,6,28]],"date-time":"2019-06-28T03:51:44Z","timestamp":1561693904000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2019-06-28-154\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,28]]},"references-count":42,"URL":"https:\/\/doi.org\/10.22331\/q-2019-06-28-154","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,28]]},"article-number":"154"}}