From Tensor Networks to Tractable Circuits, and back
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918476991430656 |
|---|---|
| author | Quist, Arend-Jan Bartra, Marc Farreras de Colnet, Alexis van de Wetering, John Laarman, Alfons |
| author_facet | Quist, Arend-Jan Bartra, Marc Farreras de Colnet, Alexis van de Wetering, John Laarman, Alfons |
| contents | Tensor networks and circuits are widely used data structures to represent pseudo-Boolean functions. These two formalisms have been studied primarily in separate communities, and this paper aims to establish equivalences between them. We show that some classes of tensor networks that are appealing in practice correspond to classes of circuits with specific properties that have been studied in knowledge compilation as \emph{tractable circuits}. In particular, we prove that matrix product states (tensor trains) coincide with nondeterministic edge-valued decision diagrams and that tree tensor networks exactly correspond to structured-decomposable circuits. These correspondences enable direct transfer of structural and algorithmic results; for example, canonicity and tractability guarantees known for circuits yield analogous guarantees for the associated tensor networks, and vice versa. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_00106 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | From Tensor Networks to Tractable Circuits, and back Quist, Arend-Jan Bartra, Marc Farreras de Colnet, Alexis van de Wetering, John Laarman, Alfons Quantum Physics Data Structures and Algorithms Logic in Computer Science Tensor networks and circuits are widely used data structures to represent pseudo-Boolean functions. These two formalisms have been studied primarily in separate communities, and this paper aims to establish equivalences between them. We show that some classes of tensor networks that are appealing in practice correspond to classes of circuits with specific properties that have been studied in knowledge compilation as \emph{tractable circuits}. In particular, we prove that matrix product states (tensor trains) coincide with nondeterministic edge-valued decision diagrams and that tree tensor networks exactly correspond to structured-decomposable circuits. These correspondences enable direct transfer of structural and algorithmic results; for example, canonicity and tractability guarantees known for circuits yield analogous guarantees for the associated tensor networks, and vice versa. |
| title | From Tensor Networks to Tractable Circuits, and back |
| topic | Quantum Physics Data Structures and Algorithms Logic in Computer Science |
| url | https://arxiv.org/abs/2605.00106 |