Expressive power of tensor-network factorizations for probabilistic modeling, with applications from hidden Markov models to quantum machine learning

1 Introduction

• The paper situates tensor networks as high-dimensional representations whose expressive power can be analyzed rigorously, building on applications in compression, physical simulation, and machine learning.It proceeds from model definitions and their HMM and quantum-circuit connections to expressive-power results, learning algorithms, and numerical experiments.Source: §1 · pp. 1–2
• The study examines non-negative tensor networks and Born machines as models of discrete multivariate probability distributions.Born machines represent a probability mass function as the absolute value squared of a real- or complex-tensor network; they also arise naturally from quantum-mechanical measurement probabilities.Source: §1 · p. 2
• Tensor-train/MPS models are emphasized because they have tractable likelihoods, efficient learning algorithms, and support rigorous theoretical analysis.In this setting, non-negative tensor networks encompass HMMs, while Born machines include models arising from fixed-depth local quantum circuits; the results also apply to tree-structured networks.Source: §1 · p. 2
• Families of probability distributions exhibit unbounded separations in resource requirements, so neither HMMs nor Born machines are generally preferable to each other.The paper also proves that complex tensors can sometimes yield an arbitrarily large reduction in network parameter count compared with real tensors.Source: §1 · p. 2
• LPS has provably better expressive power than the previously introduced models, and experiments on random distributions and realistic datasets support considering it over HMMs and Born machines.The paper frames these experiments as evidence that its theoretical findings are relevant in practice.Source: §1 · p. 2

2 Tensor-network models of probability distributions

• A probability mass function over N discrete variables with d possible values per variable is represented as a non-negative tensor whose entries sum to one.The number of entries grows exponentially with N, motivating compact factorizations when the variables have exploitable structure.Source: §2 · p. 2
• The section defines tensor networks by contracting smaller tensors and models a probability distribution as a non-negative tensor divided by its normalization factor.For the considered networks, the normalization factor can be evaluated efficiently.Source: §2 · p. 3
• The three factorizations are MPS, Born machines, and locally purified states, with the latter two representing tensors through squared amplitudes or contracted purification indices.MPS constituent tensors may be non-negative, real, or complex; Born machines use real or complex tensors, while LPS adds a purification dimension μ alongside the bond indices.Source: §2 · p. 3
• TT-rank, Born-rank, and puri-rank are defined as the minimal ranks needed for the corresponding representations, with puri-rank minimized over purification dimension.For two-index tensors, these specialize respectively to non-negative rank, conventional matrix rank, real or complex Hadamard square-root rank, and positive semidefinite rank.Source: §2 · p. 4, Table 1 · p. 4
• The section compares the sets of non-negative tensors representable by each network: these sets grow with rank, and at arbitrarily large rank each network can represent any such tensor.The comparison is characterized by the ranks required by different factorizations.Source: §2 · p. 4

3 Relationship to hidden Markov models and quantum circuits

• Fixed-depth local quantum circuits correspond to Born machines of constant Born-rank, while HMMs with a constant number of hidden units per variable correspond to non-negative MPS of constant TT-rank.The correspondences mean expressive-power results for the tensor networks also apply to the associated models.Source: §3 · p. 4

3.1 Hidden Markov models are non-negative matrix product states

• An HMM with r hidden states per variable has an equivalent non-negative MPS of TT-rank r, formed from its transition and emission probabilities.Conversely, a non-negative MPS of TT-rank r has an equivalent HMM with hidden-variable dimension at most min(dr, r^2); a different HMM graph can achieve dimension r.Source: §3.1 · p. 4, Figure 1 · p. 5

3.2 Quantum circuits are Born machines or locally purified states

• The amplitudes of a 2-local depth-D circuit on a line can be represented by an MPS with complex TT-rank less than dD+1, and Born-rule measurement probabilities give its Born-machine distribution.Thus expressive-power results for Born machines also apply to local quantum circuits treated as probabilistic models.Source: §3.2 · p. 5
• Treating every second qudit as hidden yields the locally purified state correspondence for circuits with alternating visible and hidden qudits.Measurements on the visible qudits sample from the LPS obtained by the specified contractions.Source: §3.2 · pp. 5–6

4 Expressive power of tensor-network representations

• The ranks satisfy several universal inequalities, including TT-rank_R≥0 ≥ puri-rank_R and Born-rank_R ≥ Born-rank_C, while TT-rank_R = TT-rank_C.The inequalities are Proposition 1’s inclusion relationships between representable sets.Source: §4 · p. 6
• Proposition 2 shows that these inequalities can be strict, while other representation pairs admit examples in both rank orderings; TT-rank_R≥0 can be smaller than Born-rank_C.The last inequality is the section’s highlighted new matrix example.Source: §4 · p. 6, Table 2 · p. 7
• For many representation pairs, no rank bound depends only on the other representation’s rank: as binary-variable count grows, one rank can stay constant while the other diverges.Proposition 3 reports these cases for families of probability distributions.Source: §4 · p. 7, Table 3 · p. 7
• Some separations grow at least as Ω(N): constant TT-rank_R=3 can coexist with puri-rank_C=Ω(N), and constant TT-rank_R≥0=2 can coexist with Born-rank_R ≥ π(2N+1).Other families have constant Born-rank 2 but TT-rank_R≥0 ≥ N, or constant complex Born-rank 2 but real Born-rank ≥ N.Source: §4 · p. 7
• The rank gaps arise from cancellation in real MPS, differences between distribution and square-root ranks, and how real and imaginary parts combine under modulus squaring.Real LPS with purification dimension 2 include complex Born machines.Source: §4 · pp. 7–8
• The proof strategy turns matrix-rank separations into tensor-rank separations by unfolding a matrix into a tensor network while preserving the relevant rank gap.A matrix of dimension 2^N × 2^N is unfolded for 2N binary variables; arbitrary matrices can be embedded as submatrices first.Source: §4 · p. 8
• LPS puri-ranks are bounded below by the other ranks, supporting their preference over non-negative MPS and Born machines; exact-rank results leave approximate representations open.Complex Born machines can also reduce parameter counts arbitrarily relative to real ones; the stated comparisons extend to tree-structured factorizations.Source: §4 · p. 8

5 Learning algorithms

• The models admit efficient learning algorithms, and training from samples minimizes negative log-likelihood using mini-batch gradient descent.For complex tensors, the procedure uses Wirtinger derivatives with respect to conjugated tensor elements.Source: §5 · p. 8
• For LPS, training computes each example’s tensor value and derivative alongside the normalization and its derivative through network contractions.For purification dimension µ and puri-rank r, the stated contraction costs O(dµr^3N); Born machines use the same algorithm as LPS with µ=1.Source: §5 · p. 9
• The models also support efficient marginals, correlation functions, and exact sampling, while MPS_R≥0 training uses a variation of the LPS algorithm.HMMs can instead use expectation-maximization; Born machines and LPS require different algorithms because they use real or complex tensors.Source: §5 · p. 9
• For a given non-negative tensor, compression minimizes KL divergence to a normalized tensor-network model; more efficient BM and LPS factorization algorithms are left open.The tensor to compress has exponentially many parameters in N, so the paper notes this route is practical only for a small number of variables.Source: §5 · p. 9

6 Numerical experiments

• The experiments examine both approximation of distributions from samples and compression of given non-negative tensors, using algorithms described earlier.The code, data sets, and hyperparameter choices are reported in the supplementary material and repository.Source: §6 · p. 9

6.1 Random tensor factorizations

• Complex Born machines and real or complex LPS generically approximate random tensors better than MPS or real Born machines, at fixed rank and fixed real parameter count.Figure 3 reports mean minimum error over 50 random tensors for a 20 × 20 matrix and an 8-binary-variable tensor; LPS uses purification dimension 2.Source: Figure 3 · p. 10, §6.1 · p. 10

6.2 Maximum likelihood estimation on realistic data sets

• On all realistic data sets, Born machines and LPS significantly improve negative log-likelihood over MPS_R≥0 at the same rank, while HMM and MPS_R≥0 perform similarly.The models are trained on complete categorical data without regularization; the comparison also includes an HMM trained with Baum-Welch and a learned Bayesian network without hidden variables.Source: §6.2 · p. 10

7 Conclusion

• In generic settings, LPS should be preferred over both hidden Markov models and Born machines.The paper also proves that complex tensors can yield an unbounded expressive advantage over real tensors in particular architectures.Source: §7 · p. 10
• Figure 4 compares maximum-likelihood estimation by tensor networks, HMMs, and Bayesian networks without hidden units across six data sets.The caption identifies the data sets but does not report the comparison's outcomes.Source: Figure 4 · p. 11
• The formal relationship between LPS, Born machines, and quantum circuits provides a foundation for developing and analyzing quantum machine-learning algorithms for near-term devices.Source: §7 · p. 11

• The paper's topic is the expressive power of tensor-network factorizations for probabilistic modeling.Source: Supplementary material · p. 15

• The arXiv record identifies the paper as 1907.03741v2, dated 29 November 2019, and names Ivan Glasser, Ryan Sweke, Nicola Pancotti, Jens Eisert, and J. Ignacio Cirac.The listed affiliations are Max-Planck-Institut für Quantenoptik, MCQST, Dahlem Center for Complex Quantum Systems, and Freie Universität Berlin.Source: with applications from hidden Markov… · p. 15

1.1 Non-negative MPS are HMM

• A non-negative MPS can be converted to an equivalent HMM with hidden-state dimension r′, while another graph choice can yield dimension r.The construction uses an exact non-negative decomposition, with r′ ≤ min(dr, r^2).Source: §1.1 · p. 15, Figure S1 · p. 16

1.2 Local quantum circuits are Born machines

• A depth-D circuit of 2-local gates yields a Born machine with Born-rank dD+1 and an MPS representation with TT-rank below dD+1.Source: §1.2 · p. 17

1.3 Local quantum circuits with ancillas are locally purified states

• With alternating system and ancilla qudits, a depth-D circuit yields an LPS of puri-rank rD+1, where r = min(d, µ).The circuit output has an MPS representation with TT-rank below rD+1; measuring the system qudits gives the LPS probability distribution.Source: §1.3 · p. 18

2 Proofs on the expressive power of tensor networks

• At equal rank, the stated inclusions hold between non-negative TT, real and complex TT, Born, and purified representations, while real and complex TT ranks are equal.In particular, a real Born machine is a locally purified state with purification dimension 1.Source: §2 · p. 19
• Proposition 2 shows that every stated inclusion can be strict and that for other representation pairs, examples exist in both rank orderings.The lemmas provide non-negative matrix witnesses for these comparisons.Source: §2 · p. 19
• Matrix witnesses show non-negative rank can exceed real TT rank, TT rank can be below Born rank, and non-negative TT rank can exceed several Born and purified ranks.A separate witness has real TT rank below real Born rank and real Born rank above real purified rank.Source: §2 · p. 20
• Other witnesses place real TT below real and complex purified ranks, real purified rank above complex purified rank, and complex purified rank below complex Born rank.The pentagon slack matrix has real and complex purified rank 4, while another witness has real positive-semidefinite rank 3.Source: §2 · pp. 20–21
• Real TT rank is at most the square of complex purified rank, and real purified rank is at most twice complex Born rank.The squared bound also holds using real purified rank, real Born rank, or complex Born rank in place of complex purified rank.Source: §2 · pp. 22–23
• For increasing matrix dimension d, cited families of non-negative matrices exhibit rank 3 with puri-rankC ≥ Ω(log d), TT-rankR≥0 = 2 with Born-rankR = d, and Born-rankC = 2 with Born-rankR = d.Source: §2 · p. 23
• An unfolding construction embeds matrix witnesses into tensors over 2N binary variables, preserving the chosen rank and making the matrix a submatrix of the central bipartition.Thus the matrix rank lower bound transfers to the corresponding tensor rank.Source: §2 · pp. 24–25
• Applying the unfolding to the matrix families proves the “No” overhead entries for distributions over many binary variables, while the “No∗” entries remain conjectures.Those conjectures would follow from a family with constant non-negative rank but unbounded complex Hadamard square root rank.Source: §2 · p. 25

Proposition 4

• With TT-rank_R=3, some non-negative tensors require puri-rank_C=Ω(N), Born-rank_R/C=Ω(N), and TT-rank_R≥0=Ω(N).Alternative unfolding techniques are needed for the asymptotic separations in Propositions 4–6.Source: §2 · p. 25

Proposition 5

• Constant TT-rank_R≥0=2 can coexist with Born-rank_R≥π(2^N+1), where π(x)∼x/log(x).A prime matrix submatrix supplies the square-root-rank lower bound for the Born representation.Source: §2 · pp. 25–26

Proposition 6

• Constant Born-rank_R=2 can coexist with TT-rank_R≥0≥N for non-negative tensors over 2^N binary variables.The proof uses a squared linear Euclidean matrix whose non-negative rank exceeds N.Source: §2 · p. 26

Proposition 7

• Born-rank_C=2 can coexist with Born-rank_R≥N for non-negative tensors over 2^N binary variables.The proof relies on matrices with complex square-root rank 2 but real square-root rank N.Source: §2 · p. 26

3.1 Learning algorithms for MPSR≥0

• Non-negative MPS normalization is contracted left to right, with intermediate results reused to compute normalization and sample-probability gradients.The procedure computes derivatives for both the normalization and the tensor evaluated at an observed training example.Source: §3.1 · pp. 26–27

3.2 Tensor factorizations

• The tensor-factorization models are optimized using KL divergence and limited-memory BFGS, while the MPSR comparison uses a penalty to enforce non-negativity.That constraint is difficult to satisfy and may prevent convergence to the global minimum; results are not significantly modified when using the 2-norm instead of KL divergence.Source: §3.2 · p. 27

3.3 Generalization performance

• The generalization experiment uses biofam, a sequence of 16 family-life-state variables with eight possible values, and selects test models using validation performance.The study uses 1,000 training, 500 validation, and 500 test examples; results are averaged over 20 random initializations, with standard deviations shown in Figure S2.Source: §3.3 · pp. 27–28, Figure S2 · p. 27
• On biofam, Born machines and LPS outperform HMM and non-negative MPS at small ranks with lower initialization variance; non-negative MPS improves over HMM at larger ranks.The training-set differences between HMM and non-negative MPS are small, while their test-set differences are more substantial.Source: Figure S2 · p. 27, §3.3 · p. 28