Document Open Access Logo

Trade-Offs Between Entanglement and Communication

Authors Srinivasan Arunachalam, Uma Girish

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2023.25.pdf
  • Filesize: 0.87 MB
  • 23 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
  • Theory of computation → Quantum communication complexity
Keywords
  • quantum
  • communication complexity
  • exponential separation
  • boolean hidden matching
  • forrelation
  • xor lemma

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we give explicit partial functions on n bits for which reducing the entanglement increases the classical communication complexity exponentially. Our separations are as follows. For every k ≥ ~1:
Q‖^* versus R2^*: We show that quantum simultaneous protocols with Θ̃(k⁵log³n) qubits of entanglement can exponentially outperform two-way randomized protocols with O(k) qubits of entanglement. This resolves an open problem from [Dmitry Gavinsky, 2008] and improves the state-of-the-art separations between quantum simultaneous protocols with entanglement and two-way randomized protocols without entanglement [Gavinsky, 2019; Girish et al., 2022].
R‖^* versus Q‖^*: We show that classical simultaneous protocols with Θ̃(k log n) qubits of entanglement can exponentially outperform quantum simultaneous protocols with O(k) qubits of entanglement, resolving an open question from [Gavinsky et al., 2006; Gavinsky, 2019]. The best result prior to our work was a relational separation against protocols without entanglement [Gavinsky et al., 2006].
R‖^* versus R1^*: We show that classical simultaneous protocols with Θ̃(k log n) qubits of entanglement can exponentially outperform randomized one-way protocols with O(k) qubits of entanglement. Prior to our work, only a relational separation was known [Dmitry Gavinsky, 2008].

Cite As Get BibTex

Srinivasan Arunachalam and Uma Girish. Trade-Offs Between Entanglement and Communication. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 25:1-25:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.CCC.2023.25

Author Details

Srinivasan Arunachalam
  • IBM Quantum, Almaden, CA, USA
Uma Girish
  • Princeton University, NJ, USA

Acknowledgements

We thank Vojtech Havlicek and Ran Raz for many discussions during this project. We also thank Ran Raz for feedback on the presentation.

References

  1. Scott Aaronson. BQP and the polynomial hierarchy. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 141-150, 2010. Google Scholar
  2. Scott Aaronson and Andris Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 307-316, 2015. Google Scholar
  3. Nikhil Bansal and Makrand Sinha. k-forrelation optimally separates quantum and classical query complexity. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1303-1316, 2021. Google Scholar
  4. Ziv Bar-Yossef, Thathachar S Jayram, and Iordanis Kerenidis. Exponential separation of quantum and classical one-way communication complexity. SIAM Journal on Computing, 38(1):366-384, 2008. Google Scholar
  5. Avraham Ben-Aroya, Oded Regev, and Ronald de Wolf. A hypercontractive inequality for matrix-valued functions with applications to quantum computing and ldcs. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 477-486. IEEE, 2008. Google Scholar
  6. Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication complexity. computational complexity, 21(2):311-358, 2012. Google Scholar
  7. Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902, 2001. Google Scholar
  8. Harry Buhrman, Richard Cleve, and Avi Wigderson. Quantum vs. classical communication and computation. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 63-68, 1998. Google Scholar
  9. Matthew Coudron and Aram W. Harrow. Universality of EPR pairs in entanglement-assisted communication complexity, and the communication cost of state conversion. In 34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA, volume 137 of LIPIcs, pages 20:1-20:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  10. Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf. Exponential lower bounds for polytopes in combinatorial optimization. Journal of the ACM (JACM), 62(2):1-23, 2015. Google Scholar
  11. Dmitry Gavinsky. On the role of shared entanglement. Quantum Inf. Comput., 8(1):82-95, 2008. URL: https://doi.org/10.26421/QIC8.1-2-6.
  12. Dmitry Gavinsky. Quantum versus classical simultaneity in communication complexity. IEEE Transactions on Information Theory, 65(10):6466-6483, 2019. Google Scholar
  13. Dmitry Gavinsky. Bare quantum simultaneity versus classical interactivity in communication complexity. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 401-411, 2020. Google Scholar
  14. Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf. Exponential separations for one-way quantum communication complexity, with applications to cryptography. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 516-525, 2007. Google Scholar
  15. Dmitry Gavinsky, Julia Kempe, Oded Regev, and Ronald de Wolf. Bounded-error quantum state identification and exponential separations in communication complexity. In Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing, pages 594-603, 2006. Google Scholar
  16. Dmytro Gavinsky. Classical interaction cannot replace quantum nonlocality, 2009. URL: https://doi.org/10.48550/arXiv.0901.0956.
  17. Dmytro Gavinsky, Julia Kempe, and Ronald de Wolf. Strengths and weaknesses of quantum fingerprinting. CoRR, 2006. URL: https://doi.org/10.48550/arXiv.QUANT-PH/0603173.
  18. Uma Girish, Ran Raz, and Avishay Tal. Quantum versus randomized communication complexity, with efficient players. computational complexity, 31(2):17, 2022. Google Scholar
  19. Uma Girish, Ran Raz, and Wei Zhan. Lower bounds for XOR of forrelations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, volume 207 of LIPIcs, pages 52:1-52:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  20. Hamed Hatami, Kaave Hosseini, and Shachar Lovett. Structure of protocols for XOR functions. SIAM J. Comput., 47(1):208-217, 2018. Google Scholar
  21. Trinh Huynh and Jakob Nordstrom. On the virtue of succinct proofs: Amplifying communication complexity hardness to time-space trade-offs in proof complexity. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 233-248, 2012. Google Scholar
  22. Rahul Jain, Hartmut Klauck, and Ashwin Nayak. Direct product theorems for communication complexity via subdistribution bounds. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 599-608, 2007. Google Scholar
  23. Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. Prior entanglement, message compression and privacy in quantum communication. In 20th Annual IEEE Conference on Computational Complexity (CCC'05), pages 285-296. IEEE, 2005. Google Scholar
  24. Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Streaming lower bounds for approximating max-cut. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1263-1282. SIAM, 2014. Google Scholar
  25. Mauricio Karchmer, Ran Raz, and Avi Wigderson. Super-logarithmic depth lower bounds via the direct sum in communication complexity. Computational Complexity, 5(3):191-204, 1995. Google Scholar
  26. Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discret. Math., 3(2):255-265, 1990. URL: https://doi.org/10.1137/0403021.
  27. Bo'az Klartag and Oded Regev. Quantum one-way communication can be exponentially stronger than classical communication. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC '11, pages 31-40. Association for Computing Machinery, 2011. URL: https://doi.org/10.1145/1993636.1993642.
  28. Chin Ho Lee. Fourier bounds and pseudorandom generators for product tests. In 34th Computational Complexity Conference, CCC, volume 137 of LIPIcs, pages 7:1-7:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  29. Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. On data structures and asymmetric communication complexity. In Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, pages 103-111, 1995. Google Scholar
  30. Ashley Montanaro and Tobias Osborne. On the communication complexity of xor functions, 2010. URL: https://arxiv.org/abs/0909.3392.
  31. Ilan Newman. Private vs. common random bits in communication complexity. Information processing letters, 39(2):67-71, 1991. Google Scholar
  32. Ryan O'Donnell. Analysis of Boolean functions. Cambridge University Press, 2014. Google Scholar
  33. Ran Raz. Fourier analysis for probabilistic communication complexity. Comput. Complex., 5(3/4):205-221, 1995. URL: https://doi.org/10.1007/BF01206318.
  34. Ran Raz. Exponential separation of quantum and classical communication complexity. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 358-367, 1999. Google Scholar
  35. Ran Raz and Avishay Tal. Oracle separation of BQP and PH. ACM Journal of the ACM (JACM), 69(4):1-21, 2022. Google Scholar
  36. Alexander A. Sherstov, Andrey A. Storozhenko, and Pei Wu. An optimal separation of randomized and quantum query complexity. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1289-1302. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451019.
  37. Yaoyun Shi. Tensor norms and the classical communication complexity of nonlocal quantum measurement. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 460-467, 2005. Google Scholar
  38. Yaoyun Shi and Zhiqiang Zhang. Communication complexities of xor functions. arXiv preprint, 2008. URL: https://arxiv.org/abs/0808.1762.
  39. Hing Yin Tsang, Chung Hoi Wong, Ning Xie, and Shengyu Zhang. Fourier sparsity, spectral norm, and the log-rank conjecture. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 658-667, 2013. URL: https://doi.org/10.1109/FOCS.2013.76.
  40. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Proceedings of the eleventh annual ACM symposium on Theory of computing, pages 209-213, 1979. Google Scholar
  41. Huacheng Yu. Strong XOR lemma for communication with bounded rounds : (extended abstract). In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 1186-1192. IEEE, 2022. Google Scholar
  42. Shengyu Zhang. Efficient quantum protocols for xor functions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1878-1885. SIAM, 2014. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact