Tensor networks are nowadays the backbone of classical simulations of quantum many-body systems and quantum circuits. This is because one can contract a corresponding tensor network, which also circumvents the memory problem that often arises in large simulations. While tensor contraction itself is a rather simple operation, the order in which the tensors of the network are contracted significantly impacts the time and memory performance. For this reason, one aims at finding a priori an optimal contraction order under a cost function that models the execution time of the whole network contraction. However, there is a caveat: the problem of finding the optimal contraction is NP-hard. As a consequence, most works either improve over the exponential algorithm or fall back to greedy approaches. We argue that this is a defeatist position and show that we can indeed find optimal contraction orders for a more restrictive class of tensor networks. namely, we prove that tree tensor networks accept optimal linear contraction orders. The result comes from a fascinating yet non-trivial link between database join ordering and the presented problem. To this end, we adapt a decades-old algorithm to the context of tensor networks. Beyond the optimality results, we explore whether ad-hoc join ordering techniques aid in providing near-optimal contraction orders for general tensor networks. We empirically validate that our optimizers guarantee robustness for tree tensor networks. This work extends and builds upon our preprint [1], providing a more indepth exposition of the optimality result. Moreover, we extend its section on near-optimal optimizers, by providing a thorough study of their effectiveness for tensor networks.     «

Tensor networks are nowadays the backbone of classical simulations of quantum many-body systems and quantum circuits. This is because one can contract a corresponding tensor network, which also circumvents the memory problem that often arises in large simulations. While tensor contraction itself is a rather simple operation, the order in which the tensors of the network are contracted significantly impacts the time and memory performance. For this reason, one aims at finding a priori an optimal...     »

Tensornetzwerke sind heute das Rückgrat klassischer Simulationen von Quanten-Vielteilchen systemen und Quantenschaltungen. Das liegt daran, dass man ein entsprechendes Tensornetz kontrahieren kann, wodurch auch das Speicherproblem umgangen wird, das bei großen Simulationen oft auftritt. Während die Tensorkontraktion selbst eine recht einfache Operation ist, hat die Reihenfolge, in der die Tensoren des Netzwerks kontrahiert werden, erhebliche Auswirkungen auf die Zeit- und Speicherleistung. Aus diesem Grund versucht man, a priori eine optimale Kontraktionsreihenfolge unter einer Kostenfunktion zu finden, die die Ausführungszeit der gesamten Netzwerkkontraktion modelliert. Es gibt jedoch eine Einschränkung: Das Problem, die optimale Kontraktion zu finden, ist NP-hart. Infolgedessen verbessern die meisten Arbeiten entweder den exponentiellen Algorithmus oder greifen auf gierige Ansätze zurück. Wir argumentieren, dass dies eine defätistische Position ist und zeigen, dass wir tatsächlich optimale Kontraktionsreihenfolgen für eine restriktivere Klasse von Tensornetzen finden können. Wir beweisen nämlich, dass Baum-Tensornetzwerke optimale lineare Kontraktionsreihenfolgen akzeptieren. Das Ergebnis ergibt sich aus einer faszinierenden, aber nicht trivialen Verbindung zwischen der Optimierung der Join-Reihenfolge in Datenbanken und dem vorgestellten Problem. Zu diesem Zweck passen wir einen jahrzehntealten Algorithmus an den Kontext von Tensornetzen an. Über die Optimalitätsergebnisse hinaus untersuchen wir, ob gängige Techniken zur Optimierung der Join-Reihenfolge dazu beitragen, nahezu optimale Kontraktionssequenzen für allgemeine Tensornetzwerke zu liefern. Wir validieren empirisch, dass unsere Optimierer Robustheit für Baum-Tensornetzwerke garantieren. Diese Arbeit erweitert und baut auf unserem Preprint [1] auf, indem sie eine tiefer gehende Darstellung des Optimalitätsergebnisses liefert. Außerdem erweitern wir den Abschnitt über nahezu optimale Optimierer, indem wir eine gründliche Untersuchung ihrer Effektivität für Tensornetzwerke durchführen.     «

Tensornetzwerke sind heute das Rückgrat klassischer Simulationen von Quanten-Vielteilchen systemen und Quantenschaltungen. Das liegt daran, dass man ein entsprechendes Tensornetz kontrahieren kann, wodurch auch das Speicherproblem umgangen wird, das bei großen Simulationen oft auftritt. Während die Tensorkontraktion selbst eine recht einfache Operation ist, hat die Reihenfolge, in der die Tensoren des Netzwerks kontrahiert werden, erhebliche Auswirkungen auf die Zeit- und Speicherleistung. Aus d...     »