Document Open Access Logo

Barriers for Fast Matrix Multiplication from Irreversibility

Authors Matthias Christandl , Péter Vrana , Jeroen Zuiddam

PDF
Thumbnail PDF

File

LIPIcs.CCC.2019.26.pdf
  • Filesize: 0.51 MB
  • 17 pages

Document Identifiers

Author Details

Matthias Christandl
  • Department of Mathematical Sciences, University of Copenhagen, Universitetsparken 5, 2100 Copenhagen Ø, Denmark
Péter Vrana
  • Department of Geometry, Budapest University of Technology and Economics, Egry József u. 1., 1111 Budapest, Hungary
  • MTA-BME Lendület (Momentum) Research group
Jeroen Zuiddam
  • Institute for Advanced Study, 1 Einstein Drive, Princeton 08540, NJ, USA

Funding

  • Christandl, Matthias: European Research Council (ERC Grant Agreement No. 337603) and VILLUM FONDEN via the QMATH Centre of Excellence (Grant No. 10059).
  • Vrana, Péter: National Research, Development and Innovation Fund of Hungary within the Quantum Technology National Excellence Program (Project Nr. 2017-1.2.1-NKP-2017-00001) and research grants K124152, KH129601.
  • Zuiddam, Jeroen: National Science Foundation under Grant No. DMS-1638352.

Cite AsGet BibTex

Matthias Christandl, Péter Vrana, and Jeroen Zuiddam. Barriers for Fast Matrix Multiplication from Irreversibility. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.CCC.2019.26

Abstract

Determining the asymptotic algebraic complexity of matrix multiplication, succinctly represented by the matrix multiplication exponent omega, is a central problem in algebraic complexity theory. The best upper bounds on omega, leading to the state-of-the-art omega <= 2.37.., have been obtained via the laser method of Strassen and its generalization by Coppersmith and Winograd. Recent barrier results show limitations for these and related approaches to improve the upper bound on omega. We introduce a new and more general barrier, providing stronger limitations than in previous work. Concretely, we introduce the notion of "irreversibility" of a tensor and we prove (in some precise sense) that any approach that uses an irreversible tensor in an intermediate step (e.g., as a starting tensor in the laser method) cannot give omega = 2. In quantitative terms, we prove that the best upper bound achievable is lower bounded by two times the irreversibility of the intermediate tensor. The quantum functionals and Strassen support functionals give (so far, the best) lower bounds on irreversibility. We provide lower bounds on the irreversibility of key intermediate tensors, including the small and big Coppersmith - Winograd tensors, that improve limitations shown in previous work. Finally, we discuss barriers on the group-theoretic approach in terms of "monomial" irreversibility.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • Matrix multiplication exponent
  • barriers
  • laser method

Metrics

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

Related Versions

References

  1. Josh Alman. Limits on the Universal Method for Matrix Multiplication. arXiv, 2018. URL: http://arxiv.org/abs/1812.08731.
  2. Josh Alman and Virginia Vassilevska Williams. Further Limitations of the Known Approaches for Matrix Multiplication. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1-25:15, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.25.
  3. Josh Alman and Virginia Vassilevska Williams. Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 580-591, October 2018. URL: https://doi.org/10.1109/FOCS.2018.00061.
  4. Andris Ambainis, Yuval Filmus, and François Le Gall. Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract). In STOC'15 - Proceedings of the 2015 ACM Symposium on Theory of Computing, pages 585-593. ACM, New York, 2015. URL: https://doi.org/10.1145/2746539.2746554.
  5. Charles H. Bennett, Sandu Popescu, Daniel Rohrlich, John A. Smolin, and Ashish V. Thapliyal. Exact and asymptotic measures of multipartite pure-state entanglement. Phys. Rev. A, 63(1):012307, 2000. URL: https://doi.org/10.1103/PhysRevA.63.012307.
  6. Markus Bläser. Fast Matrix Multiplication. Number 5 in Graduate Surveys. Theory of Computing Library, 2013. URL: https://doi.org/10.4086/toc.gs.2013.005.
  7. Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin, and Chris Umans. On cap sets and the group-theoretic approach to matrix multiplication. Discrete Anal., 2017. URL: https://doi.org/10.19086/da.1245.
  8. Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A Grochow, and Chris Umans. Which groups are amenable to proving exponent two for matrix multiplication? arXiv, 2017. URL: http://arxiv.org/abs/1712.02302.
  9. Matthias Christandl, Péter Vrana, and Jeroen Zuiddam. Universal points in the asymptotic spectrum of tensors. In Proceedings of 50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC'18). ACM, New York, 2018. URL: https://doi.org/10.1145/3188745.3188766.
  10. Henry Cohn and Christopher Umans. A group-theoretic approach to fast matrix multiplication. In Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on, pages 438-449. IEEE, 2003. URL: https://doi.org/10.1109/SFCS.2003.1238217.
  11. Henry Cohn and Christopher Umans. Fast matrix multiplication using coherent configurations. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1074-1086. SIAM, 2013. URL: http://dl.acm.org/citation.cfm?id=2627817.2627894.
  12. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. J. Symbolic Comput., 9(3):251-280, 1990. URL: https://doi.org/10.1016/S0747-7171(08)80013-2.
  13. Wolfgang Dür, Guivre Vidal, and Juan Ignacio Cirac. Three qubits can be entangled in two inequivalent ways. Phys. Rev. A (3), 62(6):062314, 12, 2000. URL: https://doi.org/10.1103/PhysRevA.62.062314.
  14. Jordan S. Ellenberg and Dion Gijswijt. On large subsets of 𝐅ⁿ_q with no three-term arithmetic progression. Ann. of Math. (2), 185(1):339-343, 2017. URL: https://doi.org/10.4007/annals.2017.185.1.8.
  15. Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki. Quantum entanglement. Rev. Modern Phys., 81(2):865-942, 2009. URL: https://doi.org/10.1103/RevModPhys.81.865.
  16. J.M. Landsberg and Mateusz Michałek. Abelian tensors. Journal de Mathématiques Pures et Appliquées, 108(3):333-371, 2017. URL: https://doi.org/10.1016/j.matpur.2016.11.004.
  17. François Le Gall. Powers of tensors and fast matrix multiplication. In ISSAC 2014 - Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pages 296-303. ACM, New York, 2014. URL: https://doi.org/10.1145/2608628.2608664.
  18. Will Sawin. Bounds for matchings in nonabelian groups. arXiv, 2017. URL: http://arxiv.org/abs/1702.00905.
  19. Andrew James Stothers. On the complexity of matrix multiplication. PhD thesis, University of Edinburgh, 2010. URL: http://hdl.handle.net/1842/4734.
  20. Volker Strassen. Gaussian elimination is not optimal. Numer. Math., 13(4):354-356, 1969. URL: https://doi.org/10.1007/BF02165411.
  21. Volker Strassen. Relative bilinear complexity and matrix multiplication. J. Reine Angew. Math., 375/376:406-443, 1987. URL: https://doi.org/10.1515/crll.1987.375-376.406.
  22. Volker Strassen. The asymptotic spectrum of tensors. J. Reine Angew. Math., 384:102-152, 1988. URL: https://doi.org/10.1515/crll.1988.384.102.
  23. Volker Strassen. Degeneration and complexity of bilinear maps: some asymptotic spectra. J. Reine Angew. Math., 413:127-180, 1991. URL: https://doi.org/10.1515/crll.1991.413.127.
  24. Terence Tao. A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound, 2016. URL: https://terrytao.wordpress.com.
  25. F. Verstraete, J. Dehaene, B. De Moor, and H. Verschelde. Four qubits can be entangled in nine different ways. Phys. Rev. A (3), 65(5, part A):052112, 5, 2002. URL: https://doi.org/10.1103/PhysRevA.65.052112.
  26. Péter Vrana and Matthias Christandl. Asymptotic entanglement transformation between W and GHZ states. J. Math. Phys., 56(2):022204, 12, 2015. URL: https://doi.org/10.1063/1.4908106.
  27. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. Extended abstract. In STOC'12 - Proceedings of the 2012 ACM Symposium on Theory of Computing, pages 887-898. ACM, New York, 2012. URL: https://doi.org/10.1145/2213977.2214056.
  28. Nengkun Yu, Cheng Guo, and Runyao Duan. Obtaining a W state from a Greenberger-Horne-Zeilinger state via stochastic local operations and classical communication with a rate approaching unity. Physical review letters, 112(16):160401, 2014. URL: https://doi.org/10.1103/PhysRevLett.112.160401.
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 Imprint Privacy Contact