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 $n$ qubits (held by another), up to constant accuracy, must transmit at least $\Omega(2^n)$ bits. This lower bound is optimal and matches the complexity of a simple protocol based on discretisation using an $\epsilon$-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 $\Omega(N)$ classical queries for an input of size $N$. Second, a nonlocal task which can be solved using $n$ Bell pairs, but for which any approximate classical solution must communicate $\Omega(2^n)$ bits.
 S. Aaronson. The learnability of quantum states. Proc. Roy. Soc. Ser. A, 463: 2088, 2007. 10.1098/rspa.2007.0113. quant-ph/0608142.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 E. Galvão 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.
 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.
 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.
 Mika Göös and Thomas Watson. Communication complexity of set-disjointness for all probabilities. Theory of Computing, 12 (9): 1–23, 2016. 10.4086/toc.2016.v012a009.
 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.
 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.
 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.
 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.
 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.
 I. Kremer. Quantum communication. Master's thesis, Hebrew University, 1995.
 S. Laplante, M. Laurière, 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.
 F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland, Amsterdam, 1983.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 J. Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. 10.1017/9781316848142. https://cs.uwaterloo.ca/ watrous/TQI/.
 Vojtěch Havlíček and Jonathan Barrett, "Simple communication complexity separation from quantum state antidistinguishability", Physical Review Research 2 1, 013326 (2020).
 Leonardo Guerini, Marco Túlio Quintino, and Leandro Aolita, "Distributed sampling, quantum communication witnesses, and measurement incompatibility", Physical Review A 100 4, 042308 (2019).
 David Gosset and John Smolin, "A compressed classical description of quantum states", arXiv:1801.05721.
 John-Mark A. Allen, "Reality, Causality, and Quantum Theory", arXiv:1901.01618.
The above citations are from Crossref's cited-by service (last updated successfully 2020-06-01 00:22:12) and SAO/NASA ADS (last updated successfully 2020-06-01 00:22:13). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.