Document Open Access Logo

Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication

Authors Harry Buhrman, Matthias Christandl, Jeroen Zuiddam

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2017.24.pdf
  • Filesize: 0.53 MB
  • 18 pages

Document Identifiers

Author Details

Harry Buhrman
Matthias Christandl
Jeroen Zuiddam

Cite As Get BibTex

Harry Buhrman, Matthias Christandl, and Jeroen Zuiddam. Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ITCS.2017.24

Abstract

We study nondeterministic multiparty quantum communication with a quantum generalization of broadcasts. We show that, with number-in-hand classical inputs, the communication complexity of a Boolean function in this communication model equals the logarithm of the support rank of the corresponding tensor, whereas the approximation complexity in this model equals the logarithm of the border support rank. This characterisation allows us to prove a log-rank conjecture posed by Villagra et al. for nondeterministic multiparty quantum communication with message passing.
The support rank characterization of the communication model connects quantum communication complexity intimately to the theory of asymptotic entanglement transformation and algebraic complexity theory. In this context, we introduce the graphwise equality problem. For a cycle graph, the complexity of this communication problem is closely related to the complexity of the computational problem of multiplying matrices, or more precisely, it equals the logarithm of the support rank of the iterated matrix multiplication tensor. We employ Strassen’s laser method to show that asymptotically there exist nontrivial protocols for every odd-player cyclic equality problem. We exhibit an efficient protocol for the 5-player problem for small inputs, and we show how Young flattenings yield nontrivial complexity lower bounds.

Subject Classification

Keywords
  • quantum communication complexity
  • broadcast channel
  • number-in-hand
  • matrix multiplication
  • support rank

Metrics

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

References

  1. Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, and Hein Röhrig. Multiparty quantum coin flipping. In Computational Complexity, 2004. Proceedings. 19th IEEE Annual Conference on, pages 250-259. IEEE, 2004. http://arxiv.org/abs/quant-ph/0304112, URL: http://dx.doi.org/10.1109/CCC.2004.1313848.
  2. Michael Ben-Or and Richard Cleve. Computing algebraic formulas using a constant number of registers. SIAM Journal on Computing, 21(1):54-58, 1992. URL: http://dx.doi.org/10.1137/0221006.
  3. Amey Bhangale and Swastik Kopparty. The complexity of computing the minimum rank of a sign pattern matrix. arXiv preprint arXiv:1503.04486, 2015. URL: http://arxiv.org/abs/1503.04486.
  4. Markus Bläser. Complete problems for Valiant’s class of qp-computable families of polynomials. In Computing and Combinatorics, pages 1-10. Springer, 2001. URL: http://dx.doi.org/10.1007/3-540-44679-6_1.
  5. Markus Bläser. Fast matrix multiplication. Theory of Computing, Graduate Surveys, 5:1-60, 2013. URL: http://dx.doi.org/10.4086/toc.gs.2013.005.
  6. Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi. Algebraic complexity theory, volume 315 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig. URL: http://dx.doi.org/10.1007/978-3-662-03338-8.
  7. Eric Chitambar, Runyao Duan, and Yaoyun Shi. Tripartite entanglement transformations and tensor rank. Physical review letters, 101(14):140502, 2008. http://arxiv.org/abs/0805.2977, URL: http://dx.doi.org/10.1103/PhysRevLett.101.140502.
  8. Matthias Christandl and Jeroen Zuiddam. Tensor surgery and tensor rank. arXiv preprint arXiv:1606.04085, 2016. URL: http://arxiv.org/abs/1606.04085.
  9. Henry Cohn and Christopher Umans. Fast matrix multiplication using coherent configurations. In Proceedings of the Twenty-fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'13, pages 1074-1086, Philadelphia, PA, USA, 2013. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2627817.2627894, URL: http://arxiv.org/abs/1207.6528.
  10. Fulvio Gesmundo. Geometric aspects of iterated matrix multiplication. Journal of Algebra, 461:42-64, 2016. http://arxiv.org/abs/1512.00766, URL: http://dx.doi.org/10.1016/j.jalgebra.2016.04.028.
  11. Christian Ikenmeyer. Geometric complexity theory, tensor rank, and Littlewood-Richardson coefficients. PhD thesis, Universität Paderborn, 2013. URL: http://nbn-resolving.de/urn:nbn:de:hbz:466:2-10472.
  12. Joseph M. Landsberg and Mateusz Michałek. On the geometry of border rank algorithms for matrix multiplication and other tensors with symmetry. arXiv preprint arXiv:1601.08229, 2016. URL: http://arxiv.org/abs/1601.08229.
  13. Joseph M. Landsberg and Giorgio Ottaviani. New lower bounds for the border rank of matrix multiplication. Theory Comput., 11:285-298, 2015. http://arxiv.org/abs/1112.6007, URL: http://dx.doi.org/10.4086/toc.2015.v011a011.
  14. François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC'14, pages 296-303, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2608628.2608664.
  15. Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, Cambridge, 2000. Google Scholar
  16. Arnold Schönhage. Partial and total matrix multiplication. SIAM Journal on Computing, 10(3):434-455, 1981. URL: http://dx.doi.org/10.1137/0210032.
  17. Volker Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13(4):354-356, 1969. URL: http://dx.doi.org/10.1007/BF02165411.
  18. Volker Strassen. Rank and optimal computation of generic tensors. Linear algebra and its applications, 52:645-685, 1983. URL: http://dx.doi.org/10.1016/0024-3795(83)80041-X.
  19. Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita, and Yasuhiko Nakashima. Tensor rank and strong quantum nondeterminism in multiparty communication. In Theory and applications of models of computation, volume 7287 of Lecture Notes in Comput. Sci., pages 400-411. Springer, Heidelberg, 2012. http://arxiv.org/abs/1202.6444, URL: http://dx.doi.org/10.1007/978-3-642-29952-0_39.
  20. Péter Vrana and Matthias Christandl. Entanglement distillation from Greenberger-Horne-Zeilinger shares. arXiv preprint arXiv:1603.03964, 2016. URL: http://arxiv.org/abs/1603.03964.
  21. Ronald de Wolf. Nondeterministic quantum query and communication complexities. SIAM Journal on Computing, 32(3):681-699, 2003. http://arxiv.org/abs/cs/0001014, URL: http://dx.doi.org/10.1137/S0097539702407345.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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