pith. sign in

arxiv: 2605.00106 · v1 · submitted 2026-04-30 · 🪐 quant-ph · cs.DS· cs.LO

From Tensor Networks to Tractable Circuits, and back

Arend-Jan Quist , Marc Farreras Bartra , Alexis de Colnet , John van de Wetering , Alfons Laarman This is my paper

Pith reviewed 2026-05-09 20:27 UTC · model grok-4.3

classification 🪐 quant-ph cs.DScs.LO
keywords tensor networksmatrix product statesdecision diagramstractable circuitsknowledge compilationtree tensor networkspseudo-Boolean functions
0
0 comments X p. Extension

The pith

Matrix product states coincide with nondeterministic edge-valued decision diagrams, and tree tensor networks match structured-decomposable circuits.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes exact equivalences between certain tensor network classes and tractable circuit classes from knowledge compilation. Matrix product states are shown to be identical to nondeterministic edge-valued decision diagrams. Tree tensor networks correspond precisely to structured-decomposable circuits. These identifications allow canonicity and tractability results to transfer directly between the two formalisms for representing pseudo-Boolean functions.

Core claim

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 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.

What carries the argument

Exact class-by-class correspondences that identify matrix product states with nondeterministic edge-valued decision diagrams and tree tensor networks with structured-decomposable circuits.

If this is right

  • Canonicity results proven for circuits carry over to the matching tensor networks.
  • Tractability guarantees established for one formalism apply to the other.
  • Algorithmic techniques for manipulation in circuits become available for the corresponding tensor networks.
  • Structural properties like decomposability transfer in both directions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Techniques for minimizing decision diagrams could now be applied to compress matrix product states.
  • The unification suggests hybrid representations that combine contraction methods from tensor networks with evaluation algorithms from circuits.
  • Results on variable ordering in circuits may inform bond-dimension choices in tree tensor networks.

Load-bearing premise

The standard definitions of matrix product states, tree tensor networks, nondeterministic edge-valued decision diagrams, and structured-decomposable circuits align precisely enough for the exact correspondences to hold without extra restrictions.

What would settle it

A concrete matrix product state that cannot be represented as any nondeterministic edge-valued decision diagram under the standard definitions of each would falsify the claimed coincidence.

Figures

Figures reproduced from arXiv: 2605.00106 by Alexis de Colnet, Alfons Laarman, Arend-Jan Quist, John van de Wetering, Marc Farreras Bartra.

Figure 1
Figure 1. Figure 1: Example of a structured-decomposable circuit (left) and its corresponding tree tensor network (right). The matrices of the tensors [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A non-deterministic edge-valued decision diagram (nd-EVDD) and its equivalence to a tensor train (TT). A pseudo-Boolean [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper establishes equivalences between classes of tensor networks and tractable circuits for representing pseudo-Boolean functions. Specifically, it proves that matrix product states (tensor trains) coincide with nondeterministic edge-valued decision diagrams and that tree tensor networks exactly correspond to structured-decomposable circuits, enabling bidirectional transfer of canonicity, tractability, and algorithmic results between the two formalisms.

Significance. If the claimed exact correspondences hold, the work is significant for bridging the tensor network community (physics/quantum information) with knowledge compilation (circuits), allowing direct reuse of structural guarantees such as canonicity results from one side to the other without re-derivation.

minor comments (2)
  1. The abstract and introduction should explicitly state the variable ordering assumptions and normalization conventions used in the mappings to confirm they match the standard definitions of MPS/TTNs and EVDDs/SDCs without reinterpretation.
  2. Include a small illustrative example (e.g., a 3-variable function) showing the explicit construction in both directions for the MPS-EVDD equivalence to aid readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work and the recommendation for minor revision. The referee correctly identifies the key contributions regarding the equivalences between matrix product states and nondeterministic edge-valued decision diagrams, as well as tree tensor networks and structured-decomposable circuits. These correspondences indeed facilitate the transfer of canonicity, tractability, and algorithmic results between tensor networks and knowledge compilation. Since no specific major comments were provided in the report, we have no particular points to address at this stage. We will incorporate any minor revisions as suggested by the editor.

Circularity Check

0 steps flagged

Equivalence proofs are direct structural mappings with no reduction to inputs by construction

full rationale

The paper proves that matrix product states coincide with nondeterministic edge-valued decision diagrams and tree tensor networks correspond to structured-decomposable circuits. These are mappings between independently developed formalisms studied in separate communities. The abstract and claimed results involve showing structural and semantic alignments via explicit constructions and proofs, without any fitted parameters, self-definitional loops, or load-bearing self-citations that reduce the central claims to tautologies. The derivations are self-contained against external definitions of the objects involved.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The equivalences rest on the assumption that both formalisms represent the same pseudo-Boolean functions under standard definitions from their respective fields; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Tensor networks and circuits are data structures that represent the same class of pseudo-Boolean functions
    Invoked as the foundation for proving structural coincidences.

pith-pipeline@v0.9.0 · 5438 in / 1091 out tokens · 34210 ms · 2026-05-09T20:27:16.729384+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

46 extracted references · 5 canonical work pages

  1. [1]

    Acuaviva, A., et al. 2023. The minimal canonical form of a tensor network. arXiv preprint arXiv:2209.14358

    work page arXiv 2023

  2. [2]

    A.; Jayaram, R.; and Riveros, C

    Arenas, M.; Croquevielle, L. A.; Jayaram, R.; and Riveros, C. 2021. \#NFA admits an FPRAS: efficient enumeration, counting, and uniform generation for logspace classes. J. ACM 68(6):48:1--48:40

    2021

  3. [3]

    Beyersdorff, O.; Giesen, J.; Goral, A.; Hoffman, T.; Kasche, K.; and Staudt, C. 2026. Proof systems for tensor-based model counting. In To appear in AAAI 2026

    2026

  4. [4]

    D.; Morton, J.; and Turner, J

    Biamonte, J. D.; Morton, J.; and Turner, J. 2015. Tensor network contractions for \# SAT . Journal of Statistical Physics

    2015

  5. [5]

    Bollig, B., and Wegener, I. 1996. Improving the variable ordering of OBDDs is NP -complete. IEEE Transactions on computers 45(9):993--1002

    1996

  6. [6]

    Bova, S.; Capelli, F.; Mengel, S.; and Slivovsky, F. 2016. Knowledge compilation meets communication complexity. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI) , 1008--1014

    2016

  7. [7]

    Broeck van den Broeck , G., and Darwiche, A. 2015. On the role of canonicity in knowledge compilation. In Bonet, B., and Koenig, S., eds., Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA , 1641--1648. AAAI Press

    2015

  8. [8]

    Bryant. 1986. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers C-35(8):677--691

    1986

  9. [9]

    Chamon, C., and Mucciolo, E. R. 2012. Virtual parallel computing and a search algorithm using matrix product states. Phys. Rev. Lett. 109:030503

    2012

  10. [10]

    Choi, A., and Darwiche, A. 2013. Dynamic minimization of sentential decision diagrams. In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI)

    2013

  11. [11]

    I.; Pérez-García, D.; Schuch, N.; and Verstraete, F

    Cirac, J. I.; Pérez-García, D.; Schuch, N.; and Verstraete, F. 2021. Matrix product states and projected entangled pair states: Concepts, symmetries, theorems. Reviews of Modern Physics 93(4)

    2021

  12. [12]

    Cross, A., and Vandeth, D. 2025. Small binary stabilizer subsystem codes. arXiv preprint arXiv:2501.17447

    work page arXiv 2025

  13. [13]

    Darwiche, A., and Marquis, P. 2002. A knowledge compilation map. J. Artif. Intell. Res. 17:229--264

    2002

  14. [14]

    Darwiche, A. 2001. Decomposable negation normal form. Journal of the ACM (JACM) 48(4):608--647

    2001

  15. [15]

    Darwiche, A. 2011. SDD : A new canonical representation of propositional knowledge bases. In IJCAI Proceedings-International Joint Conference on Artificial Intelligence

    2011

  16. [16]

    de Colnet, A., and Mengel, S. 2020. Lower bounds for approximate knowledge compilation. Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI)

    2020

  17. [17]

    de Colnet, A. 2020. A lower bound on DNNF encodings of pseudo-boolean constraints. In Pulina, L., and Seidl, M., eds., Theory and Applications of Satisfiability Testing - SAT 2020 - 23rd International Conference, Alghero, Italy, July 3-10, 2020, Proceedings , Lecture Notes in Computer Science, 312--321. Springer

    2020

  18. [18]

    M.; Due \ n as - Osorio, L.; and Vardi, M

    Dudek, J. M.; Due \ n as - Osorio, L.; and Vardi, M. Y. 2019. Efficient contraction of large tensor networks for weighted model counting through graph decompositions. CoRR abs/1908.04381

    work page arXiv 2019

  19. [19]

    M.; Phan, V

    Dudek, J. M.; Phan, V. H. N.; and Vardi, M. Y. 2020. DPMC: weighted model counting by dynamic programming on project-join trees. In Simonis, H., ed., Principles and Practice of Constraint Programming - 26th International Conference, CP 2020, Louvain-la-Neuve, Belgium, September 7-11, 2020, Proceedings , volume 12333 of Lecture Notes in Computer Science , ...

    2020

  20. [20]

    Fargier, H.; Marquis, P.; Niveau, A.; and Schmidt, N. 2014. A knowledge compilation map for ordered real-valued decision diagrams. In Proceedings of the AAAI Conference on Artificial Intelligence

    2014

  21. [21]

    Garcia-Saez, A., and Latorre, J. I. 2011. An exact tensor network for the 3SAT problem

    2011

  22. [22]

    J., and Lim, L.-H

    Hillar, C. J., and Lim, L.-H. 2013. Most tensor problems are np-hard. Journal of the ACM (JACM)

    2013

  23. [23]

    L.; and Wille, R

    Hillmich, S.; Zulehner, A.; Kueng, R.; Markov, I. L.; and Wille, R. 2022. Approximating decision diagrams for quantum circuit simulation. ACM Transactions on Quantum Computing 3(4):1--21

    2022

  24. [24]

    Khoromskij, B. N. 2014. Tensor numerical methods for high-dimensional PDE s: Basic theory and initial applications

    2014

  25. [25]

    Kisa, D.; van den Broeck, G.; Choi, A.; and Darwiche, A. 2014. Probabilistic sentential decision diagrams. In KR

    2014

  26. [26]

    Kourtis, S.; Chamon, C.; Mucciolo, E.; and Ruckenstein, A. E. 2019. Fast counting with tensor networks. SciPost Physics 7(5):060

    2019

  27. [27]

    Lai, Y.-T.; Pedram, M.; and Vrudhula, S. 1994. EVBDD -based algorithms for integer linear programming, spectral transformation, and function decomposition. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 13(8):959--975

    1994

  28. [28]

    Legeza, \"O ., and S \'o lyom, J. 2003. Optimizing the density-matrix renormalization group method using quantum information entropy. Physical Review B

    2003

  29. [29]

    Li, W.; Ren, J.; Yang, H.; Wang, H.; and Shuai, Z. 2024. Optimal tree tensor network operators for tensor network simulations: Applications to open quantum systems. The Journal of Chemical Physics

    2024

  30. [30]

    Li, T.; Precup, D.; and Rabusseau, G. 2022. Connecting weighted automata, tensor networks and recurrent neural networks through spectral learning

    2022

  31. [31]

    Loconte, L.; Mari, A.; Gala, G.; Peharz, R.; de Campos, C.; Quaeghebeur, E.; Vessio, G.; and Vergari, A. 2025. What is the relationship between tensor factorizations and circuits (and how can we exploit it)? Trans. Mach. Learn. Res. 2025

    2025

  32. [32]

    Loconte, L.; Javaloy, A.; and Vergari, A. 2025. How to square tensor networks and circuits without squaring them. CoRR abs/2512.17090

    work page arXiv 2025

  33. [33]

    Loconte, L.; Mengel, S.; and Vergari, A. 2025. Sum of squares circuits. In Proceedings of the AAAI Conference on Artificial Intelligence

    2025

  34. [34]

    S., and de Colnet, A

    Meel, K. S., and de Colnet, A. 2025. An FPRAS for model counting for non-deterministic read-once branching programs. In 28th International Conference on Database Theory (ICDT 2025) , 30--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik

    2025

  35. [35]

    S., and de Colnet, A

    Meel, K. S., and de Colnet, A. 2026. \# CFG and \# DNNF admit FPRAS . Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)

    2026

  36. [36]

    Miller, D.; Thornton, M.; and Goodman, D. 2006. A decision diagram package for reversible and quantum circuit simulation. In 2006 IEEE International Conference on Evolutionary Computation , 2428--2435

    2006

  37. [37]

    Onaka, R.; Nakamura, K.; Nishino, M.; and Yasuda, N. 2025. Tensor decomposition meets knowledge compilation: A study comparing tensor trains with OBDDs . In Walsh, T.; Shah, J.; and Kolter, Z., eds., AAAI-25, Sponsored by the Association for the Advancement of Artificial Intelligence, February 25 - March 4, 2025, Philadelphia, PA, USA , 15109--15117. AAAI Press

    2025

  38. [38]

    Oseledets, I. V. 2011. Tensor-train decomposition. SIAM Journal on Scientific Computing 33(5):2295--2317

    2011

  39. [39]

    Pipatsrisawat, K., and Darwiche, A. 2008. New compilation languages based on structured decomposability. In AAAI , volume 8, 517--522

    2008

  40. [40]

    Schollwöck, U. 2011. The density-matrix renormalization group in the age of matrix product states. Annals of Physics 326(1):96–192

    2011

  41. [41]

    Shi, Y.-Y.; Duan, L.-M.; and Vidal, G. 2006. Classical simulation of quantum many-body systems with a tree tensor network. Phys. Rev. A 74:022320

    2006

  42. [42]

    Valiant, L. G. 1979. Negation can be exponentially powerful. In Proceedings of the eleventh annual ACM symposium on theory of computing , 189--196

    1979

  43. [43]

    Vergari, A.; Choi, Y.; Liu, A.; Teso, S.; and van den Broeck, G. 2021. A compositional atlas of tractable circuit operations for probabilistic inference. In Ranzato, M.; Beygelzimer, A.; Dauphin, Y. N.; Liang, P.; and Vaughan, J. W., eds., Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021...

    2021

  44. [44]

    Vinkhuijzen, L.; Coopmans, T.; and Laarman, A. 2026. A knowledge compilation map for quantum information. In Proceedings of the AAAI Conference on Artificial Intelligence

    2026

  45. [45]

    Zuidberg Dos Martires , P. 2024. Probabilistic neural circuits. Proceedings of the AAAI Conference on Artificial Intelligence 38(15):17280--17289

    2024

  46. [46]

    Zuidberg Dos Martires , P. 2025. A quantum information theoretic approach to tractable probabilistic models. arXiv preprint arXiv:2506.01824

    work page arXiv 2025