Quantum states cannot be transmitted efficiently classically

Ashley Montanaro

School of Mathematics, University of Bristol, UK

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.

► BibTeX data

► References

[1] S. Aaronson. The learnability of quantum states. Proc. Roy. Soc. Ser. A, 463: 2088, 2007. 10.1098/​rspa.2007.0113. quant-ph/​0608142.
https:/​/​doi.org/​10.1098/​rspa.2007.0113
arXiv:quant-ph/0608142

[2] 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.
https:/​/​doi.org/​10.1145/​2746539.2746547
arXiv:1411.5729

[3] 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.
https:/​/​doi.org/​10.4230/​LIPIcs.CCC.2017.22
arXiv:1612.05903

[4] 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.
https:/​/​doi.org/​10.1145/​581771.581773
arXiv:quant-ph/9804043

[5] 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.
https:/​/​doi.org/​10.1137/​060651835

[6] 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.
https:/​/​doi.org/​10.1007/​s00037-007-0220-2

[7] 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.
https:/​/​doi.org/​10.1109/​TIT.2004.839476
arXiv:quant-ph/0307100

[8] E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM J. Comput., 26 (5): 1411-1473, 1997. 10.1137/​S0097539796300921.
https:/​/​doi.org/​10.1137/​S0097539796300921

[9] 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.
https:/​/​doi.org/​10.1103/​PhysRevLett.83.1874
arXiv:quant-ph/9901035

[10] 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.
https:/​/​doi.org/​10.1103/​PhysRevLett.115.120404
arXiv:1501.03505

[11] 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.
https:/​/​doi.org/​10.1103/​RevModPhys.86.419
arXiv:1303.2849

[12] 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.
https:/​/​doi.org/​10.1145/​276698.276713
arXiv:quant-ph/9802040

[13] 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.
https:/​/​doi.org/​10.1103/​RevModPhys.82.665
arXiv:0907.3584

[14] 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.
https:/​/​doi.org/​10.1103/​PhysRevLett.84.2521
arXiv:quant-ph/9906105

[15] 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.
https:/​/​doi.org/​10.1137/​120861072
arXiv:1009.3460

[16] 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.
https:/​/​doi.org/​10.1007/​978-3-642-32512-0_41
arXiv:1205.0968

[17] 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.
https:/​/​doi.org/​10.1098/​rspa.1992.0167

[18] 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.
https:/​/​doi.org/​10.1103/​PhysRevLett.90.087902
arXiv:quant-ph/0110166

[19] 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.
https:/​/​doi.org/​10.1145/​1374376.1374393
arXiv:quant-ph/0703215

[20] 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.
https:/​/​doi.org/​10.1137/​070706550
arXiv:quant-ph/0611209

[21] 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.
https:/​/​doi.org/​10.4086/​toc.2016.v012a009

[22] 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.
https:/​/​doi.org/​10.1007/​s00220-004-1087-6
arXiv:quant-ph/0307104

[23] 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.

[24] 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.
https:/​/​doi.org/​10.1109/​CCC.2010.31
arXiv:0910.4266

[25] 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.
https:/​/​doi.org/​10.1145/​1993636.1993642
arXiv:1009.3640

[26] 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.
https:/​/​doi.org/​10.1109/​CCC.2003.1214415

[27] I. Kremer. Quantum communication. Master's thesis, Hebrew University, 1995.

[28] I. Kremer, N. Nisan, and D. Ron. On randomized one-round communication complexity. Computational Complexity, 8: 21-49, 1999. 10.1007/​s000370050018.
https:/​/​doi.org/​10.1007/​s000370050018

[29] E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997. 10.1016/​S0065-2458(08)60342-3.
https:/​/​doi.org/​10.1016/​S0065-2458(08)60342-3

[30] 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.
https:/​/​doi.org/​10.22331/​q-2018-06-07-72
arXiv:1606.09514

[31] F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland, Amsterdam, 1983.

[32] 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.
https:/​/​doi.org/​10.1103/​PhysRevA.87.042331
arXiv:1301.3452

[33] 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.
https:/​/​doi.org/​10.1109/​ISIT.2014.6875080
arXiv:1401.4126

[34] 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.
https:/​/​doi.org/​10.1103/​PhysRevLett.111.160502
arXiv:1301.4441

[35] 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.
https:/​/​doi.org/​10.1109/​SFFCS.1999.814608

[36] 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.
https:/​/​doi.org/​10.1145/​301250.301343

[37] A. Sherstov. The communication complexity of gap Hamming distance. Theory of Computing, 8: 197-208, 2012. 10.4086/​toc.2012.v008a008.
https:/​/​doi.org/​10.4086/​toc.2012.v008a008

[38] S. Sýkora. Quantum theory and the Bayesian inference problems. J. Stat. Phys., 11 (1): 17-27, 1974. 10.1007/​BF01019475.
https:/​/​doi.org/​10.1007/​BF01019475

[39] 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.
https:/​/​doi.org/​10.1103/​PhysRevLett.91.187904
arXiv:quant-ph/0304076

[40] 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.
https:/​/​doi.org/​10.4086/​cjtcs.2012.001

[41] J. Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. 10.1017/​9781316848142. https:/​/​cs.uwaterloo.ca/​ watrous/​TQI/​.
https:/​/​doi.org/​10.1017/​9781316848142
https:/​/​cs.uwaterloo.ca/​~watrous/​TQI/​

[42] 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.
https:/​/​doi.org/​10.1109/​SFCS.1983.30

Cited by

[1] John-Mark A. Allen, "Reality, Causality, and Quantum Theory", arXiv:1901.01618.

[2] David Gosset and John Smolin, "A compressed classical description of quantum states", arXiv:1801.05721.

The above citations are from SAO/NASA ADS (last updated 2019-09-22 09:16:14). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2019-09-22 09:16:12).