License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2019.10
URN: urn:nbn:de:0030-drops-104025
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10402/
Go to the corresponding LIPIcs Volume Portal

O'Gorman, Bryan

Parameterization of Tensor Network Contraction

pdf-format:
LIPIcs-TQC-2019-10.pdf (0.6 MB)

Abstract

We present a conceptually clear and algorithmically useful framework for parameterizing the costs of tensor network contraction. Our framework is completely general, applying to tensor networks with arbitrary bond dimensions, open legs, and hyperedges. The fundamental objects of our framework are rooted and unrooted contraction trees, which represent classes of contraction orders. Properties of a contraction tree correspond directly and precisely to the time and space costs of tensor network contraction. The properties of rooted contraction trees give the costs of parallelized contraction algorithms. We show how contraction trees relate to existing tree-like objects in the graph theory literature, bringing to bear a wide range of graph algorithms and tools to tensor network contraction. Independent of tensor networks, we show that the edge congestion of a graph is almost equal to the branchwidth of its line graph.

BibTeX - Entry

@InProceedings{ogorman:LIPIcs:2019:10402,
  author =	{Bryan O'Gorman},
  title =	{{Parameterization of Tensor Network Contraction}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{Wim van Dam and Laura Mancinska},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10402},
  URN =		{urn:nbn:de:0030-drops-104025},
  doi =		{10.4230/LIPIcs.TQC.2019.10},
  annote =	{Keywords: tensor networks, parameterized complexity, tree embedding, congestion}
}

Keywords: tensor networks, parameterized complexity, tree embedding, congestion
Collection: 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)
Issue Date: 2019
Date of publication: 31.05.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI