How to Square Tensor Networks and Circuits Without Squaring Them
Authors: Lorenzo Loconte
Adrián Javaloy
Antonio Vergari
Venue: ICLR 2026 Poster (2026)
Keywords: tensor-networks
circuits
probabilistic-methods
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: We derive novel circuit properties based on orthogonality as to speed-up marginalization in squared circuits and tensor network-based Born machines, as well as to unlock more factorization structures enabling tractable marginalization

Abstract: Squared tensor networks (TNs) and their extension as computational graphs---squared circuits---have been used as expressive distribution estimators, yet supporting closed-form marginalization. However, the squaring operation introduces additional complexity when computing the partition function or marginalizing variables, which hinders their applicability in ML. To solve this issue, canonical forms of TNs are parameterized via unitary matrices to simplify the computation of marginals. However, these canonical forms do not apply to circuits, as they can represent factorizations that do not directly map to a known TN. Inspired by the ideas of orthogonality in canonical forms and determinism in circuits enabling tractable maximization, we show how to parameterize squared circuits to overcome their marginalization overhead. Our parameterizations unlock efficient marginalization even in factorizations different from TNs, but encoded as circuits, whose structure would otherwise make marginalization computationally hard. Finally, our experiments on distribution estimation show how our proposed conditions in squared circuits come with no expressiveness loss, while enabling more efficient learning.

Published as a conference paper at ICLR 2026
How TO SQUARE TENSOR NETWORKS AND CIRCUITS WITHOUT SQUARING THEM
Lorenzo Loconte
Adrián Javaloy a javalloyeed acc uk
Antonio Vergari -
1. Loconte@sms.s.... ed. ac.uk
avergari@ed.ce ac.
School of Informatics, University of Edinburgh, UK
ABSTRACT
Squared tensor networks (TNs) and their extension as computational graphs squared circuits-have been used as expressive distribution estimators, yet sup- porting closed-form marginalization. However, the squaring operation introduces additional complexity when computing the partition function or marginalizing variables, which hinders their applicabilitty in ML. To solve this issue, canonical forms of TNs are parameterized via unitary matrices to simplify the computation of marginals. However, these canonical forms do not apply to circuits, as they can rep- resent factorizations that do not directly map to known TN. Inspired by the ideas orthogonality in canonical forms and determinism circuits enabling tractable maximization, show how to parameterize squared circuits to overcome their marginalization overhead. Our parameterizations unlock efficient marginalization even in factorizations different from TNs, but encoded circuits, whose structure would otherwise make marginalization computationally hard. Finally, our exper- iments on distribution estimation show how our proposed conditions in squared circuits come with no expressiveness loss, while enabling more efficient learning.
INTRODUCTION
Tensor networks (TNs) are low-rank factorizations of tensors with applications in machine learning (Stoudenmire and Schwab, 2016; Han et al., 201 8; Cheng et al., 2019; Novikov et al., 2021; Tomut al., 2024), quantum physics (Schollwoeck, 2010: Biamonte and Bergholm, 2017) and quantum computing (Markov and Shi, 2008). A TN factorizes complex function & over a set of variables X (X,) having domain dom(X) X). which can be then used to model a probability distribution via modulus squaring, i.e., p(X) = (x) where Z = Jdam(x) [x)] dx is the partition function. Recently, Loconte et al. (2025b;a) have shown that the computations done with TN can be generalized into computational graphs akin to neural networks, called circuits (Darwiche and Marquis, 2002; Choi al., 2020b; Vergari et al., 2021). This is done by casting contractions between tensors in TN into hierarchical composition of sum and product computational units.
The language of circuits offers the opportunity flexibly build novel TN factorizations by stacking layers of sums and products as "Lego blocks" (Loconte et al., 2025a), including different basis input functions, and providing seamless integration with deep learning architectures (Shao al., 2022; Gala et al., 2024a;b). Moreover, viewing TNs as circuits allows one to exploit rich framework of structural properties, defined over their computational graph and parameterization, compose circuits and compute several probabilistic reasoning tasks in closed-fore These include the evaluation of information -theoretiict measures and expectations (Vergari et al., 2021), 12,1, which crucial for example in reliable neurosymbolic AI (Ahmed et al., 2022; Kurscheidt al.. 2025; Marconato et al., 2024a;b) and causal inference (Choi et al., 2020a; Wang et al., 2024). This is done with probabilistic circuits (PCssicircuis encoding probability distributions, that traditionally restricted to have positive
(PCs) circuits parameters only, i.e., monotonic PCs (Shpilka and Yehudayoff, 2010).
To increase the expressiveness of PCs for representing complicated distributions, one equip them with real parameters and square them (Loconte et al., 2024), similar to TNs. Mixing squared PCs together also provides further expressiveness gains (Loconte al., 2025b). However, differently from

---

Published as a conference paper at ICLR 2026
monotonic PCs that are not squared, squared PCs require additional overhead to be normalized. i.e., to compute Z. That is, under particular structural properties, squaring circuits and computing Z has quadratic complexity w.r.t the circuit size (Vergari et al., 2021). This quadratic complexity overhead carries over the computation of marginals that are simpler than the partition function, i.e., where only proper subset of variables are integrated out. This overhead limits the application of squared PCs in settings where performing exact yet efficient conditioning is crucial, e.g., as for sampling (Loconte al., 2024) and in lossless data compression (Yang et al., 2022; Liu et al., 2022).
One possible solution might come from the TN literature, where canonical forms are used to simplify the computation of marginals (Schollwoeck, 20 2010; Bonnevie and Schmidt, 2021). E.g. instead of computing the partition function Z explicitly in TN, canonical form ensures (x) is an already- normalized distribution, i.e., = 1. In practice, canonical forms are obtained by parameterizing a TN by means of (semi-Junitary matrices. However, different TNs need different canonical forms, and each of them is tailored for specific marginals only, yielding left/righh/mixed/upper canonical forms in
states (MPS) (Orás and Vidal, 2008) and tree TNs (TTNs) (Shi et al., 2006; Cheng et al., 2019). These canonical forms cannot be applied to circuits, as they might not correspond to a known factorization method or TN (Loconte et al., 2025a). Here, we extract the core principle behind canonical forms and reformulate in terms of new structural properties of circuits. Our conditions revolve around the idea of orthogonality between units of the circuit computational graph, which we find to be surprisingly related with a classical circuit property, called determinism, which so far has been mostly exploited in the context of tractable maximization (Darwiche and Marquis, 2002) with PCs and never linked to TNs before.
Our main contributions are the following: (i) We derive properties based on orthogonality to enable linear-time marginalization in squared PCs, thus improving over its usual quadratic complexity w.r.t. their size ($3). (ii) Since PCs often consist of densely- conneee-e layers of sums and products, we relax our orthogonality properties over scalar units in favor of a parameterization over layers, exploiting seeti-yu matrices instead. While this parameterization similar to canonical forms in TTNs, we show it generalizes to a strictly larger set of factorizations when represented as circuits (84). (iii) Under this parameterization, we derive an algorithm to marginalize any variable subset whose best-case complexity scales linearly w.r.t. the number of layers and their size, thus finding better complexity bound than previous known one that squared all layer sizes ($5). (iv) Our experiments on distribution estimation show performance loss under the proposed circuit properties, while enabling more efficient training and the use of previously unavailable circuit architectures ($6).
FROM TENSOR NETWORKS TO SQUARED PROBABILISTUS CIRCUITS
We introduce the close relationship between TNs and circuits (Loconte et al., 2024; 2025a), and show how they can encode probability distributions via modulus squaring. TNs encode hierarchical factorizations of high dimensional tensors (or functions). Perhaps the most popular TN factorization is the matrix-produs state (MPS) (Pérez-García et al., 2007), also called tensor-train (Oseledets, 2011). A R MPS factorization encodes a function vó over variables X
1 as
R (xx) E',
D Σ R
R
= of (I) (u1 (122) ... 1. did
(Ir- ( 1) ( (1)
i, i==1
where vh dom(m)) (X1) CB, wha dom(X, (xa) - CR, and vik dom(X;) CRXR with 1 < k: < d are the factors. The superscript indices in Eq. (1) select scalar entries from the factors. Note that in the case of X being discrete with finite domain, Eq. (1) can be seen as a factorization of d-dimensional tensor (Kolda, 2006; Kolda and Bader, 2009). Given an assignment x = (I1,..., E dom computing the value of (x) translates to evaluating the univariate factors, products and sums in Eq. (1), i.e., a complete contraction of the TN (Orús, 2013). While the naive way of contracting the TN in Eq. (1) requires time ( one can do it time (IPdd by computing products and sums in precise left-to-right ordering, i.e., as d - 1 matrix-vector products. The computational graph of sums and products resulting from the TN contraction in particular ordering is a circuit.
Definition 1 (Cireuit (Choi al., 2020b; Vergari et al., 2021)). A circuit e is a parameterized computational graph over variables X encoding a function c: dom(X) - C, and comprising three kinds of units: input, product and sum. Each product sum unit n receives the outputs of other units as inputs, denoted with the set in(n). Each unit n encodes a function c, defined as: (i) fa fx( if n. is an input unit, where fa is function over the variable sc(n) {X} C X, called its
2

---

Published as a conference paper at ICLR 2026
Figure 1: Matrix-product states (MPSs) are circuits. A
MPS TN of rank R = 2, here in Penrose graphical notation (bottom right), models a function & over X [X1, X2, X3}
(2s))
as (x) = Σ Eiy= v1 (x1) 22
(xs).
vi(a))
(((s))
Given an assignment X = (x), 22, Ta), the circuit computes the complete contraction of the MPS, i.e., (x() (above left).
vffa))
The circuit input units (+) compute the factors vir 1/2 2
(ma)
(ari it. #t.
vi over X1, X2. Xa. highlighted in their respective colors. The composition of product (8) and sum (0) units encode the contraction of the factors following left-to-right order- ing, i.., multiplying and summing the violet (th) ) and orange (w2) factors before the green one (1/a). Here, sum weights fixed to 1, but can generally be any complex number.
vi (xx)
4/2
4/y
(xx)
v
Xi Xs
scope, (ii) IE (sc(i)) n is a product, and (iii) Exein(n) (n,,c(ss((i) if n is a sum, where {Wa, E C (eEi(()) are the parameters of the sum unit. The scope of a product or sum unit is the union of the scopes of its inputs, i.e., sc(n)) = Usein(n) sc(i).
The circuit size, denoted as |c]. is the number of edges between the units. Evaluating a circuit e on an variables assignment x, i.e., computing c(x), is done by evaluating the input functions, products and sums, by following the computational graph, thus requiring time (lc)). Fig. 1 shows an example of MPS approximation of v represented in Penrose graphical notation (Penrose, 1971), and the circuit e encoding its left-to-right contraction, i.e., (x(x = c(x) as in Eq. (1). The circuit language allows to build factorizations by directly connecting sums and products, which in the end might not correspond to any known TN structure or other tensor factorization method (Loconte et al., 2025a).
Structural properties specified over a circuit graph structure provide sufficient conditions to guaran- tee the tractable computation of quantities useful in a number of scenarios (Darwiche and Marquis, 2002: Vergari et al., 2021; Wang et al.. 2024). For example, a circuit supports the exact integration of any variable subset in time ([c)) if (i) its input functions can be integrated efficiently and (ii) it is smooth and decomposable (Choi al., 2020b), as formalized next.
Definition 2 (Smoothness and decomposability (Darwiche and Marquis, 2002)). A circuit is smooth for every sum unit n, all its input units depend on the same variables, i.e., Vi,j E in(n): sc(i) sc(j). circuit is decomposable if the distinct inputs of every product unit n depend on disjoint sets of variables, i.e., j E in(n) i + j: sc(i) n sc(( Ø.
Smoothness and decomposability are related to multilinearityy a classical property of tensor factor- izations (Kolda and Bader, 2009), as smooth and decomposable circuit is guaranteed to encode a multilinear function (or polynomial) w.r.t. input functions (Martens and Medabalimi, 2014 4: Oliver Broadrick, 2024). We will make use of another property known as determinism, which instead ensures tractable maximum-a poosterririi inference circuits (Darwiche, 2009; Choi al., 2020b).
Definition 3 (Determinism (or support-decomposaiiiyy (Darwiche and Marquis, 2002; Choi et al., 2020b)). A sum unit n is deterministic (or support-decomposalie disjoint supports, i.e., Vi.j E in(n), i + j: supp(i) n supp(j) = Ø, where supp(n) = {x E dom(sc(n)) C, (x) A 0}. A circuit is deterministic if every sum unit in it is deterministic.
if all its inputs have pairwise
Unlike the relationship between smoothness, decomposability and multilinearity, a property similar to determinism has not been explored in tensor factorization techniques. The relationship between determinism and orthogonality will be crucial $3 to devise canonical forms for eircuits.
A probabilistic circuit (PC) is a circuit e encoding non-negative function, thus modeling possibly unnormalized probability distribution p(x) = - z-fc(x) where Z is the partition function (Choi et al., 2020b; Vergari et al., 2021). To construct and learn circuit that is PC, its parameters and input functions can be enforced to be non-negative, i.c., they are monotonic PCs (Shpilka and Yehudayoff, 2010). This in fact ensures the circuit outputs also non-negaevve. However, PCs whose parameters can be negative, i.c., non-monotonic PCs, have been shown to be strictly more expressive models than monotonic ones (Valiant, 1979). Building and learning non-monotonic PCs flexibly while ensuring
3

---

Published as a conference paper at ICLR 2026
they compute non non-negative function is in general a challenging problem (Dennis, 2016). However, a family of non-monotonic PCs can be constructed via squaring, as we detail next.
Born machines and squared PCs. As mentioned above, model distribution p(X) we can take the modulus square of a complex-valued TN, resulting in a model often called Born machine (Dirac, 1930; Glasser al., 2018). One similarly build non-monotonic PCs by squaring circuits with real or complex parameters, which comes with theoretically guarantees regarding their increased expressiveness over monotonic ones (Loconte et al., 2024; 2025b). The property-driver framework of circuits precisely tells us how to build circuit such that its squaring can be marginalized efficiently, This problem is analogous to the one of representing the multiplication of two TNs yet another TN (Michailidis et al., 2024). Formally, given a circuit c, a squared PC c² encodes a distribution p(x) = Z |c(x)] where Z Jaom(x) |c(x)]² dx. Computing Z or any marginal tractably requires
representing c² as yet another decomposable circuit (Def. 2), which can be obtained by multiplying with its conjugate c*. While the conjugate circuit c* can be efficiently obtained from c by simply taking the conjugate of the sum parameters and input functions ( (Yu et al., 2023), realizing the product of any two decomposable circuits as a decomposable circuit is in general #P-hard problem (Vergari et al., 2021). However, it can be done efficiently if these circuits are compatible.
Definition 4 (Compatibility (Vergari et al., 2021)). Two smooth and decomposable circuits c1. C2 over variables X are compatible if (i) the product of any pair fn. f' of input functions respectively in G1, 62 over the same variable can be efficiently integrated, and (ii) any pair n, m of product units respectively C1. 02 having the same scope decompose their scope over their inputs in the same way.
We say that circuit is structured-decome decomposable if it is compatible with itself (Pipatsrisawat and Darwiche, 2008), i.e., all products having the same scope decompose it towards their inputs in the same way. As detailed in App. B, circuits corresponding to MPS and TTN TNs structured- decomposable. If a circuit è is structured decooposabe......eeelll then its products implicitly encode a tree- like partitioning of variables (Kisa et al., 201 2014), which ensures that the product between and e" can be encoded by a decomposable circuit of size ([cc))). This can be done via a circuit multiplication algorithm as shown in Vergari et (2021). The quadratic increase in eircuit size is why computing the partition function or any marginal ultimately requires time ([c]²). In the next section, we address this quadratic complexity overhead in squared PCs by deriving novel structural properties.
3 RELAXING DETERMINISM VIA ORTHOGONALITY
By showing how both TN canonical forms and determinism in circuits bring simplifications when computing marginals, we translate the key idea of orthogonality to the language of circuits. Consider an MPS encoding & over variables X {X,, X2). i.c.. (0 x2) Ei t (z1 (12) As an example, consider a left canonical form requiring the factors (wite over Xi satisfy the orthonor- mality condition faom(x.) v1 (x1) (z1)" dx, (wi wH/) = 61j. where 5,y is the Kronecker delta. Under this condition, can simplify the marginal p(zz) [oom(X.) (1 x22) dr, as
Σ
R
(vi
n wit (12 = Σ 1=1 lv)
because the inner product (wf wh) is zero whenever j. We observe that the same simplification from OR?) to O(R) sums would occur also if the factors { were instead defined over non- overlapping supports, i.c., Vi.j E [R]. # j. at least one between w and v/ is zero. Exploiting factors having non-overlapping supports rather than being orthogonal suggests us could use determinism in order to simplify marginalization in squared PCs. Formally, given n a deterministic sum unit computing Gn (x1 x22) = Eigin()) (2), we can write Cn x2)) as
EnEn(H) Eyennt w.wz ci (2)1, EvEnot, |w:|² (2)
since due to determinism at least one between e; and Cj is zero whenever i + j. From Eq. (3) we recover that the number of input connections to a deterministic sum unit does not quadratically increases when taking its modulus square. Therefore, by recursively applying Eq. (3) for all sum units in a deterministic circuit c, it turns out that a decomposable squared PC can be obtained from c of the same size. For this reason, the satisfaction of determinism allows to compute any marginal
4

---

Published as a conference paper at ICLR 2026
(ins) (((()s)
w
(l))
(((1))
(Xa)
vd (12)
a2,,)
(x2))
(z))
(12(
v (ma)
12 (20)
(b)
Figure 2: Deterministic and orthogonal circuits differ by their input functions. (left) We consider the circuit representing the MPS shown in Fig. 1, and we color each input function v/2 uif1 over the variable X2 differently. Each sum unit is basis decomposable, as partitions the sets of input functions over X2 towards its inputs (see how colored edges are split at sum units). (right) If we take input functions over X2 having non-overlapping support (a), we recover determinism c. Instead, the input functions are orthogonal yet having the same support (b), then e is orthogonal.
in the squared PC in time O(ccl) rather than O(d]²). However, the caveat is that taking the modulus square of a deterministic circuit can be done by simply replacing each weight and input function with their modulus square, resulting in PC with non-negative activations only (e.g., see the |wy]? in Eq. (3)). As such, real or complex parameters would not bring any expressiveness advantage over monotonic PCs, also noticed in Loconte et al. (2024, Prop. 4). This begs the question: How can we parameterize squared PCs to overcome their computational overhead without requiring determinism? Inspired by the simplification in Eq. (2), we introduce relaxation of determinism called orthogonality requiring sum units to receive input from units computing orthogonal functions.
Definition 5 (Orthogonality (or ortho-decomposablitt).... A smooth sum unit n with sc(n) = Z is orthogonal if all pairs of distinct inputs encode orthogonal functions, i.c., Vi, in(n), i # j: (dom(z) C (z) dz = 0. circuit is orthogonal all sum units it are orthogonal.
Unlike determinism, orthogonality does not necessarily require the inputs to sum units to have disjoint support. As we formalize in App. A.2, orthogonality strictly generalizes determinism the case of non-monotonic circuits. Similar to our discussion above leveraging determinism, given circuit that is orthogonal we have that computing the partition function its modulus square can done in time O(el) rather than ((c[?). We formalize this result in the following theorem.
Theorem 1.
Let e be smooth, decomposable and orthogonal circuit over X. Then computing the partition function Z (dom(X) [c(x)]² dx can be done in time O(cc).
We prove in App. A. where we also observe that, unlike determinism, orthogonality allows us to retain real complex parameters in the modeled distribution representation. To prove Thm. I we actually introduce generalization of orthogonality-cane called Z-orthogonality- thht considers sum units having scope overlapping with Z C X and allows to compute the more general quantity dam (Z) Jc(y, 2 dz in time ([c)), where y E dom(X Z). Moreover, as detailed in App. A.4, if circuit is (X) -orthogonal for all X
then is Z-orthogonal for any Z C X. Therefore, this other result also shows a condition to marginalize any subset Z of variables in time O([c).
Unlocking sestrracturedddccoopsaae
squared PCs. One aspect of Thm. is that, under orthogonality, computing the partition function requires linear time even for squared PCs that are not mouutureddddcomposabbeeel
This perhaps surprising, because integrating the power of non- circuit is in general #P-hard, see Vergari et al. (2021, Thm. 3.3). The key ingredient overcome marginalization being #P-hard exploiting cancellations provided by orthogonality to avoid integrating the product of non-compatible circuits, which would be otherwise intractable. To the best of our knowledge, TN structures corresponding to non-structured- decomposable circuits have not been previously investigated. E.g., MPS and TTNs implicitly encode a single hierarchical partitioning of the variables (Grasedyck, 2010), thus being structured- decomposable circuits (see App. B). Furthermore, theoretical results link structured structured-decompee decooposaabiiiy to decrease of expressiveness in circuits and squared PCs (Pipatsrisawat and Darwiche, 2008; 2010; de Colnet and Mengel, 2021; Loconte et al., 2025b). Although experiments particular class
deterministic and non
5

---

Published as a conference paper at ICLR 2026
of aatuuturredddecoopssaae squared PCs do not show an expressiveness increase ($6), these works motivate future research to develop novel expressive factorizations that are not structured- decomposable, yet their modulus squaring enable efficient marginalization via orthogonality.
3.1 How TO BUILD ORTHOGONAL CIRCUITS
Peharz et al. (2014) showed one can build a deterministic circuit by (i) choosing the input functions over the same variable such that they have disjoint supports, and (ii) ensuring each sum has inputs that are connected to different input functions the circuit graph. Each sum unit in deterministic circuit built in this way- way-also called regular selective- acts like decision node for the input functions it depends on w.r.t a variable. This construction can be done recursively (Lowd and Rooshenas, 2013; Shih and Ermon, 2020). To construct circuits that are orthogonal we can use similar approach, where each sum unit implicitly selects a subset of input functions that are however orthogonal rather than have non-overlapping supports. We start by formalizing the concept of a sum unit acting like decision node for the input functions it depends on, which we call basis decompoxabilitty
Definition 6 (Basis decomposability). A smooth sum unit is basis decomposable if the inputs to n depend on non-overlapping input functions for a variable, i.e., 3X E sc(n), Vi, E in(n), & j: Bx (i) n Bx (f) = 2, where (x) denotes the set of input functions over X in the sub-cireuit rooted in the unit i. A circuit is basis decomposable if every sum unit in it is basis decomposable.
By requiring basis decomposability and that the input functions over the same variable are orthogonal with each other, we recover the class of regular orthogonal circuits that are guaranteed to be orthogonal. We formally show this in App. A.3 and define regular orthogonality below.
Definition 7 (Regular orthogonality).. A smooth and decomposable eircuit over X is regular orthog- onal if (i) it is basis decomposable, and (ii) if all input units over the same variable X E X encode orthogonal functions, i.e., Vi,j input units over X, i # j. we have that f
ca (z))) dx =
Fig. 2 illustrates examples of regular selective and regular orthogonal circuits as basis decomposable circuits having the same computational graph but differing by their input functions. Furthermore, Apps. A.3 and A.4 also generalize regular orthogonality and present sufficient conditions for Z- orthogonality ($3) enabling linear-time marginalization.
However, regular orthogonality is rather restrictive as it requires each input sum unit depend on different input functions. Fig. 3a depicts this, where we assume that differently colored inner units depend on different input functions. Instead, circuits made of densely-connecter
layers of sums and products can have inputs to sum that share the same sets of input functions (see Fig. 3b). thus not being basis decomposable. This kind of circuits
(a)
(b)
Figure 3
include popular TN structures such as TTNs (Shi et al., 2006; Cheng et al., 2019) (see Fig. B. as
well as circuit architectures that benefit from GPU parallelism (Vergari et al., 2019; Peharz et al., 2020b;a; Liu and Van den Broeck, 2021; ; Mari et al., 2023; Loconte et al., 2025a; Zhang et al., 2025a). tensorized circhits-motivates us in finding different conditions relaxing basis decomposability, yet still useful to simplify the computation of marginals. We show how grouping computational units into layers enables to define such conditions. Similarly to a canonical form, these conditions are based on orthonormal input functions and (semi-)unite) matrices, and ensure squared PCs encode already-normalized distributions. However, our construction can be applied to circuits, even those that do not map to any known tensor factorization method.
These
FROM REGULAR ORTHOGONALITY TO UNITARITY
We introduce properties similar to regular orthogonality but instead defined over layers in order to fit tensorized circuit architectures that would otherwise not be basis decomposable due to their densely- connected structure. These properties guarantee that tensorized circuit is orthogonal and that the squared PC obtained from encodes an -ereald--rmmllzzed distribution, while also providing speed- ups for the computation of any marginal ($5). These perks generalize to tensorized circuit architectures that are not souuctreed-dcompossee compared to TTNs (as noticed for orthogonality in $3). We formalize tensorized circuits below.
thus representing a strictly larger set of factorizations when

---

Published as a conference paper at ICLR 2026
Definition 8 (Tensorized circuit (Loconte al., 2025a)). A tensorized circuit is parameterized computational graph encoding a function c(X) and comprising of three kinds of layers: imput, product and sum. A layer l is vector-valued function defined over variables sc(e) X. called scope, and every non-input layer receives the outputs of other layers as input, denoted as in(E). The scope of each non-input layer is the union of the scope of its inputs. The three kinds of layers are defined as:
Each input layer L has scope X X and computes collection of K input functions [fc: dom(X) + C) i.c., & outputs a K X-dimensional vector.
Each product layer & computes either an element-wise (or Hadamard) or Kronecker product of its N inputs, i.e., - (sc(L))) or @ L.
(sc(E))) respectively.
A sum layer l receiving input from { sill computes the matrix-vector product W. [e((sc(e))) (xvxss((x)))( where W E CRi and [+] is the concatenation operation.
As we illustrate in Figs. 4 and B. tensorized circuits can be seen as "syntactic sugar" for circuits (Def. 1) having dense connections between sparse groups of units. That is, a sum layer parameterized by W E CKiXKa consists of K₁ sum units each receiving K₂ inputs and parameterized by a row in W. Similarly, a product layer consists of scalar product units. Furthermore, we refer to the size of a layer as the total number of input connections to the units inside As detailed in App. A.5, there exists squaring algorithm for tensorized circuits operating on layers and using lincar algebra operations. This squaring algorithm extends another one described in Loconte et al. (2024) to support circuits whose sum layers can receive input from more than one layer (as in Def. 8).
Similar to regular orthogonality, we start by requiring that the input units over the same variable encode collection of orthonormal functions,
formalize below.
(U1) Each input layer & over a variable X encodes K orthonormal functions, i.e., ((X) (X) fx fx(()) (X)] such that Vi.j E [K] Jaom(x) ft(x) dr = dig. For any pair of input layers l; l over X and with & + lz. we have that Jdom(x) (xxx) @ (x)))) dr = 0.
App. C reviews possible choices for flexible orthonormal input functions. To relax basis decom- posability, the following property requires that sum layers receive input from layers depending on different input layers for at least one variable. E.g., the sum layer in Fig. 3b receives input from two other layers (with red and violet units), each depending on different input functions. Still, the sums in a sum layer receive input from units that share the input functions, thus not being basis decomposable in general (e.g., in Fig. 3b each sum receives input from two red/violet units).
(U2) Each sum layer l receives inputs from layers {4:) such that xx E sc(E), Vi,j E [N], i f j: the sub-circuits rooted in l, and l, dot not share input layers over the variable X.
In the particular case of a circuit where each layer consists of exactly one unit, (U2) is equivalent to basis decomposability. Finally, each sum layer has to be parameterized by (semi-)unita) matrix.
(U3) Each sum layer is parameterized by (semi- Juniiay matrix W E CKixka, K1 & K2, i.e., Wwt = Lk, or, equivalently, the rows of W are orthonormal.
If a tensorized circuit satisfies (U1-3) above, we say it is unitary. As formalized below and as we prove in App. A.6, by exploiting cancellations provided by the orthonormality of input functions and weights, the modulus squaring of a unitarity circuit encodes a normalized distribution.
Theorem 2. Let e be smooth and decomposable circuit over variables X. If is unitary, i.e., if
satisfies conditions (U1-3), then we have that e is orthogonal and Z = Saam(x) |c(x) dx = 1.
This is similar in spirit to Born machines obtained as the modulus square of a TTN in a convenient canonical
normalization by exploiting (semi-Junitary matrices. As detailed in App. B. our unitarity conditions strictly generalize such canonical form to more general tensorized circuits. This is because we can build unitary circuits that are not pruuctureddeccompsabbe i.c., whose structure encodes multiple hierarchical variables partitionings (see Fig. 4), yet their squaring encode a normalized distribution as for Thm. 2.
called upper- apper-canonical form (Cheng al.,
Expressiveness analysis. Since we introduced new families of circuits based on orthogonality and unitarity properties, in Apps. A.8 and A.9 we provide preliminary analysis regarding their expressive efficiency, i.c., the ability of circuit class encode function in a polysize computational graph. This contributes to a number of works investigating the expressiveness of circuits and squared PCs (Darwiche and Marquis, 2002; Martens and Medahalimi, 2014; de Colnet and Mengel, 2021; Glasser
7

---

Published as a conference paper at ICLR 2026
Figure 4: Tensorized circuits can encode custom hi- erarchical factorizations with no corresponding TTN. The shown circuit encodes factorization over X using mix of Hadamard and Kronecker product layers and two input layers per variable in X = (X1, X2, Xa), Unlike the TTN in Fig. B.I, this circuit is nol structured- decomposable since there are product units that fac- torize their scope X differently (pointed by arrows): ([Xa). (X1,X9 X2]] and ((X1,Xs) [X2]), as indi- cated with the color stripes, each corresponding to dependency w.r.t. a particular variable. Remarkably, this circuit does satisfy properties (U2) and (U4), as the pointed product layers that are input to the root sum layer do not share input layers.
s/a (ins)
siu (sta)
(2
(2(
(aas)))
et al., 2019; Loconte et al., 2025b). In App. A.8 we firstly show that enforcing orthogonality in a smooth and decomposable circuit is #P-hard, thus suggesting future work looking whether some functions encoded by smooth and decomposable circuits cannot be encoded by polysize orthogonal ones. We conjecture this to hold similarly to the case of deterministic circuits (Bova al., 2016). Instead, in App. A.9 we show that enforeing polytime, thus guaranteeing no loss in terms of expressive efficiency. Our experiments $6 confirm this, showing one can learn unitary squared PCs that perform similarly to non-unitary ones, while App. D.I shows that Fourier input functions are competitive w.r.t. Gaussians for density estimation.
weights in sum layers can be done in
A TIGHTER COMPLEXITY FOR VARIABLE MARGINALIZATION
As shown in Loconte et al. (2024) and discussed in App. A.S, computing any marginal probability in a PC obtained by taking the modulus square of a structured- degtuurddddccoopsaabbll and tensorized circuit c requires time ( S where L is the number of layers and Smux is upper-bound to the size of each layer in c. In fact, the marginalization a algorithm would (i) represent the modulus squaring of e as another decomposable circuit, thus quadratically increasing its size (LLSmux) and (ii) compute marginal with a single forward-pass over the squared PC. Here, we not only present an algorithm to compute any marginal that can be much more efficient, but we also show it generalizes to non- structured-dccomposbb squared PCs as well. We do so by exploiting the unitarity conditions (U1-3).
Our idea is that, when computing marginal probabilities scope depends on only the variables being integrated out, because they simplify to identity matrices (see proof of Thm. 2). We also observe that we do not need to square the whole tensorized circuit c, but only fraction of the layers depending on both the marginalized variables and the ones being left over. By doing so, a part of the complexity will ultimately depend on Smax rather than $ S However, in order to be able to marginalize any variable subset, requiring that the layers that are input to a sum layer have disjoint input functions dependencies w.r.t. all variables. As formalized below, we simply need to change "3X" to "VX" in (U2).
do not need to evaluate the layers whose
need to specialize (U2) in unitarity by
(U4) Each sum layer l receives inputs from layers { such that VX E sc(E), Vi,j E [N], * j: the sub-circuits rooted in l, and é, dot not share input layers over the variable X.
For instance, the can ignore the integration of all pairwise products between multiple inputs to a sum layer, as they annihilate thanks to orthogonality. This makes our complexity ultimately depend on (LL) rather than O(L²). Alg. A.3 presents our marginalization algorithm and, as we show in App. A.7, the following theorem guarantees it is correct also in the case non-structured tensorized circuits.
datructuredddecompolr
circuit in Fig. 4 satisfies (U4). Thanks (U4), we
Theorem 3. let e be a smooth and decomposable circuit over X that satisfies (U1-4), and let Z C X, Y X Z. Computing the marginal p(y) Saom z) jo(y, z) 12 dz requires time O(dy \ oz Smax JoY O oz 12xx) where dh is the set of layers whose scope depends on at least one variable in *.
Moreover, App. A.7 details why our algorithm has complexity O( \ (m in the best case. The relationship with TN canonical forms. To speed-up the computation of a certain marginal with Born machine, we firstly need to adapt the TN parameters into canonical form that is specific for
8

---

Published as a conference paper at ICLR 2026
MNIST
FashionMNIST
GPU memory (GiB)
time per iteration (ms)
0.1
0.2
0.3
0.4
0.5
test bpd
1.30
10
SGD
1 Hadamard
5
Adam
Kronecker
3.5
1.20
1111
# parameters
107
# parameters
10'
10
10
10"
(a) Memory and time per training step.
(b) Distribution estimation performances.
Figure 5: Squared unitary PCs scale better than squared PCs while retaining performance. By virtue of not materializing their squares as yet another circuit to compute the partition function Z, squared unitary PCs result in more efficient learning, even when using Kronecker product layers (a). This is, in practice, without any sacrifice in model performance, as we observe on the bits-per- dimension (bpd, lower is better) on image datasets (b). Remarkably, our parametrization allows efficiently training squared www.rcttredddecoompeeee
PCs (gray lines).
the chosen marginal (Vidal, 2003; Bonnevie and Schmidt, 2021). This comes with additional overhead depending on the number of variables and the TN shape. Instead, our marginalization algorithm does not require us to change the parameters depending on the marginal being computed, yet it provides a speed-up when compared to the naive approach that materializes squared PC as a decomposable one. Moreover, our algorithm generalizes over sasrruturredddccompsss represented unitary circuits, which otherwise would support tractable marginalization ($2).
factorizations when
6 EMPIRICAL EVALUATION
We now assess the practical benefits of using unitary squared PCs. We remark that our aim in this section is not to achieve state-of-the-as the- results, but rather answer the following research questions comparing squared PCs with and without our unitary parameterization. That is, we investigate whether unitary circuits result in faster and lighter squared PCs (RQ1); if we can learn unitary squared PCs without sacrificing model performance in distribution estimation tasks (RQ2); and whether can, for the first time, efficiently learn squared PCs that are not structured-decomposabbe (RQ3). All the details, hyperparameters and additional results can be found in App. D.
Experimental setting. Given a training dataset D on variables X, we aim at finding the parameters of given squared PC that maximize the data likelihood. We follow Loconte et al. (2024) and, given a batch B C D, write its negative log-like log-likelihood as == [B] log Z - -xxes' 2 log |c(x)], such that just need materialize the squared PC once per batch to compute the log-partinn log-partition function, significantly speeding up computations. For every circuit we use complex-vall -vauued parameters, identical architectures and batch sizes, and report results on a test dataset of the model with best validation performance during training. Similar to Loconte et al. (2024), we employ Hadamard product layers for the baseline squared PCs, denoted + while we use Kronecker product layers for the squared unitary PCs, -2, as we found them to perform significantly better in practice (see Apps. D.1 and D.2).
RQ1: Improved throughput. First, we measure to which extent squared unitary PCs improve the time and memory overhead of squared PCs that instead require computing Z explicitly during training. To this end, we build circuits with increasing number of units per layer and measure the time and memory required to perform one optimization step. Fig. 5a and Tab. D.3 show that squared unitary PCs are consistently faster to evaluate and use less memory. This becomes especially clear at large scales where squared unitary PC with Kronecker product layers and 357 M parameters takes 12 GiB of GPU memory and 0.29 ms per iteration, against the 18 GiB and 0.52 ms of its counterpart with Hadamard layers. Hence, unitary circuits enable learning squared PCs with Kronecker layers at scale, which is remarkable given that materializing the squared PCs as a decomposable one to compute Z would further increase the Kronecker layer sizes dramatically (details in App. A.5).
RQ2: Learning unitary circuits. Next, we learn squared PCs for distribution estimation on MNIST (LeCun et al., 2010) and FashionMNIST (Xiao et al., 2017) images. We choose these benchmarks on distribution estimation over images because it is arguably the most common evaluation

---

Published as a conference paper at ICLR 2026
setting appearing in the probabilistic circuits community (Liu et al., 2023; Gala al., 2024b; Garg et al., 2025). In addition, due to the high-dimensionalinn of the data these benchmarks allow us to scale PCs up to IB of parameters, hence making optimizing over the Stiefel manifold particularly challenging. Nevertheless, Fig. 5b shows the biss-pe-dimension of squared PCs of increasing sizes on both datasets, where we can observe that squared unitary PCs gracefully scale, matching the performance of their baseline counterparts. To this end, we adapted the LandingSGD optimizer (Ablin and Peyré, 2022; Ablin al., 2024) to our setting, which we describe in App. E and can be of independent interest to the community. We stress that this is remarkable, since orthogonally- constrained optimization is notoriously challenging and in active development (Ablin al., 2024; Kochurov et al., 2020; Lezcano Casado, 2019) and therefore, further advancements in the field can only benefit squared unitary PCs.
RQ3: Non-struucuuedd-deoom -ecomposabbe squared unitary PCs. Lastly, we reuse the previous setup and learn a squared unitary PC whose architecture is not sruuctured-decompossee alizing its square as decomposable circuit to compute Z explicitly is generally not tractable (Vergari et al., 2021; Zhang et al., 2025b). We detail our construction of a www.strucuuueddecooosssssss in App. D.2. As discussed in $3, this circuit architecture differs substantially from MPS and TTNs fac- torizations, as they correspond to structured -ewoorrodddcoooabblllll circuits. Fig. 5b shows that such PCs can be competitive with their drnctured-decoompssaa be harder to learn Thus, our theory and preliminary experiments open future interesting venues to de- sign and learn better ssrrucuueed-dccoppsiii PCs and TNs, which can be exponentially more ex- pressive than structured ones (Pipatsrisawat and Darwiche, 2008; 2010; de Colnet and Mengel, 2021).
and hence materi-
circuit
counterparts, especially at large scales, but might
CONCLUSION AND FUTURE WORK
Inspired by determinism in circuits and canonical forms in TNs, we introduced novel conditions described the circuit framework to simplify the computation marginals in squared PCs and ensure they encode already- normalized distributions. As for the close connection between circuits and TNs, our conditions motivate research aimed at exploring new factorization structures that can be more expressive, yet enabling exact and efficient marginalization and sampling. Recently, determinism has been generalized as a property between two circuits in Wang et al. (2024) to bring complexity simplifications for exact causal inference and weighted model counting (Chavira and Darwiche, 2008). We believe one can extend our orthogonality ($3) as a property between two circuits similarly, thus possibly simplifying the computation of compositional operations while being less restrictive than determinism. Finally, as we detail in App. C, there are number of directions aimed at understanding the relative expressiveness of the proposed circuit families w.r.t. other classes of PCs, e.g., the recent positive unital circuits generalizing squared PCs shown in Zuidberg Dos Martires (2025).
REPRODUCIBILITY STATEMENT
To ensure reproducibility, we release our code and necessary scripts here. The repository contains the models implementation, scripts for the experiments and results, and instructions for setting up the environment. Furthermore, a detailed description of all experimental settings is included in App. D.
ACKNOWLEDGMENTT
We acknowledge Raul Garcia-Patron Sanchez for meaningful discussions about tensor networks and quantum circuits. AV and AJ are supported by the "UNREAL: Unified Reasoning Layer for Trustworthy ML" project (EP/Y023838/1) selected by the ERC and funded by UKRI EPSRC.
CONTRIBUTIONS
LL. and AV conceived the initial idea of the paper. LL is responsible for all theoretical contributions, circuit illustrations, and algorithms related to the proofs in App. A. LL and AJ are responsible for the implementation. AJ developed the LandingPC algorithm, run the experiments and plotted the results. LL led the writing, with the exception the experimental section led by AJ, and all authors provided feedback about the paper. AV supervised all phases of the project.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Pierre Ablin and Gabriel Peyré. Fast and accurate optimization on the orthogonal manifold without retraction. In International Conference on Artificial Intelligence and Statistics, pages 5636-5657. PMLR, 2022.
Pierre Ablin, Simon Vary, Bin Gao, and Pierre-Antoine Absil. Infeasible deterministic, stochastic, and iriancc-reduction algorithms for optimization under orthogonality constraints. Journal of Machine Learning Research, 25(389):1-38) 2024.
Milton Abramowitz, Irene A. Stegun, and David Miller. Handbook of mathematical functions with formulas, graphs and mathematical tables (national bureau of standards applied mathematics series no. 55). Journal of Applied Mechanics, 02:239-239, 1965.
Pierre-Antoine Absil, Robert E. Mahony, and Rodolphe Sepulchre. Optimization Algorithms Matrix Manifolds. Princeton University Press, 2007.
Sanyam Agarwal and Markus Bläser. Probabilistic generating circuits demystified. In 41st International Conference Machine Learning (ICML), 2024.
Kareem Ahmed, Stefano Teso, Kai-Wei Chang, Guy Van den Broeck, and Antonio Vergari. Semantic probabilistic layers for neuro-symbolic learning. In Advances in Neural Information Processing Systems 35 (NeurIPS), volume 35, pages 29944 299559. Curran Associates, Inc., 2022.
Martín Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks. In International Conference Machine Learning, 2015.
Nitin Bansal, Xiaohan Chen, and Zhangyang Wang. Can we gain more from orthogonality regu- larizations training deep networks? In Advances in Neural Information Processing Systems, volume 31, 2018.
Jacob D. Biamonte and Ville Bergholm. Tensor networks in nutshell. arXiv: Quantum Physics, 2017.
Rasmus Bonnevie and Mikkel N. Schmidt. Matrix product states for inference in discrete probabilistic models. Journal of Machine Learning Research, 22:18 22:187:1-187:48 2021.
Simone Bova, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky. Knowledge compilation meets communication complexity, In International Joint Conference on Artificial Intelligence, 2016.
Diana Cai, Chirag Modi, Charles Margossian, Robert M. Gower, David Blei, and Lawrence K. Saul. VIgenVI: score- based variational inference with orthogonal function expansions. In The Thirry- eighth Annual Conference on Neural Information Processing Systems (NeurIPS), 2024.
J. Douglas Carroll and Jih-Jie Chang. Analysis of individual differences in multidimensional scaling via an n-way generalization of "eckart-young" decomposition. Psychometrika, 35:283-319, 1970.
Mark Chavira and Adnan Darwiche. On probabilistic inference by weighted model counting. Artificial Intelligence, (77677):7727799 2008
Song Cheng, Lei Wang. Tao Xiang, and Pan Zhang. Tree tensor networks for generative modeling. Physical Review B, 15(15))15111,, 2019.
YooJung Choi, Meihua Dang, and Guy Van den Broeck. Group faimess by probabilistic modeling with latent fair decisions. In AAAI Conference on Artificial Intelligence, 2020a.
YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic modeling. Technical report, University of California, Los Angeles (UCLA), 2020b.
Adnan Darwiche. A differential approach to inference in bayesian networks. Journal of the ACM (JACM), 50:280-305, 2003.
Adnan Darwiche. Modeling and Reasoning with Bayesian Networks. Cambridge University Press, 2009.
11

---

Published as a conference paper at ICLR 2026
Adnan Darwiche and Pierre Marquis. A knowledge compilation map. Journal of Artificial Intelligence Research (JAIR), 17:229-2666 264,, 2002.
Adnan Darwiche and Gregory M. Provan. Query dags: A practical paradigm for implementing belief- network inference. In UAI, pages 203 203-210. Morgan Kaufmann, 1996.
Alexis de Colnet and Stefan Mengel. A compilation of succinetness results for arithmetic circuits. In 18th International Conference on Principles of Knowledge Representation and Reasoning (KR), pages 205-215, 2021.
Aaron W. Dennis. Algorithms for Learning the Structure of Monotone and Nonmonotone Sum- Product Networks, PhD thesis, Brigham Young University, 2016.
Aaron W. Dennis and Dan Ventura. Learning the architecture of sum-product networks using clustering on variables. In Advances Neural Information Processing Systems 25 (NeurIPS). pages 2033-2041. Curran Associates, Inc., 2012.
Paul Adrien Maurice Dirac. The Principles of Quantum Mechanics. Clarendon Press, Oxford,, 1930.
Johannes Exenberger, Sascha Ranftl, and Robert Peharz. Deep polynomial chaos expansion. In 8th Workshop on Tractable Probabilistic Modeling, 2025.
Gennaro Gala, Cassio de Campos, Robert Peharz, Antonio Vergari, and Erik Quaeghebeur. Proba- bilistic integral circuits. In AISTATS 2024, 2024a.
Gennaro Gala, Cassio de Campos, Antonio Vergari, and Erik Quaeghebeur. Scaling continuous latent variable models as probabilistic integral circuits. arXiv preprint arXiv:2406.. 06494, 2024b.
Poorva Garg, Benjie Wang, Oliver Broadrick, Guy Van den Broeck, and Todd Millstein. Bitblasting for tractable constrained decorrelation in image modeling. In Eighth Workshop on Tractable Probabilistic Modeling (TPM), 2025.
Ivan Glasser, Nicola Pancotti, and J. Ignacio Cirac. From probabilistic graphical models to generalized tensor networks for supervised learning. IEEE Access, 8:68169-68182 2018.
Ivan Glasser, Ryan Sweke, Nicola Pancotti, Jens Eisert, and Ignacio Cirac. Expressive power of tensor-network factorizations for probabilistic modeling. In Advances in Neural Information Processing Systems 32 (NeurIPS), pages 1498-1510. Curran Associates, Inc., 2019.
Lars Grasedyck. Hierarchical singular value decomposition of tensors. SIAM journal on matrix analysis and applications, 31 31))):202- 2010.
Zhao-Ya Yu Han, Jun Wang, Heng Fan, Lei Wang, and Pan Zhang. Unsupervised generative modeling using matrix product states. Physical Review 8:031012, Jul 2018.
Richard A. Harshman. Foundations of the parafac procedure: Models and conditions for an "explana- tory" multi-model factor analysis. In UCLA Working Papers in Phonetics, volume 16, pages 1-84, 1970.
Juha Harviainen, Vaidyanathan Peruvemba Ramaswamy, and Mikko Koivisto. On inference and learning with probabilistic generating circuits. In Conference on Uncertainty in Artificial Intelli- gence (UAI), 2023.
Markus Hauru, Martin Van Damme, and Jutho Haegeman. Riemannian optimization of isometric tensor networks. SciPost Physics, 2020.
Lei Huang, Xianglong Liu, Bo Lang. Adams Wei Yu, and Bo Li. Orthogonal weight normalization: Solution to optimization over multiple dependent stiefel manifolds in deep neural networks. In AAAI Conference Artificial Intelligence, 2017.
Dunham Jackson. The Theory of Approximation, volume 11. Colloquium Publications, 1930. doi: hups://doi.org/100 0..g//./////// 10100///////////111.....1
Dunham Jackson. Fourier Series and Orthogonal Polynomials, volume 6. Carus Mathematical Monographs, 1941. doi: https//bbbinyil0333xxXx00744444
12

---

Published as a conference paper at ICLR 2026
Pasha Khosravi, YooJung Choi, Yitao Liang, Antonio Vergari, and Guy Van den Broeck. On tractable computation of expected predictions. In Advances in Neural Information Processing Systems 32 (NeurIPS), 2019.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations (ICLR), 2015.
Doga Gizem Kisa, Guy Van den Broeck, Arthur Choi, and Adnan Darwiche. Probabilistic sentential decision diagrams. In International Conference Principles of Knowledge Representation and Reasoning, 2014.
Ching Yun Ko, Cong Chen, Zhuolun He, Yuke Zhang, Kim Batselier, and Ngai Wong. Deep model compression and inference speedup of sum-product networks tensor trains. IEEE Transactions on Neural Networks and Learning Systems, 31 (7)::6665-2677 2020.
Max Kochurov, Rasul Karimov, and Serge Kozlukov. Geoopt: Riemannian optimization in pytorch. arXiv preprini arXiv:2005.02819 2020.
Tamara G. Kolda. Multilinear operators for higher-order decompositions. Technical report, Sandia National Laboratories, 2006.
Tamara G Kolda and Brett W Bader. Tensor decompositions and applications. SIAM review, 51(3): 455-500, 2009.
Daphne. Koller and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques. Adaptive computation and machine learning. MIT Press, 2009.
Sebastian Krämer. Tree tensor networks, associated singular values and high-dimensional approxi- mation. PhD thesis, 2020.
Alex Kulesza and Ben Taskar. Determinantal point processes for machine learning. ArXiv, abs/1207.60$$ 600007.6683.200 2012.
Leander Kurscheidt, Paolo Morettin, Roberto Sebastiani, Andrea Passerini, and Antonio Vergari. probabilistic neuro-symbolic layer for algebraic constraint satisfaction. In Uncertainty in Artificial Intelligence (UAI), 2025.
Yann LeCun, Corinna Cortes, and Burges. MNIST handwritten digit database. ATT Labs [Online]. 2, 2010.
Available: http::/yann.lecue
Mario Lezcano Casado. Trivializations for gradient- optimization manifolds. Advances in Neural Information Processing Systems, 32, 2019.
Mario Lezcano- Caaado and David Martinez-Rubio. Cheap orthogonal constraints neural networks: A simple parametrization of the orthogonal and unitary group. In Proceedings of the 36th In- ternational Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 3794 3803. PMLR, 09-15 Jun 2019.
Selena Zihan Ling, Nicholas Sharp, and Alec Jacobson. VectorAdam for Rotation Equivariant Geometry Optimization. Advances in Neural Information Processing Systems, 2022.
Anji Liu and Guy Van den Broeck. Tractable regularization of probabilistic circuits. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 2021.
Curran Associates, Inc.,
Anji Liu, Stephan Mandt, and Guy Van den Broeck. Lossless compression with probabilistic circuits. In International Conference on Learning Representations, 2022.
Anji Liu, Honghua Zhang, and Guy Van den Brocck. Scaling up probabilistic circuits by latent variable distillation. In //th International Conference Learning Representations (ICLR), 2023.
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance the adaptive learning rate and beyond. arXiv preprint wXXv::908.00326. 2019.
13

---

Published as a conference paper at ICLR 2026
Shuangzhe Liu and Götz Trenkler. Hadamard, khatri-rao, kronecker and other matrix products. International Journal of Information & Systems Sciences, 4, 01 2008.
Lorenzo Loconte, Nicola Di Mauro, Robert Peharz, and Antonio Vergari. How to turn your knowledge graph embeddings into generative models via probabilistic circuits. In Advances in Neural Information Processing Systems 37 (NeurIPS). Curran Associates, Inc., 2023.
Lorenzo Loconte, M. Sladek Aleksanteri, Stefan Mengel, Martin Trapp, Arno Solin, Nicolas Gillis, and Antonio Vergari. Subtractive mixture models via squaring: Representation and learning, In The Twelfth International Conference on Learning Representations (ICLR), 2024.
Lorenzo Loconte, Antonio Mari, Gennaro Gala, Robert Peharz, Cassio de Campos, Erik Quaeghebeur, Gennaro Vessio, and Antonio Vergari. What the relationship between tensor factorizations and circuits (and how can we exploit it)? Transactions on Machine Learning Research, 2025a. ISSN 2835-8856. Featured Certification.
Lorenzo Loconte, Stefan Mengel, and Antonio Vergari. Sum of squares circuits. In The 39th Anmual AAAI Conference Artificial Intelligence (AAAI), 2025b.
Daniel Lowd and Amirmohammad Rooshenas, Learning markov networks with arithmetic circuits. In AISTATS, volume 31 of JMLR Workshop and Conference Proceedings, pages 406-414. JMLR.org. 2013.
Ilia A. Luchnikov, Alexander Ryzhov, Sergey N. Filippov, and Henni Ouerdane. Qgopt: Riemannian optimization for quantum technologies. SciPost Physics, 2021.
Jan R. Magnus and Heinz Neudecker. The commutation matrix: Some properties and applications. Annals of Statistics, 7:381-394, 1979.
Emanuele Marconato, Samuele Bortolotti, Emile van Krieken, Antonio Vergari, Andrea Passerini, and Stefano Teso. Bears make neuro-symbolic models aware of their reasoning shortcuts. In Uncertainty in Artificial Intelligence (UAT), 2024a.
Emanuele Marconato, Stefano Teso, Antonio Vergari, and Andrea Passerini. Not all neuro-symbolic concepts are created equal: Analysis and mitigation of reasoning shortcuts. Advances in Neural Information Processing Systems, 36, 2024b.
Antonio Mari, Gennaro Vessio, and Antonio Vergari. Unifying and understanding overparameter- ized circuit representations via low-rank tensor decompositions. In 6th Workshop on Tractable Probabilistic Modeling, 2023.
Igor L. Markov and Yaoyun Shi. Simulating quantum computation by contracting tensor networks.
SIAM Journal on Computing, 38(3):963-98) 981, 2008
Ulysse Marteau- Ferey, Francis Bach, and Alessandro Rudi. Non-parametric models for non-negative functions. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 12816 12826, 2020.
James Martens and Venkatesh Medabalimi. On the expressive efficiency of sum product networks. arXiv preprint arXiv: 2014.
Alex Meiburg, Jing Chen, Jacob Miller, Raphaëlle Tihon, Guillaume Rabusseau, and Alejandro Perdomo-Ortiz. Generative learning of continuous data by tensor networks. SciPost Physics, 18: 096, 2025.
Alexios A Michailidis, Christian Fenton, and Martin Kiffner. Tensor train multiplication. arXiv preprint arXiv:2410.19747 2024.
Valentin Murg, Ors Legeza, Reinhard M. Noack, and F. Verstracte. Simulating strongly correlated quantum systems with tree tensor networks. Physical Review 82:205105, 2010.
Heinz Neudecker and Tom Wansbeek. Some results on commutation matrices, with statistical applications. Canadian Journal of Statisticy-rever Canadienne De Statistique, 11:221-231, 1983.
14

---

Published as a conference paper at ICLR 2026
Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantumn Information: 10th Anniversary Edition. Cambridge University Press, 2010. doi: 10.1077/C8097881111766..
Georgii S. Novikov, Maxim E. Panov, and Ivan V. Oseledets. Tensor-train density estimation. In 37th Conference on Uncertainty in Artificial Intelligence (UAI), volume 161 of Proceedings of Machine Learning Research, pages 1321-1331, PMLR, 2021.
Guy Van den Broeck Oliver Broadrick, Honghua Zhang. Polynomial semantics of tractable proba- bilistic circuits. In 40th Conference on Uncertainty Artificial Intelligence (UAI), 2024.
Román Orús. practical introduction to tensor networks: Matrix product states and projected entangled pair states. Annals of Physics, 349:117-158, 2013.
Román Orús and Guifré Vidal. Infinite time-evolving block decimation algorithm beyond unitary evolution. Physical Review B, 78, 2008
Ivan. V. Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing, 33:2295- 2317, 2011.
Robert Peharz, Robert Gens, and Pedro Domingos. Learning selective sum- cun-product networks. In ICML, 2014.
Robert Peharz, Sebastian Tschiatschek, Franz Pernkopf, and Pedro M. Domingos. On Theoretical Properties of Sum-Product Networks. In International Conference on Artificial Intelligence and Statistics, 2015.
Robert Peharz, Steven Lang, Antonio Vergari, Karl Stelzner, Alejandro Molina, Martin Trapp, Guy Van den Broeck, Kristian Kersting, and Zoubin Ghahramani. Einsum networks: Fast and scalable learning of tractable probabilistic circuits. International Conference on Machine Learning. pages 7563-7574. PMLR, 2020a.
Robert Peharz, Antonio Vergari, Karl Stelzner, Alejandro Molina, Xiaoting Shao, Martin Trapp. Kristian Kersting, and Zoubin Ghahramani. Random sum- producc networks: A simple and effective approach to probabilistic deep learning. 35th Conference on Uncertainty in Artificial Intelligence (UAI), volume 115 of Proceedings of Machine Learning Research, pages 334-344, PMLR, 2020b.
Roger Penrose. Applications of negative dimensional tensors. Combinatorial Mathematics and its Applications, 1:221 1444, 1971.
David Pérez-Gareia F. Verstraete, Michael M. Wolf, and Juan Ignacio Cirac. Matrix product state representations. Quantum Information and Computing, 7(5):401-430, 2007. ISSN 1533-7146.
Aluisio Pinheiro and Brani Vidakovie. Estimating the square root of density via compactly supported wavelets. Computational Statistics and Data Analysis, 25(4):399 1997.
Knot Pipatsrisawat and Adnan Darwiche. New compilation languages based structured decompos- ability. In 23rd Conference on Artificial Intelligence (AAAI), volume 8, pages 517-522, 2008
Thammanit Pipatsrisawat and Adnan Darwiche. A lower bound on the size of decomposable negation normal form. Proceedings of the AAAI Conference on Artificial Intelligence, 2010.
Hoifung Poon and Pedro Domingos. Sum-product networks: A new deep architecture. In IEEE International Conference Computer Vision Workshops (ICCV Workshops), pages 689-690. IEEE, 2011.
Steven M Roman and Gian-Carlo Rota. The umbral calculus. Advances in Mathematics, 27(2)955- 188, 1978.
Alessandro Rudi and Carlo Ciliberto. PSD representations for effective probability models. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 19411-19422. Curran Associates, Inc., 2021.
Ulrich Schollwoeck. The Annals of Physics, 326:96-192,, 2010.
renormalization group in the age of matrix product states.
15

---

Published as a conference paper at ICLR 2026
Philipp Seitz, Ismael Medina, Esther Cruz, Qunsheng Huang, and Christian B. Mendl. Simulating quantum circuits using tree tensor networks. Quantum, 7:964, 2022.
Xiaoting Shao, Alejandro Molina, Antonio Vergari, Karl Stelzner, Robert Peharz, Thomas Liebig, and Kristian Kersting. Conditional sum prod-prouut networks: Modular probabilistic circuits via gate functions. International Journal of Approximate Reasoning, 140:298-313, 2022.
Yaoyun Y. Shi, Luming M. Duan, and Guifré Vidal. Classical simulation of quantum many-body systems with a tree tensor network. Physical Review A, 74:22320, 2006.
Andy Shih and Stefano Ermon. Probabilistic circuits for variational inference in discrete graphical models. In Advances in Neural Information Processing Systems 33 (NeurIPS). Curran Associates, Inc., 2020.
Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Founddations and Trends Theoretical Computer Science, 5:207-388, 2010.
Aleksanteri Sladek, Martin Trapp, and Arno Solin, Encoding negative dependencies in probabilistic circuits. In 6th Workshop Tractable Probabilistic Modeling. 2023.
Winthrop W. Smith and Joanne M. Smith. Handbook of Real-Time Fast Fourier Transforms: Algo- rithms to Product Testing. Wiley IEEE Press, 1995.
Edwin Stoudenmire and David Schwab. Supervised learning with tensor networks. In Advances in Neural Information Processing Systems 29 (NeurIPS), pages 4799-4807. Curran Associates, Inc., 2016.
Zheng-Zhi Sun, Shi-Ju Ran, and Gang Su. Tangent-space gradient optimization of tensor network for machine learning. CoRR, abs/2001 104099, 2020.
The APRIL Lab. cirkit, 2025. URL https::///// /gttttttthbbg/ggg cow./prrr-tooossspppeoooooeo
Andrei Tomut, Saeed S. Jahromi, Sukhbinder Singh, Faysal Ishtiaq, Cesar Munoz, Prabdeep Singh Bajaj, Ali Elborady, Gianni del Bimbo, Mehrazin Alizadeh, David Montero, Pablo Martin-Ramiro, Muhammad Ibrahim, Oussama Tahiri-Alaou,, John Malcolm, Samuel Mugel, and Román Orús. Compactifai: Extreme compression of large language models using quantum-inspired tensor networks. ArXiv, htns/2401.141099 2024.
Derrick S. Tracy. Balanced partitioned matrices and their kronecker products. Computational Statistics & Data Analysis, 10:315-324 1990.
Derrick Tracy and K. G. Jinadasa. Partitioned kronecker products of matrices and applications. Canadian Journal of Statistics-revue Canadienne De Statistique, 17:107-120, 1989.
Derrick S. Tracy and Rana P. Singh. A matrix product and its applications in partitioned matrix differentiation. Statistica Neerlandica, 26: 26: 143-177, 1972.
Russell Tsuchida, Cheng Soon Ong, and Dino Sejdinovie. Squared neural families: A new class of tractable density models. In Thirth-seventh Conference on Neural Information Processing Systems (NeurIPS), 2023.
Russell Tsuchida, Cheng Soon Ong, and Dino Sejdinovic. Exact, fast and expressive poisson point processes via squared neural families. In Proceedings of the AAAI Conference Artificial Intelligence, pages 20559-20566. AAAI Press, 2024.
Russell Tsuchida, Jiawei Liu, Cheng Soon Ong, and Dino Sejdinovic. Squared families: Searching beyond regular probability models. CoRR, abs/2503.21 128, 2025.
Leslie G. Valiant. Negation can be exponentially powerful. In 11th Arnual ACM Symposium on Theory of Computing, pages 189-196. 1979.
Antonio Vergari, Nicola Di Mauro, and Floriana Esposito. Visualizing and understanding sum- product networks. Machine Learning, 108(4):551-57, 2019.
16

---

Published as a conference paper at ICLR 2026
Antonio Vergari, YooJung Choi, Anji Liu, Stefano Teso, and Guy Van den Broeck. A compositional atlas of tractable circuit operations for probabilistic inference. In Advances Neural Information Processing Systems 34 (NeurIPS), pages 1119-13201. Curran Associates, Inc., 2021.
Guifré Vidal. Efficient classical simulation of slightly entangled quantum computations. Physical Review Letters, 91:147902. Oct 2003.
Benjie Wang and Guy Van den Broeck. On the relationship between monotone and squared proba- bilistic circuits. In The 39th Annual AAAI Conference on Artificial Intelligence (AAAI), 2025.
Benjie Wang, Denis Mauá, Guy Van den Broeck, and YooJung Choi. A compositional atlas for algebraic circuits. In The Thirty-eighth Annual Conference Neural Information Processing Systems (NeurIPS), 2024.
Norbert Wiener. The homogeneous chaos. American Journal of Mathematiics, 60(4):897-936, 1938.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion- -MNIST: a Novel Image Dataset for Bench- marking Machine Learning Algorithms. ArXiv, abs/ 708. 07747, 2017.
Yibo Yang. Stephan Mandt, and Lucas Theis. An introduction to neural data compression. Founda- fions and Trends in Computer Graphics and Vision, 15:113-200 2022.
Zhongjie Yu, Martin Trapp, and Kristian Kersting. Characteristic circuits. In Advances in Neural Information Processing Systems 36 (NeurIPS), 2023.
Lena Zellinger, Nicola Branchini, Lennert De Smet, Victor Elvira, Nikolay Malkin, and Antonio Vergari. How to approximate inference with subtractive mixture models. The 29th International Conference on Artificial Intelligence and Statistics, 2026.
Honghua Zhang, Steven Holtzen, and Guy Van den Broeck. On the relationship between probabilistic circuits and determinantal point processes. In Conference on Uncertainty in Artificial Intelligence, 2020.
Honghua Zhang, Brendan Juba, and Guy Van den Broeck. Probabilistic generating circuits. In International Conference on Machine Learning, pages 12447-12457. PMLR, 2021.
Honghua Zhang, Meihua Dang, Benjie Wang, Stefano Ermon, Nanyun Peng, and Guy Van den Broeck. Scaling probabilistic circuits via monarch matrices. Pruceedings of the 42th International Conference on Machine Leurning (ICML), 2025a.
Honghua Zhang, Benjie Wang, Marcelo Arenas, and Guy Van den Broeck. Restructuring tractable probabilistic circuits. In Proceedings of the 28th International Conference on Artificial Intelligence and Statistics (AISTATS), 2025b.
Qibin Zhao, Guoxu Zhou, Shengli Xie, Liqing Zhang, and Andrzej Cichocki. Tensor ring decomposi- tion. CoRR, abss/600..0m 666.05535, 2016.
Pedro Zuidberg Dos Martires. A quantum information theoretic approach to tractable probabilistic models. In Uncertainty in Artificial Intelligence (UAI), 2025.
17

---

Published as a conference paper at ICLR 2026
Appendix
Table of Contents
A Proofs
19
A.1 Linear-time Partition Function and Marginals Computation via Orthogonality
19
A.2 Orthogonality Strictly Generalizes Determinism
21
A.3 Regular Orthogonality is Sufficient for Orthogonality
21
A.4
Marginalizing Any Variables Suhset in Linear Time
24
A.5
Tensorized Circuit Multiplication Algorithm
24
A.6 Alrcady-Normalized Tensorized Squared Circuits via Unitarity
28
A Tighter Marginalization Complexity
A.8 Enforcing Orthogonality is #P-hard
32
A.9 Enforcing
Parameters is Efficient
33
B Tree Tensor Networks as Structuredddecompossbbee Circuits
36
B.I Unitary Circuits Generalize Upper Canonical Tree Tensor Networks
38
Related Work
D Experimental Details
41
D.1 Continuous Input Features
41
D.2 Image Distribution Estimation
42
D.3
Benchmarking Squared PCs.
44
E The Family Landing Algorithms
45
18

---

Published as a conference paper at ICLR 2026
A PROOFS
Assumptions, Below we implicitly make the following mild assumptions. We require each inner unit compute
function its support. We also assume that the functions computed by input units can be evaluated and integrated over their support efficiently. With a slight abuse of notation, we use integrals to actually denote summations if taken w.r.t. discrete variables.
A.1 LINEAR-TIME PARTITION FUNCTION AND MARGINALS COMPUTATION VIA ORTHOGONALITY
In order to prove that computing the partition function of a squared PC, obtained by taking the modulus square of an orthogonal circuit e (Def. 5), requires time ([c)) (i.e., our Thm. 1), here we firstly introduce generalization of orthogonality. This other condition, which call Z-othogonnality, considers only sum units having scope overlapping with Z and requires the inputs to sum units to encode orthogonal functions when variables that are in the variables set Z are kept fixed. We formalize Z- z-othhogonality below.
Definition A.1 (Z-orthogonality). A smooth sum unit is Z-orthogonal, with Ž = sc(n) n Z * Ø, if all pairs of its inputs encode orthogonal functions when fixing the variables in sc(n) 2. i.e., j E in(m). í * j: Jdom (2) cy (y) (y, 2)* dă = 0, for any y E dom(sc(m) 2). Moreover, we say a circuit over variables X is Z-rrthogonal, with Z S X, if all sum units having scope overlapping with Z are Z-orthogonal.
Under the satisfaction of Zootthogonality in c, the following lemma shows that computing the quantity (dom(z) (Z) (cyy, 2 dz can done in time O[cl)), where y E dom(X \ Z).. In particular, we show the correctness and complexity of our Alg. A.1 to compute this quantity. We will later show that, by setting Z X, one recovers Thm. 1, i.e., computing the partition function Z = fdom(x) le(x)]² dx can be done in time ((e)).
Lemma A.1. Let be a smooth, decomposable and Z-orthogonal circuit over variables X. Then computing [dom(z) |e(y, z)|² dz can be done in time ((cc)), where y E dom(X Z).
Proof. We prove it by showing the correctness of Alg. A.l via induction on the structure of
Units having scope not overlapping with Z. Let n be a unit in c. In the case of sc(n) nz = Ø. we have that we can compute Ic,, [5) for some assignments ý obtained from y by restriction over variables in sc(n), in time ([c)). This is because we can evaluate en by doing feed-forward evaluation of the sub-cireuit rooted in c, and then take the modulus square of the result. This case as formalized in L1-3 in Alg, A.I.
Sum units. Let n be sum unit in such that Ż sc(n) n Z + Ø, i.e., the variables scope of n overlaps with Z. Thus, assume that n computes c, cy, 2) Exein(n) (y 2), where
E dom(2) and y E dom (Y) with Y sc(n) \ 2. By hypothesis n is Z-orthogonal, and therefore we have that Vi.j E in(n), i + j: (2 cs (y,, 2),, (y, 2)r dž = 0. For this reason, we can write
Jomez (y, 22
Σ (Ein(n) jEin(n)
Σ
wn.wwhi
c,y, 2)c, (y, 2)) dž dom()))
|wn,s| 2
d2.
dom(2)
(Ein(n)
Thus, we can compute the integral of the modulus squaring n by firstly evaluating the integral of the modulus squaring of its inputs and then computing a weighted summation. This is L4-7 in Alg. A.1. By inductive hypothesis, computing the Saom(2) (cs(y, 2) dž in our algorithm requires time ((el) d2 also requires time O(cc). Furthermore, we observe
and therefore evaluating fdom(2) |c,, that if the sub-circuits respectively rooted in and j, with i, in(n), & j are not compatible (Def. 4), then computing the integral Jaomzz cy 2)c, (y, 2)* dă would be in general a #P-hard problem (Vergari al., 2021). In particular, would not be struttueed-decompsaablee eircuit.
19

---

Published as a conference paper at ICLR 2026
However, due to cancellations arising from Z-orthogonality, algorithm avoids the computation of these integrals as they cancels out, thus allowing us to efficiently marginalize variables in the case of baaruuctrreddccompsstteeee
squared PCs.
Product units. Let be product unit in such that Ž = sc(n) n Z + Ø and computing c, (y Iinin))) cy,,, 2.). Since i decomposable we have that (Z))iein(n) forms a partitioning of variables Z with 2; dom (Z,), and the assignment, y to Y is partitioned into assignments (y,)eein(n)- Thus, we can write
Dommco (y,ly, (,(y,2)12d22
2,)1 (Ein(n)
II
d21 d2(in()))
"xiiitn) Z.)
1o 2:)) 2
(Ein(n) domm
Thus, similar to the case of n being a sum unit above, we have that computing the integral of the modulus squaring translates to multiplying the integrals of the modulus squaring of their inputs. Note that with slight abuse of notation we allow Z, be possibly empty for some E in(n). This allows to recursively call Alg. A.1 to the inputs of thus yielding L8- 12 in it. Again, by inductive hypothesis we have that this case requires time O(cc).
Consider the base case where is input unit over X Z and computing f(X), i... (X) f(X). By assuming that the modulus squaring of f can be integrated efficiently, we have that computing /dom(x) Cn, (x:) dr is efficient. Therefore, since all the cases considered above take time O(cc)), we have that computing [aom(z) |oly, 1² dz with Alg. A. requires time ((cc)..
Algorithm A.1 MAR- ORTHO-DEC(C.y,.
Input: circuit over variables X that Z-orthogonal for some Z C X, and an assignment y to variables Y = X \ Z. We denote as n the output unit of Output: The value of dom(z)) Ic(y, 2) dz.
D does not depend on the variables to marginalize 2: let y be the restriction assignments y to variables in sc(n). FEEED-FORWRRD(((((O 4: return |r|2
I: sc(n) n Ø
3: r-c-
5: else n sum unit then
let n. receive input from units in(n) and parameterized by (Wa, Ivein()) (c((1)), Vi E in(n)
7: let:;; <- MMRR-ORTHO-DECf
8: return Eign(n)) |Wa,il 2
9:
else ru is a product unit then
10: let receive input from units in(n)
11: r. MAR-ORTHO-AA DEC(i, sc(())) Vi in(n)
12: return Ileinn Fz
13: else
14: let be input unit over variable X Z
return Samm(x) |on (x) da
b Assuming it can computed efficiently
From Lem. A.1 we are now able to prove Thm. 1, as formalized below.
Theorem 1. Let be a smooth, decomposable and orthogonal circuit over X. Then computing the partition function Z Jdom(x) |e(x)]2 dx be done in time O(cc).
Proof. Since e is orthogonal, then e is also Z-orthogonal with Z = X. This can be seen by noticing that sc(n) n Z sc(n) for any unit and with Z X. Therefore, from Lem. A.1 we have that computing 7 requires time O(cc) by using Alg. A.1.
Unlike determinism, orthogonality preserves complex parameters. Assume that a determin- istic (Def. 3) smooth sum unit computing en (X) Eigin(n) (X). Then, for any i,j E [n], i we have that (X)))((X) ( i and j have disjoint supports. Thus, can write
20

---

Published as a conference paper at ICLR 2026
Ic, Eiei((n) (e,,l/(c,(X)) For this reason, the modulus squaring of a deterministic cir- cuit with possibly complex parameters turns out to be equivalent to another deterministic and mono- tonic circuit. However, under orthogonality of n instead, we cannot rewrite |ca (X)] in the same way, because cancellations only occur when integrating variables out, and the inputs to can have overlapping support (e.g., see Fig. 2). For this reason, unlike determinism we observe that orthogo- nality retains the possibly real complex parameters in the distribution representation modeled as p(X) xx lc(X))², which is a crucial feature aiding the expressiveness of squared PCs over monotonic ones (Loconte et al., 2024: 2025b).
A.2 ORTHOGONALITY STRICTLY GENERALIZES DETERMINISM
In the following, we show that determinism is a sufficient but not a necessary condition for orthogo- nality in the case of circuits whose unit outputs be negative complex valued. In other words, orthogonality is a strict generalization of determinism in the case of non-monotonic circuits.
Proposition A.1. If circuit e is deterministic, then it is orthogonal. Under mild assumptions, the converse implication holds if is also monotonic.
Proof. (=> By determinism of e we have that, for any sum unit n having scope sc(n) = Z.
Vi,j E in(n), i + j: supp(i) supp(j) Ø. Therefore, we have that either e₂ c;(z) = 0 or C₁ (z)
for any i i and z E dom Z). Now, if c = 0 then c; (z) = O, and if (z) = C (z) = 0
then ((()))(())
O. Therefore, we have that V E in(n), o j: Sdam (2) (z(2) (2) dz =
ie., 12 is orthogonal. Therefore, we conclude that c is an orthogonal circuit.
( (f c is also monotonic, under mild assumptions) To show the converse direction, start by assuming that e is both orthogonal and monotonic, i.e., all input functions and sum unit weights in are positive. This means that every computational unit in e computes positive function over its support. Now, by orthogonality of we have that Vi,j E in(n), i * j: Jdom(z) ((2)c, (z)* dz = 0.
hold, recover that the inputs i and j to n, with / j. must have disjoint supports, i.e., n is deterministic. In other words, under monotonicity, the supports of i and j were overlapping, then e, and e, would not be in general orthogonal functions as their inner product would be non-zero. Therefore, the circuit c is deterministic. However, the case of continuous variables X, for this to hold we require an additional mild assumption over the supports of i and j. That is, we also need that the set supp(1) O supp(j) has non-zere measure. Otherwise, supp(i) n supp(j) being of zero measure but non-empty (e.g., finite set) would imply orthogonality of e; and ej yet they have overlapping supports (as the integral taken over a zero measure set is zero).
However, due monotonicity we have that (z) ey (z) and, for orthogonality
( (#,, if is non-monotonic) To prove that the converse direction does not hold in the more general case of non- monotonic circuits, we need to find a single non-monotonic circuit that is orthogonal yet non-deterministic. This circuit can be built as single sum unit that receives input from two real- valued orthogonal functions both having IR as support, e.g., Hermite functions (Roman and Rota, 1978).
In conclusion, orthogonality is a strict generalization of determinism in the case of non-monotonic circuits and, under mild assumptions regarding the measure of supports intersections, determinism and orthogonality become equivalent properties in the case of monotonic circuits.
A.3 REGULAR ORTHOGONALITY IS SUFFICIENT FOR ORTHOGONALITY
In this section, we prove that regular orthogonality (Def. 7) is sufficient for orthogonality to hold (Def. 5). For this purpose, here we firstly introduce a generalization of regular orthogonality, called Z-regular orthogonality, and then show it is sufficient for Z- Z-orthogonality By doing so, we present sufficient conditions based on the structure of parameterization of a circuit to marginalize a subset Z of variables in linear time w.r.t. the circuit size. We start by introducing the Z-basis decomposability property, which specializes basis decomposability (Def. 6) to only sum units having scope overlapping with Z. We start by formally introducing the concept of basis scope.
defined in Def. A.1.
21

---

Published as a conference paper at ICLR 2026
Definition A.2 (Basis scope). The basis scope of unit n for variable X E sc(n), denoted as Bx(n). is the set of imput unit functions over X that the unit n depends on, ie., found in the sub- circuit rooted in n.
Definition A.3 (Z-basis decomposability). A smooth sum unit is Z-basis decomposable, with sc(n) n Z + Ø, if the imputs to n depend on non-overlapiing basis scopes for a variable in Z, i.c., X E sc(n) n Z, Vi, in(n), i + Bx (i) n Bx (i) 2. A eircuit is Z-basis decomposable if every sum unit is Z-basis decomposable.
In the following, we use Z-basis decomposability to define the Z-regular orthogonal property.
Definition A.4 (Z-regular orthogonality). A smooth and decomposable circuit c over X is Z-regular orthogonal, with Z S X. if (i) is Z-basis decomposable, and (ii) if all input units over the same variable E Z encode orthogonal functions, i.e., Vi,j input units over X, + j, we have that (dom(x) (z))c((z)) dr O.
For instance, the circuit shown in Fig. 2 is (X2)-orthogonal) since the input functions over the same variable X2 are orthogonal and each sum unit having X₂ in their variables scope is {Xx2) } decomposable, i.e., it splits the input functions over X2 it depends on towards its inputs. Note that, given a circuit e over variables X. we observe that Z-basis decomposability decomposability (Def. 6) in the special case of Z X. Therefore, Z-regular orthogonality of in the special case Z = is equivalent to regular orthogonality as defined in Def. 7.
coincides with basis
We aim at showing that Z- Z-regular orthogonality is sufficient for Z-orthogonality (Lem. A.3), thus implying regular orthogonal is sufficient for orthogonality the special case X = (Thm. A. In order to show this result, firstly prove the following lemma, saying that the integral over variables S X of the product of two circuits C₁ C2 defined over annihilates (i.e., it is zero), whenever the input functions in 6₁ and 02 over the same variable X Z are orthogonal with each other.
Lemma A.2. Let C1. C2 be smooth and decomposable circuits over variables X. having nı. f2 as output units, respectively. Assume that, for some variable X E X, the input functions over X in ai and C2 orthogonal, i.e., 3X E X: Vf E (x(m), Vy Bx (m2): Jdom(x) (())g(x)* dx O.
Then, for any Z S X such that X E Z, we have that Jdom(z) C1 2),2))2(y, dz = 0, where y dXm Z))
Proof. For the proof we will write down the polynomial encoded by a circuit, also called the circuit polynomial (Choi al., 2020b), whose construction relies on the idea of induced sub-circuit of unit.
Definition A.5 (Induced sub-cireuit (Choi et al., 2020b)). Let be circuit over variables X. An induced sub-circuit Ç is circuit constructed from as follows. The output unit in c is also the output unit of Ç. If n product unit in Ç then every unit E in(n). i.e., with a connection from to is in Ç. If is sum unit in Ç. then exactly one of its input unit i in(n) is in Ç.
Note that each input unit in an induced sub-cireuit Ç of a circuit is also input unit in By "unrolling" the representation of с as the sum of the collection of all its induced sub-circuits, we have that the function computed by can be written as the circuit polynomial below (Shpilka and Yehudayoff, 2010; Choi et al., 2020b):
c(x)
Σ
II
II nEZIC)
(n(sc(n))
CEH(C)
(EE())
where H(c) is the set of all induced sub-cireuits of c, O(C) is the set of all sum unit weights covered by the induced sub-circuit Ç. I({) is the set of all input units in Ç and x(n, {) is positive integer denoting how many times the input unit E I(C) is reachable in from the output unit of Ç. For brevity, we will denote the coefficients of the polynomial in Eq. (4) as w(() = IIweo()) w.
In the particular case c being smooth and decomposable, we observe that also Ç must be from the construction of an induced sub-cireuit. Therefore. under smoothness and decomposability, we have that each input unit in I(C) can be reached from the output unit in Ç exactly one time, i.c., s(n, <) = 1 for any n E I(C) and for any Ç E H(). Thanks smoothness and decomposability, also recover
22

---

Published as a conference paper at ICLR 2026
that each imput unit in I() is defined over different variable in X. With these observations, rewrite Eq. (4) as follows
c()
Σ w(() II fxx((),
(EH(C)
XeX
where each fc,x is the function computed by the only imput unit in over the variable X e X, i.e.
En E sc(), = { cn = (X)
Now, given C1. 02 circuits per hypothesis, from Eq. (5) write their circuit polynomials as
Ci (x) = Σ ((() II (x) and 02 (2(x) = Σ w((2)
II xca (X). (6) (EHH(()) XEX
(IEH(()
XEX
By hypothesis, we have that EX E X such that bf E Bx(m)), Vg E (x (dam(x) f(r)g(x)* dæ = O, where Ri, T2 respectively denote the output units of c1, c2. Since the input functions of any induced sub-circuit of circuit always also input units of i.e., fa. E Bx(nn), 9 (n2) for any X E X and for any Ç1 E H(c1). S2 E H(e2), we have that the following statement holds.
/ (x)x(())6.. (x) ( dr = =0
XE E EX E H(a)..Ga E H((2)):
dom(X)
In other words, for at least one variable X X, we have that the functions encoded by input units over X in any pair Ç1, S2 of induced sub-cireuits are orthogonal with each other. In the following, we exploit this observation annihilate the integral over the product of Cı and the conjugate of 02 over any variables Z C X such that X & Z. thus yielding the wanted result.
That is, by fixing y E Y dom X Z) and from the circuit polynomials in Eq. (6), write down the integral of the product of 6₁ and 02 w.r.t. to the variables in Z as follows
products of functions not depending on Z or X
J ())y2))2(y: 2)" dz Σ /oom()
Σ
(((1)
(s.. (yv)" veY
II
GiE((e)) (2EM((e2)
1smey f4, )9ca, v (za)" dzv
Vomncy fc, (Zx)) (xx)" dzx
VEZu(X) dom(V)
integrals of products of functiions depending on Z {X}
because Eq.
where we generally denote as the assignment to the variable V found in the assignments By plugging Eq. (7) into the formula above, we recover that the products annihilate, since the inner products of functions over X in S1 and in C2 are orthogonal. Therefore, this shows that (dom(z) C1 (y: 2)) 2)" dz =
By applying Lem. A.2, we prove in the following theorem that Z-regular orthogonality is a sufficient condition for Z-orthogonality. Then, in Thm. A. we prove that, when Z X, our Lem. A.3 (Def. 7) implies the sufficiency of regular orthogonality for orthogonality (Def. 5).
Lemma A.3 (Z-regular orthogonality over variables X, with Z C X. Then, is Z-orthogonal.
= Z-orthogonality). Let be Z-regular orthogonal circuit
Proof. By Z-regular orthogonality of e, we have that all input units in e over the same variable X E Z encode orthogonal functions. In addition, let be sum unit in c having scope overlapping with Z, i.e., Ż sc(n) Z * Ø, and let i,j E in(n) be any pair of inputs n such that i + From Z-regular orthogonality of we have that EX Z: Bx (i) (x Ø. By combining orthogonality of imput functions over X E Z and Z-basis decomposability of we recover that XX E 2, E (1),)) Vg E (x) faom())[(x)g(a f())g(x)* dx O. Now, under these results we can apply Lem. A.2 and obtain that 4; and ej orthogonal when fixing the variables not in Ż, i.c., (oom(2) cyy, 2)c, 2)" dž 0, where y dom dom (sc(n) 2). Thus, we recovered the wanted result, i.e. vi,j E in(n), i # j. 2aom(2) c, 2)c,(x (v, 2)" dž = 0. That is, every sum unit in having scope overlapping with Z is Z-orthogonal, i.e., is Z-orthogonal circuit.
23

---

Published as a conference paper at ICLR 2026
Theorem A.1. Let be regular orthogonal circuit over variables X. Then, c orthogonal.
Proof. Regular orthogonality in e translates to Z-regular orthogonality in e with Z X. Therefore, from Lem. A.3 we have that is X-orthogonal and thus orthogonal.
A.4 MARGINALIZING ANY VARIABLES SUBSET IN LINEAR TIME
Under Z-orthogonality. Lem. A.1 ensures that computing the particular marginal quantity Jdam(2) 2 dz requires time O[cc).. As we formalize in the following lemma, if a circuit is {X) ) Jorthogoonl for all variables X E X, then it is Z-orthogonal for all Z X. thus allowing to compute any marginal in time ([(cl) by using our Alg. A.I. We will use this lemma later in Thm. A.2 to formalize sufficient conditions based regular orthogonality (see App. A.3), i... based on the circuit structure and parameterization, to marginalize any variables subset in linear time.
Lemma A.4. Let e be a circuit over variables X that is {X Jorthhoggon for all X e X. Then e is Z-orthogonal for all Z C X.
Proof. To prove this, we need show that if every sum unit in is -orthhogonn for all X E sc(n), then n is Z-orthogonal for all Z C sc(n). Let n be a sum unit in e having scope sc(n). By {X] -othhoogggyyllyty of for all X E X, have that the inputs to n encode orthogonal functions whenever we fix the variables in sc VX E sc(n), Vi,j in(n), * j: fdom(x) c z)e, (v, x)" dæ
{X} for all X E sc(n). Formally, we have that
for any y E dom(sc(n) \X). (X), for i,j E in(n)
Now, consider a subset S sc(n). Therefore, given any E Z, 2 with i * j we can write
- c(y,2)e, dz = /ammz)) (Lom))) c, 2, 2 (v,,,, x) dæ dē - 0,
dom( Z))
since the inner integral over X is equal to zero for any variables assignments y and 2, as is (X}- orthogonal. Therefore, we recover that n. is Z-orthogonal for all C sc((n..
We then use the above lemma to formalize the result saying that if a circuit is {X] [X)-rege p-regular orthogonal w.r.t. all variables (see Def. A.4), then it enables the computation of any marginal in linear time.
Theorem A.2. Let be eircuit over variables X that is (-rrgaular orthogonal for all variables X E X. That is, for any sum unit n in e we have that its inputs depend on non-overlapping basis scopes for all variables, i.e., VX sc(n), Vi, E in(n), i # j: Bx(i) n (j( Ø: and all input units over the same variable encode orthogonal functions. Then computing Jdom(z) Ic(y, 2) dz for
any Z C X, with y dom(X Z) can be done in time ((d)).
Proof. Since e {X) }-rrgull orthogonal for all X E X, from Lem. A.3 we recover that e is (X)- orthogonal for all X E X. Thus, we can apply Lem. A.4 to say that is also Z-orthogonal for all variables subsets of X. Therefore, by applying Lem, A.1 we conclude that computing any marginal can be done in time ((el) by using Alg, A.I.
A.5 TENSORIZED CIRCUIT MULTIPLICATION ALGORITHM
In the case of tensorized cireuits whose sum layers can only receive input from exactly one other layer, Loconte et al. (2024) already proposed circuit squaring algorithm operating on layers that only requires simple linear algebra operations. This assumption over sum layers is particularly convenient, as it ensures the that tensorized circuit is arruttueedddecompssall 2024), and therefore representing their squaring as yet another decomposable circuit is tractable (Vergari et al., 2021). In this section, we extend this squaring algorithm to circuits whose sum layers can receive input from more than one layer, as required by the tensorized circuit definition by Loconte et al. (2025a) and that report in Def. 8. This particular difference between Def. 8 and the circuit representation used in Loconte et al. (2024) allows us to build tensorized squared PCs that are not necessarily stracured-deccompssabbe Nevertheless, in $5 show conditions to enable
by construction (Loconte et al.,
24

---

circuit c is the Published as a conference paper at ICLR 2026
Algorithm A.2 MULTIPLY(CI,C))
Input: Tensorized and compatible circuits cı, 0g over variables X,, X₂ respectively, and having & l as output layers, respectively. Output: The output layer & of a circuit over variables X₁ U X2 such that 8(X, Ux2 & (X() @ (X2).
1: if sc(E1) (2)) = 2 then return & & &2
2: if tı. l2 are input layers then
3: Assume &1 (resp. E2) computes K₁ (resp. K2) functions over variable X
4: return An input layer computing K₃ K₂ functions l @ ly
5: i, and Ea are sum layers then
let & [E -. Liv,] and & [E2) ... L2
7: Assume W1 = [w WIN. IN. and W2 [221 ... W2N,]
8: Ei MULTIPLYY (22), Vi [N] Vj [Nz]
9:
return (W, & [e' ......... L.j L'1 Ng.
where X denotes the Tracy-Singes product (see proof of Prop. A.2)
11:
if and lg Hadamard product layers then
12:
Assume & = f1 C f12 and & l2 @ l2
13:
where the circuit in En (resp. Ei2) is compatible with the circuit E2 (resp. l22).
14:
E < MUULTIPL((I1,..
15:
Eg < MULIIPLY
16:
return Eg &
17:
if &1 and le are Kronecker product layers then
18:
Assume l lu l12 and & l21 822
19:
where the circuit in E1 (resp. E12) is compatible with the circuit l21 (resp, l22).
20:
E + MULTIPLY(&II,&a)
21:
& < MULTIPLY(212..2)
22:
return P (ei @ Eg) where permutation matrix (see proof of Prop. A.2).
tractable marginalization of any variables subset. Furthermore, here we trivially extend such squaring algorithm to tensorized circuits with complex parameters.
Preliminaries. Given a pruuctureddecoompsabbe and tensorized circuit c, we represent its modulus squaring as yet another decomposable and circuit. This can be done by multiplying e with its conjugate c* ($2). Note that the conjugate e* can be efficiently obtained from by taking the conjugate of the functions computed by the input layers and the conjugate of the sum layer weights (Yu et al., 2023). and
This procedure preserves the structural properties of c, thus e* also compatible with c. Thus, we can represent the product between and c* as yet another decomposable circuit in polytime (Vergari et al., 2021). 1). In the following, we present an algorithm, namely MULTIPLY (Alg. A.2), in order multiply two tensorized circuits that compatible another decomposable tensorized circuit. Therefore, the modulus squaring of a pructured-decoomposse result of (UC.).
Notation. To simplify the notation, note that from now on we typically remove the scopes of the layers from the argument of the layer evaluations, e.g., & (sc(E)) & l2 (=(()()2) Furthermore, for simplicity we will assume that the product layers in the tensorized circuits C1 C2 be multiplied are either Kronecker or Hadamard (i.e., no product between circuits with mixed Kronecker and Hadamard layers). This is without loss of generality, as one can always rewrite an Hadamard product as a Kronecker product followed by sum layer encoding a linear transformation via selection matrix that filters out the cross products (e.g., see Liu and Trenkler (2008, Lem. 1)).
éi < le mean {(sc(e)
Proposition A.2. Let C1, C2 be tensorized and compatible circuits over variables X,, X2 respectively. Then, there exists an algorithm constructing a smooth and decomposable circuit e over X, U such that c(x) ci (x) (2(x) for any dom(X, U X2). Moreover, the algorithm runs in time L2S. S2. where L1 (resp. L2) denotes the number of layers in Ci (resp. c1), and Sj,aa (resp. S2,max) denotes the maximum layer size in e₁ (resp. 62).
Proof. We prove the correctness of Alg. A.2 by structural induction. That is, given & and lg the output layers of two compatible circuits over variables X,, X2, respectively, we show that Alg. A.2 returns the output layer e of another tensorized circuit over variables X, U X2 such that l Lú 88 lz.
25

---

Published as a conference paper at ICLR 2026
To begin with, consider the where X, O X2 Ø. Then, construct & Kronecker product layer taking li. l2 as inputs. Moreover, if L1, lz are both input layers over the same construct another imput layer over X such that it computes all the pairwise products of the function computed by & and l2- That is, consider (x(X) = (X))))... [K, (X)]T and (x)
variable X, X₂ {X},
[g) (X) 9K, 9K,(X) (X)]², then f(X) (X) @ (x( ( .... (..-f((XX)) (X) fk, (X (9,, (X)] Next, we consider the cases where L, l have overlapping scope and are either sum product layers.
We continue the proof by first reviewing the definitions of commulation matrix and Tracy-Singe product and their properties, they will be used to perform linear algebra transformations needed to show the correctness of Alg. A.2.
Definition A.6 (Commutation matrix (Magnus and Neudecker, 1979)). A commutation matrix K(m.n) is nm nm permutation matrix for which, for any x matrix A, we have that ((mm)) vec A T) vec(A), where vec denotes the flattening (or vectorization) operation.
Proposition A.3. Let P denote the permutation matrix I, @ ((.mm) @ L.. The following proper- ties hold (Neudecker and Wansbeek, 1983; Tracy and Jinadasa, 1989; Tracy, 1990).
(CI) Given v E CmM, w E C", then K (m,.a) (v 8 w) = w Ø V.
(C2) (K(s.))) (K()))))) k(m,a) and ( (P P I, 8 K (m.a) x &Ir.
(C3) Given A E Cmen, B E Crxs, then vec(A A & B) = Prm (vec () @ ve).
(C4) Given a C",, b E C", c E C", e C", then pm (a @ & c d) aacobbdd
Definition A.7 (Tracy-Singh product (Tracy and Singh, 1972)). Let A E m be a block matrix where each block A (1:5) is m, X ny matrix, and similarly let B E Cr be a block matrix where each block (+.)) is T; 8j matrix. Here, = Σ, m4, E, R3, r Σ; Ti = E, 5j. The Tracy-Singh product between A and B, with such blocks and denoted as A X B is defined as the block matrix C E Cmrxns where each block ((.A)..G)) is computed A (1.i) 69 B (R.)).
Proposition A.4. The following properties hold (Tracy and Jinadasa, 1989; Tracy, 1990).
(TI) For non-block matrices A, B, have that A X B
A @ B.
(T2) For block matrices A, B, (A
A
X
B
(T3) For block matrices A, B, we have that A X B
S G (A B), where each of the matrices Sg. G and Hğ is a special kind of a a,9 x aB permutation matrix that depends on the number of row and column blocks in A, B.
(T4) For block matrices A, B consisting of single row of blocks, i.e., my and rı, we have that A x B = (A @ B.
(T5) For block matrices A, B, we have that A 3 H SA (ABB)
For a precise formalization of the permutation matrices Sg. G H and for the proofs of these statements, refer to Tracy and Jinadasa (1989, $2) and Tracy and Jinadasa (1989, Thm. 7).
We now consider the product and sum layers case by case.
Case (i): Hadamard layers. We assume without loss of generality that each product layer receives input from exactly two other layers and, due to compatibility, two pairs of produet layers with overlapping scope will factorize their scope towards their layer inputs in the same way. Let e, l be Hadamard product layers receiving inputs from in(E,) = (E11, L in(E2) = {l21 {22), respectively. From decomposability and compatibility of E and lz. we have that Eι is compatible with En and L12 is compatible with E2g- As such, let E (resp. En) be the output layer of the tensorized circuit obtained by recursively calling MULTIPLY(EIn, l21) (resp. MULTIPLY (L12, l22)). In other words, L and Eg compute ln & l and l12 @ l22, respectively. Then, we encode lj @ lg as yet another Hadamard layer f:
t= li l2 (en1 L12) @ (fe @ l22) = (e11 l21) @ (e12 L22) E + Cg
(8)
26

---

Published as a conference paper at ICLR 2026
property of the Kronecker, with respect to the Hadamard produet. Thus, Alg. A.2 returns another Hadamard layer & that receive inputs from E,, Eg respectively.
where we used the
of Hadamard layers above. Let L, &2 be Kronecker product layers receiving inputs from in(e1) ) = {411. &12). in((2) = {l21 b22). respectively. From decomposability and compatibility of & and l2, we have that Eι is compatible with E2 and 12 is compatible with E22- As such, let E (resp. Lg) be the output layer of the tensorized circuit obtained by recursively calling MULTIPLY E2) (resp. MULTIPLY l22)). Then, encode & @ &2 as yet another Hadamard layer &:
Case (ii): Kronecker layers. We proceed similarly to the
L
L1 80 E (e11 (12) (421 L22) P
Ka ((e1 & B21 @ (f12 09 E22) P K,KG
Kg
(E) E2), K,Kg
where P KKKKi K1 in Prop. KiK; is permutation matrix used to re-arrange the Kronecker products as defined and shown A.3, and K, K2, K3, K4 respectively denote the output size of layers L11, L21, L12, l22- Therefore, Alg. A.2 returns a composition of and Kronecker layer, where the sum layer applies the permutation matrix P KaK, and the Kronecker layer receive inputs from L lg respectively. K,K;
Case (iii): sum layers. Let L1, le be sum layers receiving inputs from layers in(e)) {fI1...., LIN, and in(2)) (e21..... L2N, J. respectively. Moreover, let ( w denote the parameter matrices of L1. L2, respectively. We will firstly consider the case N1 = N2 = 1. and gener- alize it for any Ni, N₂ later. If Ni = N2 = 1, then due to smoothness we have that e and lo are compatible. As such let Eú denote the result from MULTIPLY(&1: f21). From induction hypothesis, we have that Eÿ computes l1 3 L21. Now, we instantiate layer l over variables X₃ UX2 such that
e= l21 en) @ (we) (w()) & W(1 @ L21),
where we used the mixed-product property of the Kronecker operation. Therefore, we realize l as another layer having (1)), & w(2) parameters and receiving input from f.. Next, consider the case N1, N2 > In this case we rewrite ( Oiiks, w(2) CJxxx as block- wise matrices as follows
w = [W... W(IM)
w()) (W(21). W/
Now, by smoothness of lj and l2, we have that Vi E [Ni]. Vj E [122]. & is compatible with Lzj. As such, by induction hypothesis we will denote as E, the layer obtained by calling MULTIPLY R2j). i.e., Eú is the output layer of smooth and decomposable circuit that computes the Kronecker product Ey Lii Lzj. Now, let L1, L2 denote placeholders for the layer concatenations [e11-. [iM and (E21 ... l2N,), respectively. To retrieve another layer l such that it computes E₁ 6 l2, rewrite
e e= 8 l2 = (w X WL) & L2) = (W & (2)
H J2 K2 SKa (L1 M L2)
SK2
=(W(L) & W
(L, X L2) = (w R w
where we used the following properties: (i) Kronecker mixed-product property; (ii) the transformation from Kronecker to Tracy-Singh product by using the permutation matrix H S as written in the property (T5) in Prop. A.4; and (iii) the similar transformation using the permutation matrix H S S as written in property (T4) in Prop. A.4, which is specialization (T3) as the number block rows in ( and (2) is one. Therefore, we obtained that for sum layers L,, ly having arity N₁ > 1, N₂ 2 in general, our Alg. A.2 returns another sum layer l receiving inputs in( = ( =1 and parameterized by the weight matrix (1) X (2).
Finally, we consider the complexity of our Alg. A.2. Due to Kronecker products, we firstly observe that the size each layer in the resulting product circuit must be OSS1,max where S1,max (resp. S2,max) denotes the maximum layer size in (resp. 02). Furthermore, multiplying sum layers L,, lg receiving inputs from N₁ layers and N2 layers respectively, is done calling Alg. A.2 recursively on all the N2 pairings of inputs to l1 and fg. Thus, the number of layers of the resulting product circuit is (L, in the worst case, where L1 (resp. L2) denotes the number of layers in c (resp. <2). Therefore, Alg. A.2 must in worst case time O [T 112.S_,mx...11 mux S2,
27

---

Published as a conference paper at ICLR 2026
A.6 ALREADY-NORMALIZED TENSORIZED SQUARED CIRCUITS VIA UNITARITY
In the following we prove that the modulus squaring tensorized circuit that is unitarity, i.e., satisfies (U1) to (U3). is orthogonal (Def. 5) and encodes an already-normaley distribution (Thm. 2). Below we start by clarifying some notation.
Notation. In this section and in App. A.7, we require integrating layers & that output vectors, e.g., in CK That is, given layer l having scope sc(E) = Y Z and encoding function & dom Y UZ) - CK* we write (dom(z) e(y, z) dz to refer to the K K-dimensional vector obtained by integrating the K univariate function components encoded by the scalar computational units in l:
Ely, z) dz
[laamiz] (z) e(y, ()) dz Saomiz ely, 2(y,z)2 dz
Saomiz) 2(y, dz) E Cx
(Z)
Moreover, due to the linearity of the matrix product, we can write
Wely, 2) dz
w [aammi2) e(y, z) dz Saam(z) E(y, 2) dz
W
fely z) dz. dom(2) (2)
(Z)
Furthermore, for Hadamard products of layers having disjoint scopes, we can write
J ei 21) @ (y 22) dz dz dami dom(Z,) (xm))) (Zz)
/ (dam(z))
ei(y1, dz o / Saom(z)) L2 22) dz2,
where (Y,, Y2) partitioning of Y and (Z,, Z2) is partitioning of Z. The above equality still holds if we replace the Hadamard product (0) with the Kronecker product (0).
Theorem 2.
Let be smooth and decomposable circuit over variables X. If is unitary, i.e., it satisfies conditions (U1-3), then we have that e is orthogonal and Z = -dom(X) ((xx))=d dx 1.
Proof. We prove it bottom-up by showing that, since e is unitary, then every layer l over variables C X in e satisfies Sdom(2) Z E(z) @ E(z)* dz = vec(Ik), where vec denotes the vectorization (or flattening) operation and K denotes the size of the output of L. Thus, for the last layer in i.c., having number of units K-
and computing the output of c, we have that Z 1. In other words. we will inductively prove that each layer consisting of K units encodes vector of K orthonormal functions. This will not only give us
for the last layer c, but also that e orthogonal by observing orthonormality of the inputs to a sum layer. Below we proceed by cases.
Case (i): input layer. Let be an input layer in e over the variable X. By unitarity of c and in particular from (U1), we have that l computes vector of K orthonormal functions e(X)= (X) ... S.....'( (X)) Therefore, we have that Jaam(x) ((x) @ l(x))* dx vec(Ix).
Case (ii): Hadamard product layer. Let l be a Hadamard product layer in receiving inputs from layers it( {Li, (2). By decomposability, we have that sc(Ei) Z1, sc({2) Zz. with Z, n Ze = Ø and sc = Z = Z, U Zz. Assume by induction hypothesis that Jdam & (2,) @ (z1)) dz = vec(Ix) and Jdom Zz) (z(2)) (z()))
dz vec(Ix). Then, we have that
e(z)) ② E(z)' dz / (L1(Z)) ④ (z())) & (Z1) @ (2(22))) dzj dz2
dom(z)
dom )x
- -(Je(z)) & (z1) dz
((((z)) 2 (2(Z2)" dzz
())
@dom(z..
vec(Ix) @ vec(Ik) = vec(Ix),
where we used the Kronecker mixed- -exeudtrroductt property with respect to the Hadamard product, and decomposed the integral into lower dimensional ones by using the fact that Z, n Zg = Ø.
Case (iii): Kronecker product layer. Let l be Kronecker product layer in receiving inputs from layers in(E) {L1, L2). By decomposability, we have that sc(E1) Z,, sc(E2) = Zg. with Z O Ze Ø and sc(e) Z Z U Zz. Assume by induction hypothesis that Jdom(z,) e1 (z)) &
28

---

Published as a conference paper at ICLR 2026
L1 (z1))) dz1 vec(IKi) and Saom(Zz) (2(2)) 2 Ez(z22) dz2 = vec(Ixa). Then, we have that
/ dom(2)
{(z) @ [(z))) dz= = /
@ (Z1())) x (zz))) dzj dz
dom dom( xddm
[()](z)) @ L (zi)") @ (L2(z2) @ (2(2)))) dz dzz K2Ki
dom(Z,) (
[V
( (2(2)) @ (z(2)) dz2
-P K2Ki
Li (1)) @ (z))) dzi @ (dommiz))
dom(()))
P (vec(IR,) & ve)() - vec(In, @ IKg) - vec(Ix,
K2K, K2K
where PK2K,, is a permutation matrix as defined as in Prop. A.3. In particular, in the above we apply K2K;
the property (C4) in Prop. A.3, then decompose the integral into lower dimensional ones by using the fact that Z, n Z2 Ø3, and finally use the property (C3) in Prop. A.3.
Case (iv): sum layer. Let & be sum layer in receiving inputs from layers in(e) { and l is parameterized by (semi-Junitary matrix W K with K₁ I K2 by unitarity of c, i... ww Ix, as for (U3). From smoothness, We firstly assume that = 1, ie.. in(e) = {l}, J. and then handle the case N > later. For N = by induction hypothesis we have that /dom(2) (z( @ (z) dz vec(I )- Then, we have that
recover that sc(f,) sc(L) Z, for any i [N].
((z) ② E(z) dz =
(WE) (z)) &
dz = (W & W
(z(Z) @ E (z) dz dam(Z)
dom (Z)
dom (2)
-( W (vec(I [k,) vec( K2 W = vec( (Wc(( = vec(Tk,),
where we used the Kronecker mixed-product property, and the following property of the Kronecker:
(A @ (V) vec(BVA )) for matrices A, B, V. Consider now the case N > 1. For all i [N] by induction hypothesis have that (aom(z) (1(z) dz vec(I,,), where Jr denotes
the size of the output of l,, i.e., K₂ ΣN Jr With a slight abuse of notation, we overload the basis scope definition (Def. A.2) to layers rather than units, i.e., we denote as Bx (l) the union of all basis scopes w.r.t. X of the units within l. Then, from (U2) of unitarity by hypothesis, we can apply the following lemma.
Lemma A.5. Let L2 be output layers of smooth and decomposable tensorized circuits cı, c2 over variables X. Assume that, for some X E X, the input functions computed by the input layers over X in Ci and 02 are orthogonal with each other, i.e., EX E X: Vf E Bx(e)) Vg E (x(22): [dom(x) (x)g(a)) da = 0. Then, for any Z C X such that X E Z, we have that Saom(z z (y),z) @ (2(y,2) dz O, where y dom X Z).
Proof. By hypothesis for some X E Z C X the basis scopes of é, and lg w.r.t. X consists of orthogonal functions over X. As such, for any pair of units n and m respectively é and Ez, the input functions over X in the sub-cireuits rooted in and m, respectively, are orthogonal. Therefore, apply Lem. A.2 to recover the wanted result: all pairs of units n and m respectively in & and lg encode orthogonal functions when fixing variables not in Z, i... Jaom(z) (Z) e, (y z) @ b z)* dz 0. N
can
Therefore, for all E [N]. [N], i + j. by leveraging (U1) and (U2) of unitarity we can apply Lem. A.5 and recover that I ddm(()) (z) 8 (z)) dz = 0, i.e. a zero vector of size J;Jy. From these equalities and by rewriting Kronecker products in terms of outer products (denoted as o), we also obtain that ldom(2) (z))) (z(z) dz Ij,, and Sdom(z) (z(z)* (z( dz for any í,j E [N], i + j. where denotes the outer product. Therefore, we can write the following:
[ dom(z)
((z) 2 E(Z)" dz = /
/dom(z) (W[E((2)- ... ........... ex(2)) @ (W)) ... (x(2)" dz
= =(W 8 W*) dom(2)
vec (1e( (..(()))... ((41))))12222))))(((((1 ... (x(2)) dz)
29

---

Published as a conference paper at ICLR 2026
Jdomiz) (z)²) (z)
Jdom(z) (ı(2)) Lyv (z)
(W & Weevec
Jdom(2) (x(z)" o (z) dz
Jdom(2) Cx(z)" o LN (z)
Il
(W & Weev
0
IJ
(W& W")vec(Ix,,) vec(W"IL Ix, = vec((WW)))) vec(Ix;))
where we applied the same properties used for the case recover that each sum unit in the sum layer l receives input from units encoding orthogonal functions, as integrating all pairwise products yields an identity matrix. Therefore, turns out that is orthogonal. By recursively applying the above cases, if & is the output layer of the tensorized circuit then K1 = 1, and we have that Sdom(x) [c(x)]2 dx Sdomix) {(x))(xx) dx = vec(I,)
shown above. From the above we
Algorithm A.3 MAR-SQUAREIT SQUARED-UNITARYLE
Input: A tensorized circuit variables satisfying conditions (U1) (U4), where is the output layer in a set variables Output: The vector (dom(z) Ely, z) & E(y, z)" dz. l is the last layer c, then consists of exactly one unit, and thus the algorithm returns the marginal likelihood p(y) depends on only variables being marginalized
X to marginalize, and an assignment y variables Y X Z.
Seam(z) Je(y, 2) dz.
1: if sc(() Z Ø0 then
2: return vec (Ic
3: else if sc(E) 2 2 then EVAL-FEED-FORWWRDD y)
l does not depend on the variables to marginalize
4:
return
6: else é is sum layer then
b l depend on both the variables to marginalize and the ones left over 7: let é receive inputs from (lI,..., EN and parameterized by W CKiXK2
Assume is block matrix W [W(1) W
9: ri +
UNITARY((AAARAAAAA.. Zn sc():)), vi [N].
10: let R,; be the reshaping of r; as J, matrix, Vi E [N]
return vec (EN") W. (+11
12:
else if l is a Hadamard product layer then
13:
let L = L1 @ &
14: ri + MAR-SQUARED-UNITAAA (f1, Z sc(()))
15:
r2 +- MAR-SQUARED-UNNITRYY &2, Z sc((2)
16:
return r1 1
17:
clse
b. l is a Kronecker product layer
18:
let l E1 8 lg MAR-SQUARED-UUITTRYY ra + MAR-SQUARED UNITARY (L2, y, Z sc((2)
19:
sc((e)
20:
21:
return P(r, 3 r2), where P is permutation matrix
A.7 A TIGHTER MARGINALIZATION COMPLEXITY
Theorem 3. Let be a tensorized circuit over variables X that satisfies (U1-4), and let Z C X.
Y = X Z. Computing the marginal p(y) = /dom(() ic(y, z) dz requires time O \ Oz Smmx
Joy oz $2 ) where d, is the set of layers whose scope depends on least one variable in *.
Proof. We prove it by constructing Alg. A.3, i.e., the algorithm computing the marginal likelihood given by hypothesis. Alg. A.3 is based on two ideas. First, integrating sub-cireuits whose layer depend only the variables being integrated over (i.e., Z) will yield identity matrices, so there is no need to evaluate these cub-circuits. Second, the sub-circuits whose layers depend on the variables that are not integrated over (i.e., Y) do not need to be squared and can be evaluated bringing linear rather than quadratic complexity w.r.t. the circuit size. Below, we consider different cases layers based the variables they depend on, and we later discuss the overall complexity.
30

---

Published as a conference paper at ICLR 2026
Case (i): layers depending variables Z only. Consider layer e in such that sc(L) S Z, i... E Φz \ oY by hypothesis. Since the tensorized circuit c unitary by hypothesis, the tensorized sub- circuit rooted in l is also unitary. Therefore, from our proof for Thm. 2 we recover that integrating the Kronecker product of and its conjugate yields the flattening of an identity matrix. Formally, have that ddmm(sc(E)1zz)) E(z) l(z)* dz vec(Ix), where K denote the size of the output of f. Therefore, layers in dz \ oy do not need be evaluated, and this is reflected in L1-2 of our Alg. A.3.
Case (ii): layers depending on variables Y only. Consider layer l in e such that sc((e) n Z Ø i..,, l E Øy \ Φz by hypothesis. Since l does not depend on the variables to be marginalized out, can compute E(y) @ Ely)" with y E dom(sc(f) Y) by evaluating & y and then computing the conjugation and Kronecker product. This case is captured by L3-5 in Alg. A.3. Note that the complexity of evaluating l on y is @ ( Moreover, we observe that L3-5 are executed only on layers l that are input to other layers having scope overlapping with both Y and Z. i.e. they are in dy O Oz If that were not the case, then either Case (i) would have been executed, or L3-5 would have been executed on the layer receiving input from é instead. Since each product layer in dy O Φz receives input from exactly two other layers f,, and at most one between E and & can depend on variables Y only (i.e, it is in @y \ (z)) we have that L3-5 are executed a number of times that is in Oloy n ézl). This would be true even if a product layer receives input from more than two layers, as it can be casted into multiple product layers receiving input from exactly two other layers. Furthermore, since the size of layer & (i.e., the number of scalar input connections) is bounded by below by the number of units K in L. we have that the Kronecker products (L5) will account for just a Oldy O oz K2) C CO n Φz (aax) factor to the overall time complexity of Alg. A.3.
Case (iii): layers depending variables both in Y and Z. Consider layer E in e such that sc(E)nY Y * 2 and sc())zZ * Ø0, i.e., & E Φy fizz by hypothesis. Since we assume that input layers can only compute univariate functions (Def. 8), we have that l must be either sum or product layer.
Case (iii-a): product layers. Now, assume l is an Hadamard product layer in e receiving input from L1. Let 2- = sc({) n 2. 2, -c((2)) n 2, 2, = sc(E2) n Z. From decomposability. we recover that (Z,, Z2) is partitioning of Z. We denote ý the variables assignment obtained from y by restriction to variables in sc(e) Ž, and similarly let 81 denote the variables assignments obtained from y by restriction sc(f)) 2, sc(E2) Zz, respectively. Therefore, we can write
Secs 2) 2 2)" dž Joon dZ)(
(Jenlt))
(21) (11(,1,21) 21) 21) 01 21)" dē, @
( 22) @ Re 22) d22 Jdomi (22)
where we used the Kronecker mixed-product property w.r.t the Hadamard product, and split the integral into lower dimensional ones. Therefore, L12-16 our Alg. A.3 use recursion to compute the integrals w.r.t. the layers f, lg and then aggregate the results with an Hadamard product. In the case of being a Kronecker product layer in instead, a similar approach can be used, resulting in L18-21 in Alg. A.3. In the case of Kronecker product layers, permutation matrix described as in Thm. 2 is used.
Case (iii-b): sum layers. Let é be a sum layer receiving inputs from layers in(E) = { (l.....,44 } and parameterized by W E C x K2, Assume that W is a block matrix W [W()) (M)) Moreover, let 2 = sc(L) n Z, Y = sc(E) Z and let ý denote the variables assignment obtained from y by restriction variables in sc(E) 2. For any i, E [N), we will denote as R.j the matrix
R.j = faom(2) ly 2) o &g (ý, 2)" d2. By the satisfaction of unitary and the property (U4), and by
applying Lem. A.5 we have that Vl,, ly in()), l, + Lj. Rij 0. Therefore, similarly to our proof for Thm. 2, we recover that
J e(y, 2) @ 2)" dē- domi dom(Z)
/(WIe( ....)) @ (8)) ... eN 2) da dom(2)
= -W & W*) vec( (e (9.2)* 2)...)... ... (N 2) (9 2) (x, 2))
d2m
31

---

Published as a conference paper at ICLR 2026
Rii
= -W & W'ec
vec (W diai
R
Riv
N w v
N W W w(r))
R2 w
= vec
vec
L6-11 in our Alg. A.3 recursively marginalize the Kronecker product of E, by its conjugate, for all i E resulting in matrices { and then performing matrix multiplications and summations.
Computational complexity. We recover the overall time complexity stated in the theorem. First, Case (ii) has an overall complexity of O( \ (malS + |øy n dz (Smm)) Second, for Cases (iii- a) and (iii-b) above,
have that need to evaluate the integral of "squared" layer, i.e., the integral faom(2) E(ý, 2) @ E(y, 2)" dá. Thus, these cases account for a quadratic complexity w.r.t the layer size, i.c., O (S m as highlighted in the proof of Prop. A.2, and they occur a number of times that is Ioy n Φz)- Therefore, we conclude that the overall complexity of our Alg. A.3 is m. Furthermore, note that we have 1 +0z|+ Cázz In other words, the complexity is independent on the number of layers whose scope is a subset of Z. ie.. léz \ (v Although the complexity depends on the particular marginal being computed and the circuit structure chosen, our Alg. A.3 can be much more efficient than O(L's max) To see this, consider the following example. The structure for circuit defined over pixel variables can be built by recursively splitting image into patches obtained by alternating vertical and horizontal even cuts (Mari et al., 2023; Loconte et al., 2025a). If Z consists of only the pixel variables in the left-hand side of an image (i.e., w.r.t. L since only a few layers near the circuit output layer will depend on variables both in Y and Z. The rest of the layers will entirely depend either Y or on Z. Therefore, the best-case complexity considers jøyNéz) being independent of the total number of layers L. i.e., it is O(ox \oz (max)) [
Oloo (zz mmax 1 f
O I
computing the marginal of the right-hand side Y), then bo O ndzl is constant
A.8 ENFORCING ORTHOGONALITY IS #P-HARD
We presented new families of circuits through the introduction of novel circuit properties, namely orthogonality ($3) and unitarity ($4). In general, each family of circuits with a particular parameteri- zation and set of structural properties they satisfy exhibit different expressive efficiency, which refers to the ability of encoding function or distribution with a circuit computational graph having polynomial size w.r.t the number of variables (Martens and Medabalimi, 2014). As such many works focused on the formulation of hierarchies that compare different circuit clases in terms of their expres- sive efficiency (Darwiche and Marquis, 2002; de Colnet and Mengel, 2021; Loconte et al., 2025b). Here, we provide a preliminary expressiveness analysis by investigating which of the presented prop- erties can be enforced in polytime, as this would immediately guarantee no loss expressive efficiency. We start with a negative result, which tells us that enforcing orthogonality is #P-hard.
Theorem A.3. Let c be smooth and decomposable circuit over variables X. Then, constructing a circuit from such that e' c((X) = c(X) and é' is an orthogonal circuit is #P-hard.
Proof. The idea is to construct reduction from the problem of making smooth and decomposable circuit also orthogonal to #3SAT, which is known to be a #P-hard problem. In particular, we leverage the same technique used to prove that representing any power of a pno-sstrrcuurddddcooposbbbl circuit as another decomposable circuit is in general #P-hard (Vergari et al., 2021, Thm. 3.3).
We start by defining the #3SAT problem. Let X {X,), be a set of Boolean variables, and let & be a CNF formula that contains m clauses I' = {cz 1 1 where each clause contains exactly 3 literals. The #3SAT problem consists of counting the number of assignments to the variables X that satisfy 4. i.c., the quantity Exedom(x) (x). where (xx)
if x satisfies & and otherwise. For every
variable X; and for every clause cj. we introduce an auxiliary variable Xij. We denote as X the set of all such auxiliary variables, i.e., X = {X,, X, E X,c, E r}. For every variable X, we set all auxiliary variables associated to it to share the same Boolean value of X,, which can be described by the logic formula 3 = Ax,ex (X, + X;2 + ... + Xim). ). In order to encode & using an equivalent logic formula defined over the auxiliary variables instead, we introduce the logic formula
32

---

Published as a conference paper at ICLR 2026
Y y= Acjer Vxlev(e)) ((xt)), where we denote as ((c,) the variables scope of the clause ej and ((X,,) is the literal of X, found in Cj. We can see that @b is equivalent to 3 Ary. As detailed in Khosravi et al. (2019) and Vergari et al. (2021, $A.3), the logic formulae 3 and 7y can be respectively encoded by pruuctred-decomposale done by casting conjunction and disjunctions into products and deterministic sums, respectively. Therefore, ((x) can be computed as the product of the outputs of c3 and cy when evaluated x, which is obtained from the assignments x as for the sharing of Boolean values between the auxiliary variables of each X,, Crucially, we have that Cp and by are not compatible circuits by construction.
and deterministic circuits Cg and c. having polynomial size. This is
Reducing finding an orthogonal circuit to solving #3SAT. Consider now the circuit Co computing (x) = ca (x)x) + (&) for any & E dom(X) Since Cg, Cy are
non- compatible, and with overlapping support for generic satisfiable logic formula o we have that ca is smooth and decomposable circuit that is non non-determinisicc and non-structured decomposable. Moreover, from the sizes of Ca and Ce we recover that C₂ has also polynomial size. From now on, we will focus on the problem of computing the quantity ExEdom(X) Co (x)2 called POW2PC in Vergari et al. (2021), ), and reduce it to solving #3SAT. Formally, by the construction of ca we have that the POW2PC quantity can be written as
Σ
ca cx())²
Σ cx(x)² + xEdom(X)
Σ x)
(x) +2 Σ (x)
xX)om(X)
&Edom(X)
Now, since Cg and Cy are both deterministic, we observe that Exedom(x) (x) and Exedom(X)) (, (x)² can both be computed in polytime (Vergari et al., 2021). Assume by absurdum that there exists a polytime algorithm taking a smooth and decomposable circuit as input, e.g., Ca. and that returns orthogonal circuit computing the same function. Then, from Thm. I we have that we would be able to compute Ex ca (x)² in polytime. As a consequence, from the definition of POW2PC, we would be able to compute the remaining quantity Exedom()) ca (x) k),c (x) in poly-
time. However, computing this last quantity in polytime would imply solving #3SAT in polytime, since the conjunction of 33 and 7 is equivalent to the logic formula & as described in the preliminaries above. Therefore, an algorithm receiving a smooth and decomposable circuit as input and converting it to an orthogonal circuit cannot run in polytime. In particular, the problem of representing smooth and decomposable circuit as an orthogonal one must be at least #a-hard
From Thm. A.3 it turns out that enforcing regular orthogonality and unitarity must also be hard, since they both imply orthogonality (see App. A.3 and Thm. 2). However, Thm. A.3 does not necessarily imply an expressiveness separation (Martens and Medabalimi, 2014) between orthogonal and smooth and decomposable circuits, i.e., the existence of a family of functions that cannot be encoded by any orthogonal and polysize circuit, while can by a smooth and decomposable circuit. The reason is that Thm. A.3 does not say anything about the minimum circuit sizes required by an orthogonal circuit, While investigating such separation deserves a separate work, here we conjecture it hold similarly to known separation between deterministic and non-deteriinistic circuits (Bova et al., 2016).
In the following, we instead investigate whether the choice of orthonormal input functions and (semi- Junitary weights in tensorized circuits (i.e., only the conditions (U1) and (U3) in unitarity) can restrict their expressiveness when compared to squared PCs that do not satisfy such conditions. First, as we further detail in App. C, there are many choices of orthonormal basis functions that come with guarantees about the families of functions they can arbitrarily approximate. Second, the following theorem guarantees that there is no loss in terms of expressive efficiency from restricting the sum layer parameters to be ssemi-)unitary matrices (i.e., (U3)), as can be enforced in polytime.
A.9 ENFORCING (SEMI-)UNITARY PARAMETERS IS EFFICIENT
Theorem A4. Let c be a smooth and decomposable tensorized circuit over X. There exists an algorithm running in polynomial time returning a circuit e' with (semi-)unitary matrices as sum layer weights, where c' is equivalent to c up to multiplicative constant, i.e., e' c((x) = 3c(X), B 2 0.
Proof. We prove the correctness of our Alg. A.4 to "unitarize" the weights of a tensorized circuit, whose idea is to recursively make the circuit parameters (semi-)unitary via QR decompositions. More
33

---

Published as a conference paper at ICLR 2026
Algorithm A.4 UNITARIZE(()
Input: tensorized circuit over variables X, where the output layer
Output: The output layer E' of tensorized circuit e' over X such that each sum layer in c' has a (semi Junitary matrix as weight; and matrix R E C CK1 K₁ I K2, such that l equivalently computes Re' where K1, K2 are the width of layers L, E' respectively (i.e., the number of units in the layers E.
1: if is an input layer then
2: Assume computes K orthonormal functions
3: return (L, 1x)
4: if is sum layer receiving inputs from in(e) fli,..., ] and parameterized by W E Ki then
(L), R.) <- UNITARIZE(E.). (.). Vi [N]
6:
where R. E C
let W =W( W(N xK
8: where Vi E [ w E C and K2 =E J.
(( E CK where 17 E FT 10: Factorize Vi = QR. where Q is (semi-)unitary and R is upper triangular
9: let V = (
11: let l' be sum layer computing Q [ fxx
12:
return (E', RR)
13:
is Kronecker product layer with inputs L, then (E,, R.) + (NITARIZE(E)), R. E xK1k
14:
15:
(E2, R2) (NITARIZE(&2), R. E CK5XK,
16:
be a layer computing & & & return (E', R1 & R2)
17:
> &: Kronecker matrix product
18:
if T is an Hadamard product layer with inputs L,, lg then
19:
(Ei, R1) + UNITARIZE(Ei). R. E CK1x82 (E, R2) f- (NITARIZE(&2), R. E CKiXKs
20:
21: let L' be a layer computing & @ E
22: return (E', R. R2)
D Face-splitting matrix product (see Def. A.8)
formally, Alg. A.4 is used to retrieve tensorized circuit e' from such that c((X) Be(()) for non-negative constant 3, where the weight matrices of sum layers in c' are (semi-)unitary To do so, we take inspiration from the unitarization (or canonization) algorithm in tree-shaped tensor networks (TTNs) (Shi et al., 2006; Orús, 2013; Cheng et al., 2019; Krämer, 2020). That is, the idea of Alg. A.4 recursively apply QR decompositions make the weight matrices of sum layers (semi)Junitary while still preserving the function computed by the circuit up to non-negative multiplicative constant 3. However, differently from the canonization algorithm in (TTNs), our Alg. A.4 generalizes to hierarchical tensor factorizations when represented by circuits (Loconte et al., 2025a) (see $$3 and 4).
Assumptions. In the proof we are going to assume that each sum layer receives inputs from product layers, and that each product layer receives inputs from either two input layers or two sum layers. These assumptions are without loss of generality, as they can be enforced in polynomial time without changing the function computed by and with at most polynomial increase in circuit size. For instance, a product layer receives inputs from another product layer, then we can "interleave" these product layers by introducing sum layer whose parameter matrix is an identity matrix. Now, given the output layer of a tensorized circuit, we will show by structural induction that Alg. A.4 returns pair (f", R), where f' is the output layer of the tensorized circuit c', and R is matrix such that equivalently computes the matrix-vector product RÉ'. In particular, R will have as many rows as the number of units in l (i.e., its layer width) and as many columns as the number of units in E'. Moreover, we will have that the sum layers in the sub-circuit rooted in E' have (semi- Junitary matrices as parameters. Therefore, when Alg. A.4 is applied to the output layer of e, then R is 1 x matrix containing the value of 3 as stated above. We proceed by cases below.
Case (i): input layer. The base case when é is an input layer in c, Assume that l computes the value of K functions. Then, LI-3 in Alg. A.4 returns l unchanged, i.c., L' = l and it sets R to be the K x K identity matrix Ig. We also have that the circuit rooted in e' does not have sum layers and therefore trivially satisfies the requirement that the weights of the sub-circuit rooted in E' must be
Case (ii): sum layer. Let be sum layer receiving input from layers in(e) = [ and computing the matrix-vector product e W[e ... L..,, where W CKiXK2 denote the parameter matrix of l. By inductive hypothesis, for each L, i E [N], Alg, A.4 returns the output layer l, of circuit whose weights are
and matrix R, C4 with K₃ Σ Je. where H, is the
34

---

Published as a conference paper at ICLR 2026
number of units in the layer E. That is, we have that L, equivalenty computes R.C,, We denote W as the block matrix W [w(1).. w(y where w CKix,, and we can rewrite the function computed by l as follows
N
N Σ 1=1
L = W(e ... LN]
Σ 1=1
w
R viG Exl.
where we set V [V()... (il)...(())).) v(N) CkixH, with H Di H,, and such that each block is v(i_ = w R. CKixH; To retrieve (semi- Junitry matrix, we perform the QR decomposition on V thus retrieving V = QR. Now, in the following we distinguish two cases based on whether V is a wide or tall matrix.
QR.
where Q E C R CHXKi where Q E CHxKi, E CRiXKi
vt is wide square, i.e., H K1 v tall, i.e., H K
v
QR
Moreover, in the wide square case have that Q Ly, while in the tall case have that Q'Q I,, In both cases, have that R is upper triangular. Thus, computed by l as
rewrite the function
L e= V 1xl = RiQUT ... exl = R'e'
where l' is sum layer parameterized by the (semi- Junitary matrix Qi and computing Q' -x Therefore, L4-12 in Alg. A.4 returns (e', RR), and we have that the sub-circuit rooted in l' has (semi- Junitary matrices as the weights of sum layers. Finally, we observe that the number of sum units in e'-or equivalently the number rows in Q'-is min (H, Ki) whatever V is a wide, square or tall matrix. Therefore, the number of units in l' is bounded by the number of units K₁ in l. Similarly, the size of the matrix R returned by Alg, A.4 is at most of size K1 K1. Instead, in the particular case of V being tall, i.e., H K1, than W E C x K2, which would account for an increase in the circuit size. As we detail below, this increase in circuit size is still polynomial, as it can only occur in the case of Hadamard product layers and it is bounded to be at most quadratic w.r.t. the original circuit size.
notice that Q' E CKi can possibly be larger
Case (iii): Hadamard product layer. Let é be Hadamard product layer computing l = &1 + l2. By inductive hypothesis, let Ej and E, be the output layers tensorized circuits obtained by recursively applying Alg. A.4 & and lz, respectively. Moreover, let R₁ CKixK2 and R2 E C X be the matrices obtained via Alg. A.4 w.r.t. Lj and l2 That is, we have that & (resp. l2) equivalently computes & (resp. R2C.). For this reason, we can rewrite the function computed by l as
= (R(C) @ (R2C) (R, (2) 69 E).
where we used the Hadamard mixed mixed-product property, and denotes the face-splitting matrix product.
Definition A.8 (Face-splitingg matrix product). Let A E Cm and B E C be matrices. The B is defined as the matrix C Cmxcr
face-splitting product
a &
b
A1
b
C
where
A
: am
B
am
X
bm
b
and (a, 1 (b,) are row vectors.
L18-22 in Alg. A.4 constructs a Kronecker layer E' in c' computing E' = @ Lz i... equivalently computes (R, R2).'. Thus, L22 returns returns both E' and the matrix R, R2. By inductive hypothesis, we have that the circuits rooted in E and E have sum layers with (semi-Junitary weights, thus also the circuit rooted in l' must have. Furthermore, we observe that an Hadamard product layer replaced by a Kronecker ones, resulting in a quadratic increase circuit size. To avoid the size of the layers in e' and the matrices R being returned by Alg. A.4 to grow exponentially in the particular case of subsequent Hadamard product layers c, the assumptions made at the beginning of this proof become here useful. As stated above, e by using sum layers having identity matrices as parameters. By doing so and as observed Case (ii) above for sum layers, the size of the matrices R returned by Alg. A.4 and the number of units in
efficiently "interleave" consecutive Hadamard layers in
35

---

Published as a conference paper at ICLR 2026
each sum layer being built in c' remain bounded. Therefore, this effectively bounds the size of the Kronecker layers being built in c' from Hadamard layers in c.
Case (iv): Kronecker product laver. Let l be Kronecker product layer computing L = L @ Lg. By inductive hypothesis, let E and Eg be the output layers of tensorized circuits obtained by recursively applying Alg. A.4 on l and L2, respectively. Moreover, let R, E CK xxx and R2 E CKax Ka be the matrices obtained via Alg. A.4 w.r.t. L and l. That is, we have that & (resp. l2) equivalently computes R, Lj (resp. R2C2). For this reason, we can rewrite the function computed by aas R
= (R,L) @ (R2C) = (R1 @ (2) & &E),
where we use the Kronecker mixed product property. That is, we retrieve a Kronecker layer l' in computing e' = E 6 Ez, i.e., equivalently computes (R, 69 R2) Thus, L13-17 in Alg. A.4 returns both f' and the matrix R, @ Rg. By inductive hypothesis, we have that the circuits rooted in E and Eg have sum layers with (semi-)unitary weights, thus also the circuit rooted in E' must have.
Case (v): output layer. We consider the case of l being the output layer in c, thus resulting in the last step of our Alg. A.4. Without loss of generality, we consider l being a sum layer. Then from our Case (ii) above, we have that R C2xl is obtained by the QR decomposition of column vector V E CKX1, thus corresponding to the scalar T11 such that I|r V'Ila 1, i...
en = - (EK K - (oall²) Therefore, the non-negative scalar 3 mentioned in the theorem must be exactly / = r11-
A note the value of B and on unitarity. Assume that e satisfies (UI) and (U2) of unitarity. Since Alg. A.4 does not change the input layers and the dependencies of the sum layer inputs to the input layers, we have that c' also satisfies (U1) and (U2). Therefore, e' is unitary because satisfies conditions (U1) to (U3), and thus from Thm. 2 we have that the modulus squaring of e' is an already normalized distribution, i.c., pXX) = (x) = [2) This means that, under the assumptions of (U1) and (U2), the value of 3 is exactly 3 = - with Z being the partition function of the modulus squaring of i.e., Z = [dom(x) |e(x)] dx. Finally, Thm. A.4 can be seen as the dual of another result about monotonic PCs shown by Peharz et al. (2015): they show an algorithm that updates the positive weights of smooth and decomposable PC such that the distribution it encodes already normalized, while Alg. A.4 updates the complex weights of a circuit such that its modulus normalized distribution.
squaring is an
note on the computational complexity. We now analyze the computational complexity of Alg. A.4. We observe that the complexity mainly depends on the complexity of performing QR decompositions and computing Kronecker (or face-splitting) products of matrices. as many QR decompositions as the number of sum layers in c, each requiring time O(K H) in the case of a wide matrix E CKi*H and O(K, IH²2) in the tall matrix case. Now, let Kmox denote the maximum number of units in a layer in By the way the matrix V is computed (see Case (ii) above) and since the Hadamard layer is the only case accounting to a quadratic increase in layer width (i.e., transforming Hadamard into Kronecker and leveraging the face-splian face-splitting product), have that K2 < Kmax and H < K2n As such, the complexity of performing the QR factorizations will be ( maxx), where I. is the number of layers in c. Similarly, the complexity of computing Kronecker and face-splitting products as in Cases (iii-iy) above is O ((Ka)) Overall, the complexity of our Alg. A.4 is (L
particular, we need to perform
B TREE TENSOR NETWORKS AS
CIRCUITS
In this section, we show how the complete contraction of a tree-shaped tensor network (TTN) (Shi et al., 2006) can be encoded by a particular class of sructured-decomposabb tensorized circuits (Def. 8), where product layers are Kronecker products. By a very similar argument, one can see how also other TN structures, such as MPS (Schollwocck. 2010) and tensor rings (Zhao et al., 2016), can be encoded by sruuctured-dccompsssee Tucker tensor factorization (Grasedyck, 2010) as a circuit was already formally shown in Loconte et al. (2025a), in App. B.1 we connect this construction to a canonical form of TTNs ensuring normalization of the distribution modeled via modulus squaring.
circuits. Although a result representing the hierarchical
'Hirarcchcal Tucker tensor is essentially TTN having binary tree structure Penrose graphical notation.
36

---

Published as a conference paper at ICLR 2026
W
X
Ezz
W
W
76
W
W
2/2
X1
X2 X3
X
Figure B.I: Tree tensor networks (TTNs) represented as tensorized circuits. The contraction of a TTN over variables X
(left, in Penrose graphical notation) starting from the factors at the bottom towards the root node can be encoded by a tensorized circuit having Kronecker product layers, and whose sum layers are parameterized by the non-leaf tensors, i.e., W(0), W(1), w (right). Due the densely connected structure, the circuit is not basis decomposable (Def. 6), the products that are input to the output sum depend on the same input functions (in colors). Similarly the circuit corresponding to the MPS factorization shown Fig. this circuit structured- decomposable because the products encode a single hierarchical partitioning of the variables.
From TTNs to tensorized circuits. When compared to -atrii-prodduct states (MPS) TNs (Pérez- García et al., 2007), TTNs come with the advantage of better capturing longer variables sequence correlations by using hierarchical tree-like structure (Murg al., 2010; Seitz et al., 2022). Formally, let X = و be a set of variables, and for each X, E X let V = {us dom + =) be of factors for the variable Xj. where R is the factorization rank of the TTN. For simplicity, here we consider the case of binary TTNs, i.e., whose structure in Penrose graphical notation is a binary tree, but the following discussion be translated other TTNs well. A rank-Rt binary TTN factorization defines the following decomposition of (X).
k=1
R
N-1
(x)
W
II n=1
w
(n) in lan 12
II la-2- (zz)
(9)
$1 12
12N=1
where (0) CRxi and for all n E [N -I: 1]: w(n) CRXRXR with being the total number of inner tensors in the TTNs, i.e., N = d - I in this binary tree case. For example, Fig. B.1 (left) illustrates TTN over variables, which encodes the following factorization of (X()..
R f Σ
ft
=
Wist
w
w (2) fiigis Wiis 2/s (I1 Jo (I2) (æa) ( (10)
The complete contraction of TTN following bottom-up topological ordering be encoded by a tensorized circuit. In order to give an intuition of this, we focus on the example in Eq. (10). We reorder summations and multiplications in Eq. (10) as in the equation below, which corresponds to a contraction ordering that starts from the factor leaves and proceeds towards the root tensor of the TTN (i.e., the matrix w(()).
( 42, 23, x44
n n
R
R
R
f
Σ i
w
(0)
ΣD
w
(1 (xz)
Σ
Σ Ri
w
(23))
(11)
In other words, we pushed the outer summations as inside as possible in the TTN factorization formula. By doing so, recover three groups of sums and products that contract the indices (2,,
37

---

Published as a conference paper at ICLR 2026
(iz, and fis, do). respectively in red, green and blue colors in Eq. (11). In order to build tensorized circuit e encoding this contraction, i.e., c(X) (X),, we construct one input layer e for each variable X, E X computing the corresponding factors in V, , as a R-dimensional vector. That is is, for all X, E X we have that e computes E (a;) [ (zz) of (z,)] We then observe from Eq. (11) that the composition of groups of sums and products can be encoded by a hierarchical
composition of sum layers and Kronecker product layers. Formally, let wi denote the reshaping
of ( as a x R² matrix, and similarly let W and ( respectively denote the reshaping of W(1 and W(2) as R x H² matrices. Then, we can rewrite Eq. (11) as
w
[w (ef(zi) 8 (T [
(w()) (2) (e)(2a) 8 ef ((a)))
(111, 22, F3, T3)
x
(12)
The above can be equivalently encoded by a tensorized circuit c, as we illustrate in Fig. B.1 (right). That is, the Kronecker products computed by Kronecker layers in c, and the matrix-vector multiplications are computed by sum layers respectively parameterized by the matrices W w(")
(2) We also observe that the corresponding circuit is cuucturedddecomposabbe interpret its structure as encoding a single hierarchical partitioning of the set of variables X it is defined on, i.c., X is partitioned into ( X2) and {X3, by the Kronecker product layers, and in turn these are split towards the univariate input layers respectively over (X1), (X2) and { (X3), (Xa).
we can
Next, connect our orthogonality conditions defined over circuits with popular TTN canonical sur--sometimgs called upper-canonical form (Cheng et al., (019)-wicch ensures that the cor- responding Born machine encodes an already-normalized distribution. That is, we show that this canonical form in TTNs is a particular case of unitarity, i.e., the corresponding tensorized circuit satisfies the conditions (U1) to (U3) shown in $4. We then make some observations on how unitary tensorized circuits can represent a strictly larger set of hierarchical factorizations when compared to TTNs, which instead can only be muucttredddccoppsseee
by construction (see $2 and App. B).
B.1 UNITARY CIRCUITS GENERALIZE UPPER CANONICAL TREE TENSOR NETWORKS
The upper-canonical form is a special case of unitarity. The upper canonical form of a TTN consists of two assumptions the factors and the inner tensors. That is, we require the factors over the same variable to be orthonormal, and that each inner tensor is an isometry w.r.t. the two indices pointing downwards. More formally, a TTN is upper canonical if satisfies the following conditions.
[
vX, E X, Vk1, 22 E [R]:
(omm(X))
1/ (2 (Iz)* dr, Ō
(13)
R
R
R
w (U) i2 .1.12 dess and Vn E [N
W.
(U)
1]: f2n+1=1 12(1+11)1
Σ
Σ
(n) w 12 2hizn-122(es)
(n)x
6t
(14)
is possible to show that these two conditions ensure that the partition function of the corresponding Born machine obtained by modulus squaring of v is Z fdom(x) |v(x) dx = 1 (Cheng et al., 2019; Seitz et al., 2022). We interpret Eqs. (13) and (14) as conditions defined over the input layers and
weight matrices of the tensorized circuit described by Eq. (12). That is, under upper canonicity of the TTNs, we recover that each input layer e/) over the variable X, E X satisfies [dom(x,) C, (I,)) e
E) (2z)) dæ,- IR. For this reason, the tensorized circuit satisfies (UI) of unitarity. Furthermore, we have that c satisties (U2) of unitarity trivially, since by construction each sum layer receives input from exactly one other layer, i.e., Kronecker product. Finally, we can equivalently rewrite Eq. (14)
(0) In. w w (1)
(1)
In. and (2)
(2) (2
as W W
In- In other words, each sum layer in e is parameterized by a (semi- ceani-ynnttary matrix, thus it satisfies (U3) of unitarity. Therefore, we conclude that the tensorized circuit encoding the same upper canonical TTN is unitarity.
Going beyond TTNs with unitarity. As also stressed in $$3 and 4, tensorized circuits can represent strictly larger set of hierarchical factorizations when compared to TTNS. This is because TTNs are
38

---

Published as a conference paper at ICLR 2026
particular instance of tensorized circuits that are structured-decompee decomposaabe. Instead, non-structured- decomposable tensorized circuits can encode multiple hierarchical partitionings of variables, e.g., see the circuit in Fig. 4. Despite this crucial difference w.r.t. TTNs, the modulus squaring of non- tensorized circuit can still encode a normalized distribution via unitarity (as for Thm. 2), and it supports the tractable computation of marginals (as for Thm. 3). In particular, theoretical results in circuit complexity have shown that pruuctredddecomposse exponentially less expressive than www.sttcuuuuedddcoopssisee
sriuctureddeecompsaabbe
circuits can be ones (Pipatsrisawat and Darwiche, 2008; 2010; de Colnet and Mengel, 2021). For this reason, our contributions motivate future work aimed at developing novel TN structures different from TTNs that can possibly be more expressive, yet they support tractable marginalization and sampling via unitarity.
C RELATED WORK
The relationship between circuits and TNs. To the best of our knowledge, Ko et al. (2020) was the first work linking ideas from both TNs and from particular circuits known sum-product networks (SPNs) (Poon and Domingos, 2011), by showing an approach to approximate sparse SPNs into non- negative MPS TNs (Glasser et al., 2019). Representing popular factorization methods such as CP (Carroll and Chang, 1970; Harshman, 1970), hierarchical Tucker (Grasedyck, 2010) and MPS TNs as circuits was later highlighted in Loconte al. (2023; 2025b;a). In particular, casting TN contractions into a composition of sums and products is analogous to performing variable elimination in a graphical model (Koller and Friedman, 2009; Glasser et al., 2018), whose implementation can also be encoded by a circuit (Darwiche and Provan, 1996; Darwiche, 2003; 2009). The property-driven framework of circuits provides sufficient and necessary conditions to compose them in operations and enable the computation of quantities in closed-form, such as expectations and information -hheoretic measures (Vergari et al., 2021; Wang et al., 2024). Recently, determinism has been generalized as a property between two circuits in Wang et al. (2024) to bring complexity simplifications for exact causal inference and weighted model counting (Chavira and Darwiche, 2008). Similarly, we believe one can extend our orthogonality ($3) as a property between two circuits, thus possibly simplifying the computation of compositional operations while being possibly less restrictive than determinism. Note that these properties and operations can be translated to TNs as well, as for their close relationship with circuits ($2). Furthermore, in some cases one can efficiently restructure the hierarchical variables decomposition implicitly encoded by a direturedddecooppsablle circuit (and thus TNs) (Zhang et al., also called vtree (Pipatsrisawat and Darwiche, 2008; Kisa et al., 20u4)-thus enabling the efficient renormalization of the product of certain non-compatible circuits.
Canonical forms of TNs exploit parameterizations in terms of (semi-)unitary matrices to unlock many practical advantages (Schollwoeck, 2010). Among these. canonical forms provide simplifications for the computation of certain physical quantities (Orús, 2013), as well as the computation of marginal and conditional probabilities (Bonnevie and Schmidt, 2021) by ensuring the modeled distribution is normalized. By connecting with circuit determinism, we provide novel conditions defined in the circuit language to unlock similar advantages, namely ensuring squared PCs encode already- normalized distributions ($4) and to enable fast marginalization ($5 and App. A. Moreover, TNs expressed in canonical forms come with an enhanced numerical stability, support optimization methods aimed at avoiding vanishing and exploding gradients (Sun et al., 2020), and are amenable to advanced Riemannian optimization techniques (Hauru et al., 2020; Luchnikov et al., 2021). These practical advantages can be translated to circuits well. Furthermore, popular TNs such MPS and TTNS can be efficiently turned into a particular canonical form by iteratively performing either SVD or QR decompositions (Shi al., 2006; Orús, 2013; Cheng et al., 2019; Krämer, 2020). Our algorithm to make the parameters of a circuit (semi-) cemii)unnttrry (Thm. A.4) takes inspiration from procedures to make a TN canonical, but generalizes to tensorized circuits.
Possible choices of orthonormal functions. Depending on whether a variable is discrete or continu- ous, we have different ways to encode it with orthonormal functions. For a variable X with domain dom(X) X) = [o], any function f(X) can be expressed as Σk=1 f(k)) i.e., f can be written in terms of v Kronecker deltas (5 )iz that are orthonormal. That is, Exe(s] 62 = dRs for k. k' E [v]. For a continuous variable X, many function families can be expressed in terms of orthonormal basis. E.g., periodic functions can be represented by Fourier series (Jackson, 1941) and, under certain conti- nuity conditions, functions can be approximated arbitrarily well by finite Fourier partial sums (Jackson, 1930). Furthermore, certain families of functions can also be described in terms of orthogonal polyno-
39

---

Published as a conference paper at ICLR 2026
mials (Abramowitz et al., 1965), e.g.. Hermite functions generalize Gaussians and form orthonor- functions over all R (Roman and Rota, 1978). More in general, any set
mal basis of of linearly independent functions can be described a linear projection of set of orthonormal basis functions (see Meiburg et al. (2025, $ $A)). In practice, different choices of orthonormal functions and polynomials have been used in signal processing (Pinheiro and Vidakovic, 1997), score-hased varia- tional inference (Cai et al., 2024) and also in TNs modeling density functions (Meiburg et al., 2025). Recently orthonormal functions have been used in circuits to better scale polynomial chaos expansion (Wiener, 1938) for uncertainty quantification analysis to high dimensions (Exenberger et al., 2025).
Learning (semi- Junitry matrices. Many works in the deep learning community have investigated the challenging problem of learning on the manifold of conmi-y matrices, also called the Stiefel manifold (Absil et al., 2007). That is, there are many ways of parameterizing unitary matrices, with different advantages regarding efficiency, numerical stability and generality (Arjovsky et al., 2015; Huang et al., 2017: Bansal et al., 2018; Lezzano--assan
and Martínez-Rubic 2019), which could be employed for learning the parameters of squared PCs. More recently, Hauru et al. (2020); Luchnikov et al. (2021) proposed optimizing the parameters of MPS TNs and quantum gates using Riemmanian optimization approaches (Kochurov al., 2020).
Many models supporting tractable marginalization have been recently introduced. These include squared neural families with real complex parameters that square the 2-norm of the output of a single-hidden-layer neural network (T'uchida et al., 2023; 2024; 2025). In addition to squared PCs and mixtures thereof (Loconte et al., 2024; 2025b), other models are based squared circuit representations. These are PSD circuits (Sladek et al., 2023) inspired from PSD kernel methods (Marteau-Ferey et al., 2020; Rudi and Ciliberto, 2021), and Inception PCs generalizing structured- decomposable monotonic and squared PCs (Wang and Van den Broeck, 2025). Recently, Zellinger et al. (2026) developed expectation estimators using squared PCs in the context of variational inference and importance sampling. Furthermore, Zuidberg Dos Martires (2025) has recently unified these circuit families under a single formalism-positiv unital circuits (PUnCs)- based on concepts from quantum information theory (Nielsen and Chuang, 2010). The realization of the squaring circuit as yet another decomposable circuit is subsumed by PUnCs.
of a setneturedddccomposss However, differently from PUnCs where the layer activations are K K PSD matrices, unitary squared PC admits a more memory efficient representation by means of a circuit that does not necessarily require being squared, i.e., whose layer activations are K -ddimensional vectors instead. While PUnCs has been proposed also as a way to construct monotonic PCs, we find that ensuring either orthogonality ($3) or unitarity ($$4 and 5) is sufficient for it in wtw.ssuuuuuuuuddddoossssssees
darrucurreddeccoppsabb non-
squared PCs instead.
About expressiveness. The satisfaction of either orthogonality or unitarity allows us build squared PCs that are not structured- decoupedddeoo.psbbeee yet they still enable the tractable computation of marginals ($$3 and 5). Since popular TN structures such MPS and TTNs are encoded by diruttuee-ddecompose aimed at understanding how
circuit by construction (App. B), our contribution motivates future works wwwpecturedddecoopssbbhbbt
squared PCs are related structured- decomposable ones in terms of expressive efficiency. We believe that answering to these questions might require techniques that are different to the ones used to prove separations between circuits and squared PCs that are structured-decct decooposabee (de Colnet and Mengel, 2021; Loconte et al., 2024; 2025b). Furthermore, as shown by Agarwal and Bläser (2024) and Oliver Broadrick (2024), other instances of non-monotonic PCs that are not squared include determinantal point processes (Kulesza and Taskar, 2012; Zhang et al., 2020) and probabilistic generating circuits (Zhang et al., 2021; Harviainen et al., 2023). Understanding the relationship in terms of expressiveness also w.r.t. these other non-monotonic PCs and PUnCs (Zuidberg Dos Martires, 2025) is an interesting direction.
40

---

Published as a conference paper at ICLR 2026
D EXPERIMENTAL DETAILS
In this section, we describe all the necessary details to reproduce the results from $6.
Computational resources. To run all experiments, we use a cluster of 8 NVIDIA L40S GPUs and 8 NVIDIA RTX A6000 GPUs managed via Slurm. Every experiment uses single GPU. For the benchmark experiments (see App. D.3), we make sure all experiments run in isolation in one of the NVIDIA RTX A6000, to properly compare their time and memory requirements.
Implementation and sanity checks. Our implementations of squared unitary PCs are based on the ci wirkit library (The APRIL Lab, 2025), and extend a previous code base for squared PCs with complex parameters by Loconte et al. (2025b). Since the proposed unitary parameterization ensure squared PCs encode already- -oramaizod distributions, we do not materialize their square as another decomposable circuit in order to compute the partition function. This allows us to efficiently train squared PCs by maximum-likelihen would be too expensive memory- wise, e.g., when using Kronecker product layers. As we do not compute the partition function explicitly, how do we make sure that the squared unitary PCs in our software implementation encode a normalized distribution? Besides the theory presented in this manuscript, we employed several units tests to check that the distribution modeled by squared unitary PCs integrates to one via numerical integration on iosttaaliiiiiilizzedd circuits with Kronecker product layers, as well as in the case of As result, we have empirically corroborated that our implementation of squared unitary PCs indeed model normalized distributions up to unavoidable numerical errors due to floating point precision.
even those cases where materializing the squared PC
detprtuuureddecooosabbeee circuits having different sizes,
Squared PCs families. In the following we denote as + the class of squared PCs with complex parameters, while we use 13 to denote the class of squared unitary PCs.
D.1 CONTINUOUS INPUT FEATURES
In this section, we perform some preliminary experiments assessing the expressiveness of orthogonal input functions in the case where we have continuous variables, as discussed in App. C and $4.
Fourier input functions. To this end, for each input function in the circuit of a Fourier series with equal periodicity across input functions. That is, if we have 2 + 1 input functions-wa we assume an odd number of them-then each input function fi is of the form fa(x) x where
one single term
exp(2ri (xx+ (x))), b)),
C is the imaginary unit, k {-K, -KKKKK +1, ..... K) ]. P is the same for every k and larger than the size of dom X), and b E R is a learnable bias term. As a result, all input functions are orthogonal between then, and we make them orthonormal by normalizing them, such that they integrate out to one. We set P = 6 for the spinner dataset, and P = 12 for the spiral dataset.
Experimental setting. We take two synthetic datasets from the official code released by Loconte et al. (2025b), and train different circuit architectures to perform distribution estimation. To this end, in each iteration we sample a new batch of size 1024 from the synthetic generator function, and add noise from
+ Fourier Hadamard
+ Fourier Kronecker
1 Fourier Kronecker
Gaussian Hadamard
Fourier Hadamard
Samples
Spinner
Spiral
Figure D.I: Densities estimated by different combinations of circuit classes, product layers, and input layers (one per column), fitted with samples from two different synthetic datasets (one per row).
41

---

Published as a conference paper at ICLR 2026
centered Gaussian with standard deviation of 0.1 to avoid overfitting. We train all models for thousand iterations and apply cosine learning rate annealing to avoid instabilities at the end of training.
Circuits. We take baseline squared PC with Hadamard product layers and Gaussian in- put functions, and then test the Fourier input functions in all combinations of usual and unitary squared PCs with Hadamard or Kronecker product layers, i.e., the configurations in {+3; 1 } x X (Hadamard, Kronecker). For regular squared PCs we use Adam (Kingma and Ba, 2015) with learning rate 0.001, and our LandingPC (see App. E) for squared unitary PCs with learning rate 0.01 and X = 0.1, For every combination we use 21 input and sum units, except for = with Hadamard layers for which we keep them at 7, since otherwise the model takes too long to run.
Results. We show the estimated densities for each model combination and dataset in Fig. D.I. Despite the simplicity of the synthetic datasets at hand, we find a couple of interesting insights. First, we see that the Fourier layers do outperform the fitting (at least, qualitatively) of the identical same circuit with Gaussian input functions. Therefore, validating the expressivity claims regarding the input functions made at the end of $4. Second, we find that certain combinations work better than others. Specifically, = seem to work better when combined with Hadamard product layers, while 1. do particularly well with Kronecker layers. This is consistent with the fact that multivariate Fourier series definition considers all possible product combinations of univariate complex exponentials (Smith and Smith, 1995), i.c., similarly to Kronecker product. In addition, we later validate again in App. D.2 that Hadamard layers do not seem to work well with 11.
D.2 IMAGE DISTRIBUTION ESTIMATION
Here we describe the details for the experiments on image distribution estimation, as well as present some additional results that complement the findings from the main text.
Datasets. For the distribution estimation experiments with image data, we employ the MNIST (LeCun et al., 2010) and FashionMNIST (Xiao et al., 2017) datasets composed of, respectively, digits and clothing black-and-white pictures of size 28 x 28 px. yielding total of 784 input features. We treat each of these inputs as Categorical inputs with 256 classes (one for each of the grayscale intensity values). We randomly reserve 5 % of the training dataset split for validation.
Building decooppsadd circuit architectures. One way of casily construct smooth and decomposable (Def. 2) circuit architectures is by parameterizing via product and sum units hierar- chical partitioning of the variables scope. This hierarchical variables partitioning-Kee wwaniinng--wwnnn as region graph (Dennis and Ventura, 2012)- recursivvly splits a set of variables X into disjoint sets, which provides a "skeleton" for the circuit architecture. In other words, a region graph tells us how the product units will split their scope towards their inputs, thus guaranteeing the satisfaction of decom- posability. A region graph whose structure is constrained to be a tree is analogous to mode cluster trees as in hierarchical factorization methods (Grasedyck, 2010), which also guarantees the corre- sponding circuit is structured structured-decompper decomposable (Pipatsrisawat and Darwiche, 2008). Now, following Peharz et al. (2020b;a); Loconte et al. (2025a) we build tensorized circuits by (i) instantiating a re- gion graph and (ii) parameterizing each variables partitioning node in the region graph by adding a product layer followed by a sum layer. This guarantees that the resulting tensorized circuit is smooth ad decomposable. To build pructuredddecomposatte a tree-shaped region graph called quad-tree, which is obtained by recursively splitting the image into four even and aligned patches (Mari et al., 2023). Our baseline and unitary squared PCs (=3 and -3. respectively) are based on this region graph.
circuits over image pixel variables, we consider
Building wessrruttuuedddeooopeeee
circuit architectures. In addition to structured- decomposable squared unitary PCs, we experiment with con-structuree--ecommpoo squared PCs that satisfy our conditions (U1) to (U4) and whose structure encode multiple variable par- titionings (unlike TTNs, e.g., see Fig. 4). Differently from the quad-tree region graph, which only re- circuits, we devise new region graph by considering multiple ways
ones, i.e.,
sults in sruuctueedddcooposia to recursively split an image patch into smaller patches. Formally, given set of image pixel variables X, we partition them into two distinct ways by splitting the image either horizontally or vertically, re- sulting in partitions (Xahove, X )helow) and (Xintt Xright), respectively. We do the same recursively for each obtained image patch X Xaboves X Xhelow, Xjeft. Xright. until either the patch height or width is too small w.r.t. certain threshold (we choose our minimum patch width and height to be 8), or the
42

---

Published as a conference paper at ICLR 2026
patch is composed of single pixel. This approach of constructing region graph for images by con- sidering multiple ways of splitting the same patch recursively is similar to other ones in the circuit liter- ature (Poon and Domingos, 2011; Peharz et al., 2020a; Mari et al., 2023). However, these approaches construct one input layer for each pixel variable, whose outputs are then shared by different parts of the circuit architecture. Instead, in order ensure orthogonality between input layers over the same variable (i.e., to satisfy our conditions (UI) and (U2) and (U4)) we do not share the embedding input layers and parameterize them such that they are pairwise orthonormal. Note that, since the goal of the work is showing that one can train squared non www.sctureeddccooppaaeeo decomposaale squared unitary PCs supporting tractable marginalization, we did not focus on the construction of the region graph. We believe that our results for strractueeddecooposssee (Fig. D.2) could be further improved by exploring different ways of constructing their architecture.
squared unitary PCs
Hyperparameters. In our experiments whose results are shown in Fig. 5b and Fig. D.2, we vary the number of computational units in each input and sum layer by ensuring that all models have comparable number of trainable parameters. That is, for circuits build from the quad-tree region graph, we consider {16, 32, 64, 128, 256, 512] units in the case of squared PCs with Hadamard layers and 64,6,8 8, 10, 12, 14, 16} units in the case of Kronecker layers. For the non wewuuctureddecooppseee squared PCs with Kronecker layers, we also consider {18, 20, 22] units per layer. For the baseline squared PCs, we tune the models where consider Adam with a learning rate of 0.01 (which were the best hyperparameters found by Loconte et al. (2025h)), as well as SGD with learning rates 0.01 and 0.001. For squared unitary PCs, consider LandingPC* with learning rate of 0.05 and LandingSGD with a momentum of 0.9 and learning rates 0.01 and 0.001, where we fix X = 0.1 always. Here, an asterisk denotes LandingSGD with one both modifications described in App. Finally, for unitary circuits we also consider LandingSGD as described by Ablin et al. (2024) and the same hyperparameter as described before for LandingSGD".
Additional settings. To provide a broader view on the design choices made in our experimental section, we expand in Fig. D.2 the plot from Fig. 5b with more combinations of product layers and optimizers. The first observation is that the performances of baseline squared PCs heavily relies on the optimizer: despite testing various learning rates, we could not obtain satisfactory results using SGD as the optimizer. Second, we observe that indeed squared unitary PCs do not play well with Hadamard product layers: for every optimizer and circuit size we tried, their performance is significantly worse that the best models. Finally, we the importance of the adjustments made to the Lan algorithm (Ablin and Peyré, 2022) described in App. E: while the original algorithm (LandingSGDD does not perform well, by projecting back to the Stiefel manifold each time matrix goes too far from it (LandingSGD")) we significantly improve their performance, yet they struggle with the larger circuits. Then, by replacing the Euclidean gradient in the algorithm (LandingPC*) we strictly improve the performance of the trained unitary circuits in every setting we tested.
Table D.I: Distribution estimation performances of squared PC and unitarity squared PC on the MNIST dataset (LeCun et al., 2010) as we increase the number of layer units. Performance shows mean and standard deviation across three random initializations.
Circuit
Product layer
# params (x10%
Test performance (bpd)
class
Optimizer
# units
16
6.5577
1.3071 # 0.0105
32
13.3858
1.2676 # 0.0068
64
27.8529
1.2518 # 0.0033
+
Hadamard
Adam
128
60.0312
1.2337 # 0.0011
256
137.3640
1.2147 # 0.0015
512
343.9340
1.1991 + 0.0004
4
2.1353
1.3112 # 0.0001
6
6,4260
1.2567 + 0.0003
LandingPC
8
20.1339
1.2328 # 0.0005
Kronecker
10
55.6461
1.2201 + 0.0005
(see App. E)
12
133.2764
1.2064 # 0.0005
14
283.2467
1.1998 0.0015
16
547.6680
1.1923 0.0007
43

---

Published as a conference paper at ICLR 2026
MNIST
MNIST
13
Kronecker LandingPC (non-str-dec)
4.4
-
12
Kronecker LaudingPC
1.6
4.2
Hadamard
LandingPC'
test bpd
1.5
4.0
1
Hadamard
LandingSGD"
1.4
Kronecker LandingSGD"
3.8
1
Kronecker LandingSGD
1.3
3.6
43 Hadamard Adam
1.2
+ Hadamard SGD
3.4
10
10
107
10
# parameters
Figure D.2: Image distribution estimation experiment from Fig. 5b with additional settings. Specifi- cally, we show normal and unitary squared PCs using Hadamard or Kronecker product layers, and us- ing different optimizers. An asterisk denotes LandingSGDD with one both modifications described in App. E, referring to the latter as LandingPC. The plot is computed over three random initializations.
Table D.2: Distribution estimation performances of squared PC and unitarity squared PC on the FashionMNIST dataset (Xiao et al., 2017) as we increase the number of layer units. Performance shows mean and standard deviation across three random initializations.
Circuit
Product layer
# params (x10%)
Test performance (bpd)
class
Optimizer
# units
16
6.5577
3.5451 = 0.0020
32
13.3858
3.4689 = 0.0019
64
27.8529
3.4479 # 0.0008
+
Hadamard
Adam
128
60.0312
3.4545 # 0.0044
256
137.3640
3.4349 0.0024
512
343.9340
3,4199 = 0.0012
4
2.1353
3,6700 # 0.0008
6
6,4260
3.5325 = 0.0005
LandingPC (see App. E)
8
20.1339
3,4651 = 0.0008
.18
Kronecker
10
55.6461
3,4306 # 0.0016
12
133.2764
3.4148 0.0007
14
283.2467
3.4105 # 0.0009
16
547.6680
3.4128 0.0028
D.3 BENCHMARKING SQUARED PCS
In this section, we briefly describe the experimental details regarding the benchmark results plotted in Fig. 5a, well provide the quantitative results said experiment, see Tab. D.3.
Experimental setting. We keep the experimental setting as close as possible to that from App. D.2, meaning that we use the same circuit architectures as there. To increase the number of parameters, we increase the number of units in input and sum layers, as we report in Tab. D.3. To provide reliable timings and peak GPU memory measurement, we simulate single optimization step (or training iteration) that minimizes the negative log- log-likelihood computed over one batch of data points. That is, we measure time and peak GPU memory required to evaluate the input and inner layers, as well as to perform the backpropagation step and parameters update using particular optimizer (SGD, Adam and LandingPC (App. E)). Finally, we average the results over 50 training iterations and perform 10 initial burn-in iterations to discard initial artifacts and overheads.
Results. In Tab. D.3 we report time and peak GPU memory measurements illustrated in Fig. 5a in tabular format, for both squared PCs (++) and squared unitary PCs (13). As discussed in $6, the unitary parameterization in squared PCs permits us to not materialize the squared PC as a decomposable circuit in order compute the partition function (as it is fixed to required by the
44

---

Published as a conference paper at ICLR 2026
negative log- li-likelihood loss. As such, the unitary parameterization together with the LandingPC optimizer (App. E) brings computationally cheaper parameter updates, when compared to baseline squared PCs learned using either SGD or Adam optimizer.
Table D.3: Time and memory consumption different combinations of squared PCs and optimizers for single training iteration. We find that squared unitary PCs are faster and use less memory than their counterparts, even they employ Kronecker product layers.
Circuit class
Product layer
# params (x10%)
GPU Mem.
Time (ms/iter)
Optimizer
# units
(GiB)
0.0873
0.0889
0.0366
16
0.3492
0.1647
0.0374
1.3968
0.3348
0.0371
Hadamard
SGD
64
5,5870
0.7497
0.0337
128
22.3479
1.8779
0.0443
256
89.3914
5.3277
0.1285
512
357.5649
17.0012
0.5226
8
0.0873
0.0893
0.0366
0.0349
0.1660
0.0374
32
1.3968
0.3400
0.0375
-
Hadamard Adam
5.5870
0.7705
0.0375
128
22.3479
1.9611
0.0459
256
89.3914
5.6607
0.1337
512
357.5649
18.3332
0.5426
0.0873
0.0866
0.0170
16
0,3492
0.1555
0,0171
LandingPC (see App. E)
32
1.3968
0.2984
0.0173
13
Hadamard
64
5.5870
0.6040
0.0199
128
22.3479
1.2953
0.0303
256
89.3914
2.9979
0.0737
512
357.5649
11.0130
0.2666
11,2108
0,8895
0.0364
LandingPC
10
34.1124
1.9109
0.0508
Kronecker
12
84.7711
3.7685
0.0848
(see App. E)
14
183.0993
6,9384
0.1695
16
356.8435
12.0623
0,2923
E THE FAMILY OF LANDING ALGORITTMS
Here, briefly describe the family of Landing optimization algorithms used to learn semi-unitary matrices, as well as the modifications we performed to train squared unitary PCs. Refer to the original works to full description of the LandingSGD algorithm, its variants, well as their theoretical properties (Ablin and Peyré, 2022; Ablin et al., 2024).
Say that we want to optimize one of the matrices W E gnxp with > p of circuit, constraining W to lie in the Stiefel manifold, i.c. such that W w Ip. The LandingSGD algorithm (Ablin and Peyré, 2022) will then produce sequence of iterates as follows:
W = W. - nA(W.)
(15)
where A is the landing field defined as
(W) == grad (W) + WW
(16)
and where (W) skew V F(W) W is the relative gradient (i.e. gradient in the tangent space of the non non-singular matrix manifold with respect to multiplicative noise, rather than additive)
of the loss function trying optimize. The second term of the last equation can also be
45

---

Published as a conference paper at ICLR 2026
Algorithm E.1 The original LandingSGD algorithm (Ablin and Peyré, 2022).
J. a momentum buffer A (initiated as V(()). and iteration Hyper-parameters Learning rate 7,, momentum 7, weight decay t,, dampening v, attraction strength X, safe step 6, stabilization steps T.
Input: The matrix its gradient (W(W).
1: let g = Vf(W) + W
> Weight decay
2: let gW) skew (V/(W)
Relative gradient (in the manifold)
y then
4: let A - 7 + (1 - u)g
Momentum
5: let = A
6:
use Nesterov momentum then
7:
let V/(W) + A
8:
let VW) (W W I,)
Normal direction (towards the manifold) Compute safe step size
9:
> 0 then
10:
let d | - 1,ll
11:
let 1 (.V
12:
let 17" = (-Ad(d- - 1) (d 1)2 max(0, - d))/(r² - 1)
13:
let 1) = min(n" .))
14:
let W = - - -ng
15:
if mod T 0 then
16:
let W (W W) W
Project back to the manifold b Project to the tangent space of W
17:
let A = A - WA W
seen as the gradient of the distance of the matrix W to the manifold, VW((W, where N(W) = I/| W - I1ll In turns out that the two terms of the sum above are actually orthogonal, and thus the landing algorithm can understood as the combination of an f-informed force (the relative gradient) and an attractive force which pulls the iterates towards the Stiefel manifold.
From the base algorithm introduced by Ablin and Peyré (2022), and described in Alg. E. Ablin et al. (2024) generalize it and introduce its stochastic version, LandingSGD, as well as another variant for variance reduction. In order to make the algorithm work on our setting, we took our own spin and modified LandingSGD. Namely, gradient V)( to be the one given by the result of combining VectorAdam (Ling et al., 2022) and RAdam (Liu al., 2019); and (ii) project the gradient back to the manifold if find their distance to exceed the same threshold as the one given to the LandingSGD algorithm. To distinguish from the original algorithm, in this manuscript we refer the final algorithm after the aforementioned adjustments as LandingPC. The change of gradient does not break the theoretical guarantees of landing algorithms since the generalized analysis by Ablin al. (2024) works long grad (W) is kew-syymmetric, which is still the case if we replace Vf(W).
introduced two main changes: (i) we replace the Euclidean
46


Reviews:
[{"review_id": "AoFGOs6BJM", "reviewer": "Reviewer_zFDG", "summary": "This paper proposes new structural and parameterization conditions for squared tensor networks and squared probabilistic circuits that enable linear-time marginalization without losing expressiveness. Prior squared circuits incur quadratic complexity for computing marginals or partition functions, limiting scalability. The authors introduce orthogonality and unitarity constraints on circuits—generalizing canonical forms in tensor networks—to achieve efficient normalization and marginalization even for architectures that do not map to classical tensor-network forms. Experiments demonstrate that these unitary squared circuits are faster and more memory-efficient, while matching or exceeding the performance of unconstrained models.", "questions": "Please see the weakness above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Very well-written paper\n\n2. Novel connection between tensor networks and probabilistic circuits. The paper conceptually unifies canonical forms in tensor networks with determinism in probabilistic circuits and introduces orthogonality as a more general tool for tractable inference .\n\n3. Theoretical contributions with clear practical implications. Orthogonality and unitarity are shown to guarantee O(|c|) marginalization in squared circuits instead of O(|c|²), and results extend to non-structured-decomposable circuits.", "weaknesses": "1. Experiments cover MNIST-style tabular/image datasets; evaluation on more complex tasks (e.g., high-dimensional continuous density estimation, conditional queries, or sampling quality metrics) would strengthen the real-world significance.\n\n2. The core intuition behind orthogonality vs determinism and its practical implications could be communicated more clearly for a broader audience.\n\n3. Orthogonality/unitary constraints often complicate optimization; although addressed here, more ablation on optimizer sensitivity would be valuable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hULEDSafbX", "reviewer": "Reviewer_kdCq", "summary": "This work builds on previous work that investigates the relation between Tensor Networks and Squared Probabilistic Circuits, two computational frameworks developed in different communities. The Matrix-Product State representation of Tensor networks have been previously shown to be equivalent to structured and decomposable circuits with negative weights. Both Tensor networks and Circuits with negative weights can be constrained in order to satisfy probability distributions by squaring and renormalization. As previously noted, Squared Probabilistic Circuits are more general than MPS Tensor Networks, which makes the connection interesting. In this work, the authors investigate the orthogonality property often used by MPS to decrease the overhead of renormalization and squaring from quadratic to linear. That property is lacking from the Probabilistic Circuits literature. Since a direct adaptation of orthogonality leads to squared Probabilistic Circuits with a relatively simple structure, the authors propose a relaxation of the property, called Z-orthogonality (inspired by the concept of X-determinism in PCs). They show how the property can be exploited to speed up marginal computations while increasing flexibility of the model. Experiments in simple tasks (MNNIST and FASHION MNIST) show that their approach can effectively learn good representations and improve scalability.", "questions": "All in all, I think this is a solid work, although I didn't have the time to check all the material in the appendices. \n\nThe analysis of RQ2 states that \"squared unitary PCs gracefully scale, matching the performance of their baseline counterparts.\" I could not understand from the plots in Figure 4 how one can reach that conclusion.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Interesting discussion, connecting topics studied in different communities\n- Well-written\n- Promising approach to learning high-dimensional probability distributions with tractable marginalization", "weaknesses": "- Empirical analysis is very preliminary\n- Very long text (including appendices), difficult to revise given time constraints of a conference", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1zoK6ZQIma", "reviewer": "Reviewer_J6uk", "summary": "The paper presents novel results for squared Probabilistic Circuits that can represent expressive distributions. In particular, inspired by the applications of determinism in tractable probabilistic models, the proposed work introduces a new concept called orthogonality as a relaxed version of determinism in squared PCs. For a PC that is orthogonal inference they show that inference is tractable (partition function is computed in linear time).  They develop an approach to build orthogonal circuits. However, since such a circuit requires decomposability it is quite restrictive. Instead, they define conditions to construct circuits (called unitary circuits) over multiple layers which does not require decomposability. They develop a marginal inference approach for unitary circuits and prove the inference complexity for such circuits. The experiments show the efficiency of unitary circuits and their expressive power.", "questions": "Are squared PCs generalizable across different types of problems? Is the limiting factor learning them at larger scales?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Strengths\n+ Provides several novel previously unknown results in the context of probabilistic circuits, i.e. a new class of circuits that is expressive and tractable\n+ The connection between determinism to orthogonality seems to be unique and perhaps will offer other research directions\n+ Guarantees on inference complexity with unitary circuits being in normalized form\n+ Paper is high on rigor with proofs for all the key results", "weaknesses": "- While the paper makes a strong contribution in probabilistic circuits with the introduction of unitary circuit learning and inference, it does not show why unitary circuits are better than existing tractable probabilistic models. The baseline comparison is with variants of squared PCs but perhaps the benefits of squared PCs over other approaches is not as clear. Maybe this is an empirical aspect that seems missing in the paper. \n- The choice of experiments and benchmarks was not so clear (MNIST and FashionMNIST). More generally, from the comments in lines 459-463 it seems like this approach is hard to scale for other general problems? This may be a limiting factor for broader use.\n\nIn general, the paper is strong in theory and presents novel theoretical results in the context of squared PCs. The empirical evaluation seems a bit weaker.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6jNbGHu5dz", "reviewer": "Reviewer_eo4A", "summary": "The paper introduces a novel framework for efficiently performing marginalization in squared tensor networks (TNs) and squared circuits, which are models for distribution estimation. While squared TNs and circuits offer strong expressive power and closed-form marginalization, the squaring operation typically increases computational complexity, making inference expensive. The authors address this challenge by proposing a new parameterization strategy based on unitary matrices and deterministic structure, inspired by canonical forms in tensor networks and the tractability of maximization in deterministic circuits. Unlike traditional canonical forms, which are limited to tensor network structures, this approach extends to general circuit representations, including those that do not correspond to standard TN factorizations.", "questions": "Please refer to the section on weaknesses.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The paper makes an original contribution by bridging two distinct paradigms in probabilistic modeling—TNs and circuit-based representations—through a unified, structure-aware parameterization strategy. While prior work has explored canonical forms for TNs, this paper extends such ideas to arbitrary circuits, including those that do not correspond to any known TN factorization.\n- The key insight, parameterizing squared circuits using unitary matrices and determinism to enable closed-form marginalization, is both elegant and novel. It draws inspiration from canonical forms in tensor networks and the tractability of maximization in deterministic circuits.\n- The paper demonstrates strong theoretical rigor. The main result, a sufficient condition under which squared circuits admit closed-form marginalization via unitary parameterization, is formally stated and proved.\n- The experimental evaluation is well-designed and methodologically sound. The authors test on standard distribution estimation benchmarks. The proposed parameterized circuits achieve competitive or superior log-likelihoods compared to unconstrained models.\n- Marginalization is faster, and training converges more rapidly due to better conditioning of the optimization landscape.", "weaknesses": "- The paper claims that its method enables efficient marginalization in non-TN factorizations, but the empirical comparison is limited to a few baselines. There is no direct comparison with other tractable circuit families.\n- The paper proves that unitary parameterization leads to closed-form marginals, but the practical utility depends on whether such parameterizations can be optimized effectively. Unitary matrices are highly constrained, and optimization over this manifold is known to be challenging.\n- The paper does not discuss gradient flow on the Stiefel manifold or the risk of vanishing gradients in deep unitary circuits.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)