Quantum states cannot be transmitted efficiently classically
School of Mathematics, University of Bristol, UK
Published: | 2019-06-28, volume 3, page 154 |
Eprint: | arXiv:1612.06546v3 |
Doi: | https://doi.org/10.22331/q-2019-06-28-154 |
Citation: | Quantum 3, 154 (2019). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
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] Vojtěch Havlíček and Jonathan Barrett, "Simple communication complexity separation from quantum state antidistinguishability", Physical Review Research 2 1, 013326 (2020).
[2] Leonardo Guerini, Marco Túlio Quintino, and Leandro Aolita, "Distributed sampling, quantum communication witnesses, and measurement incompatibility", Physical Review A 100 4, 042308 (2019).
[3] Ashley Montanaro and Changpeng Shao, "Quantum Communication Complexity of Linear Regression", ACM Transactions on Computation Theory 16 1, 1 (2024).
[4] Scott Aaronson, Harry Buhrman, and William Kretschmer, "A Qubit, a Coin, and an Advice String Walk Into a Relational Problem", arXiv:2302.10332, (2023).
[5] John-Mark A. Allen, "Reality, Causality, and Quantum Theory", arXiv:1901.01618, (2019).
[6] David Gosset and John Smolin, "A compressed classical description of quantum states", arXiv:1801.05721, (2018).
The above citations are from Crossref's cited-by service (last updated successfully 2024-03-29 01:39:50) and SAO/NASA ADS (last updated successfully 2024-03-29 01:39:51). 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.