{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,12]],"date-time":"2025-09-12T18:08:31Z","timestamp":1757700511945,"version":"3.38.0"},"reference-count":48,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T00:00:00Z","timestamp":1740528000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>The matrix rank and its positive versions are robust for small approximations, i.e. they do not decrease under small perturbations. In contrast, the multipartite tensor rank can collapse for arbitrarily small errors, i.e. there may be a gap between rank and border rank, leading to instabilities in the optimization over sets with fixed tensor rank. Can multipartite positive ranks also collapse for small perturbations? In this work, we prove that multipartite positive and invariant tensor decompositions exhibit gaps between rank and border rank, including tensor rank purifications and cyclic separable decompositions. We also prove a correspondence between positive decompositions and membership in certain sets of multipartite probability distributions, and leverage the gaps between rank and border rank to prove that these correlation sets are not closed. It follows that testing membership of probability distributions arising from resources like translational invariant Matrix Product States is impossible in finite time. Overall, this work sheds light on the instability of ranks and the unique behavior of bipartite systems.<\/jats:p>","DOI":"10.22331\/q-2025-02-26-1649","type":"journal-article","created":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T16:14:56Z","timestamp":1740586496000},"page":"1649","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":1,"title":["Border Ranks of Positive and Invariant Tensor Decompositions: Applications to Correlations"],"prefix":"10.22331","volume":"9","author":[{"given":"Andreas","family":"Klingler","sequence":"first","affiliation":[{"name":"Institute for Theoretical Physics, Technikerstr. 21a, A-6020 Innsbruck, Austria"},{"name":"Faculty of Mathematics, Oskar-Morgenstern-Platz 1, A-1090 Wien, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tim","family":"Netzer","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Technikerstr. 13, A-6020 Innsbruck, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gemma","family":"De les Coves","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Physics, Technikerstr. 21a, A-6020 Innsbruck, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2025,2,26]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"D. Bini, G. Lotti, and F. Romani. ``Approximate solutions for the bilinear form computational problem&apos;&apos;. SIAM J. Comput. 9, 692\u2013697 (1980).","DOI":"10.1137\/0209053"},{"key":"1","doi-asserted-by":"publisher","unstructured":"J. M. Landsberg. ``Tensors: Geometry and applications&apos;&apos;. Volume 128. American Mathematical Soc. (2011).","DOI":"10.1090\/gsm\/128"},{"key":"2","doi-asserted-by":"publisher","unstructured":"T. Barthel, J. Lu, and G. Friesecke. ``On the closedness and geometry of tensor network state sets&apos;&apos;. Lett. Math. Phys. 112, 72 (2022).","DOI":"10.1007\/s11005-022-01552-z"},{"key":"3","doi-asserted-by":"publisher","unstructured":"M. Christandl, A. Lucia, P. Vrana, and A. H. Werner. ``Tensor network representations from the geometry of entangled states&apos;&apos;. SciPost Phys. 9, 1\u201335 (2020).","DOI":"10.21468\/SCIPOSTPHYS.9.3.042"},{"key":"4","doi-asserted-by":"publisher","unstructured":"J. M. Landsberg, Y. Qi, and K. Ye. ``On the geometry of tensor network states&apos;&apos;. Quantum Inf. Comput. 12, 346\u2013354 (2012).","DOI":"10.26421\/qic12.3-4-12"},{"key":"5","doi-asserted-by":"publisher","unstructured":"V. De Silva and L. H. Lim. ``Tensor rank and the ill-posedness of the best low-rank approximation problem&apos;&apos;. SIAM J. Matrix Anal. Appl. 30, 1084\u20131127 (2008).","DOI":"10.1137\/06066518X"},{"key":"6","doi-asserted-by":"publisher","unstructured":"J. M. Landsberg and Mateusz Micha\u0142ek. ``Abelian tensors&apos;&apos;. Journal de Math\u00e9matiques Pures et Appliqu\u00e9es 108, 333\u2013371 (2017).","DOI":"10.1016\/j.matpur.2016.11.004"},{"key":"7","doi-asserted-by":"publisher","unstructured":"J. Zuiddam. ``A note on the gap between rank and border rank&apos;&apos;. Linear Algebra Appl. 525, 33\u201344 (2017).","DOI":"10.1016\/j.laa.2017.03.015"},{"key":"8","doi-asserted-by":"publisher","unstructured":"M. Christandl, F. Gesmundo, D. Stilck Fran\u00e7a, and A. H. Werner. ``Optimization at the boundary of the tensor network variety&apos;&apos;. Phys. Rev. B 103, 1\u20139 (2021).","DOI":"10.1103\/PhysRevB.103.195139"},{"key":"9","doi-asserted-by":"publisher","unstructured":"P. Comon, L.-H. Lim, Y. Qi, and K. Ye. ``Topology of tensor ranks&apos;&apos;. Adv. Math. 367, 107128 (2020).","DOI":"10.1016\/j.aim.2020.107128"},{"key":"10","doi-asserted-by":"publisher","unstructured":"C. Beltr\u00e1n, P. Breiding, and N. Vannieuwenhoven. ``The average condition number of most tensor rank decomposition problems is infinite&apos;&apos;. Found. Comp. Math. 23, 433\u2013491 (2023).","DOI":"10.1007\/s10208-022-09551-1"},{"key":"11","doi-asserted-by":"publisher","unstructured":"G. De las Cuevas, T. S. Cubitt, J. I. Cirac, M. M. Wolf, and D. P\u00e9rez-Garc\u00eda. ``Fundamental limitations in the purifications of tensor networks&apos;&apos;. J. Math. Phys. 57, 071902 (2016).","DOI":"10.1063\/1.4954983"},{"key":"12","doi-asserted-by":"publisher","unstructured":"M. Kliesch, D. Gross, and J. Eisert. ``Matrix-product operators and states: NP-hardness and undecidability&apos;&apos;. Phys. Rev. Lett. 113, 160503 (2014).","DOI":"10.1103\/PhysRevLett.113.160503"},{"key":"13","doi-asserted-by":"publisher","unstructured":"G. De las Cuevas, N. Schuch, D. P\u00e9rez-Garc\u00eda, and J.I. Cirac. ``Purifications of multipartite states: Limitations and constructive methods&apos;&apos;. New J. Phys. 15, 123021 (2013).","DOI":"10.1088\/1367-2630\/15\/12\/123021"},{"key":"14","doi-asserted-by":"publisher","unstructured":"G. De las Cuevas and T. Netzer. ``Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices&apos;&apos;. J. Math. Phys. 61, 41901 (2020).","DOI":"10.1063\/1.5127668"},{"key":"15","doi-asserted-by":"publisher","unstructured":"G. De las Cuevas, M. Hoogsteder Riera, and T. Netzer. ``Tensor decompositions on simplicial complexes with invariance&apos;&apos;. J. Symb. Comput. 124, 102299 (2024).","DOI":"10.1016\/j.jsc.2024.102299"},{"key":"16","doi-asserted-by":"publisher","unstructured":"H. Fawzi, J. Gouveia, P. A. Parrilo, R. Z. Robinson, and R. R. Thomas. ``Positive semidefinite rank&apos;&apos;. Math. Program. 153, 133\u2013177 (2015).","DOI":"10.1007\/s10107-015-0922-1"},{"key":"17","doi-asserted-by":"publisher","unstructured":"R. Jain, Y. Shi, Z. Wei, and S. Zhang. ``Efficient protocols for generating bipartite classical distributions and quantum states&apos;&apos;. IEEE Trans. Inf. Theory 59, 5171\u20135178 (2013).","DOI":"10.1109\/TIT.2013.2258372"},{"key":"18","doi-asserted-by":"publisher","unstructured":"I. Glasser, R. Sweke, N. Pancotti, J. Eisert, and J. I. Cirac. ``Expressive power of tensor-network factorizations for probabilistic modeling, with applications from hidden markov models to quantum machine learning&apos;&apos;. Adv. NeurIPS 32, 1498\u20131510 (2019).","DOI":"10.48550\/arXiv.1907.03741"},{"key":"19","doi-asserted-by":"publisher","unstructured":"M. Yannakakis. ``Expressing combinatorial optimization problems by linear programs&apos;&apos;. J. Comput. System Sci. 43, 441\u2013466 (1991).","DOI":"10.1016\/0022-0000(91)90024-Y"},{"key":"20","doi-asserted-by":"publisher","unstructured":"J. Gouveia, P. A. Parrilo, and R. R. Thomas. ``Lifts of convex sets and cone factorizations&apos;&apos;. Math. Oper. Res. 38, 248\u2013264 (2013).","DOI":"10.1287\/moor.1120.0575"},{"key":"21","doi-asserted-by":"publisher","unstructured":"S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. De Wolf. ``Linear vs. semidefinite extended formulations: Exponential separation and strong lower bounds&apos;&apos;. Proc. ACM Symp. Theory of Computing (2012).","DOI":"10.1145\/2213977.2213988"},{"key":"22","doi-asserted-by":"publisher","unstructured":"R. Jain, Z. Wei, P. Yao, and S. Zhang. ``Multipartite quantum correlation and communication complexities&apos;&apos;. Comput. Complexity 26, 199\u2013228 (2017).","DOI":"10.1007\/s00037-016-0126-y"},{"key":"23","doi-asserted-by":"publisher","unstructured":"J. E. Cohen and U. G. Rothblum. ``Nonnegative ranks, decompositions, and factorizations of nonnegative matrices&apos;&apos;. Linear Algebra Appl. 190, 149\u2013168 (1993).","DOI":"10.1016\/0024-3795(93)90224-C"},{"key":"24","doi-asserted-by":"publisher","unstructured":"D. P\u00e9rez-Garc\u00eda, F. Verstraete, M. M. Wolf, and J. I. Cirac. ``Matrix product state representations&apos;&apos;. Quantum Inf. Comput. 7, 401\u2013430 (2007).","DOI":"10.26421\/qic7.5-6-1"},{"key":"25","doi-asserted-by":"publisher","unstructured":"K. Temme and F. Verstraete. ``Stochastic matrix product states&apos;&apos;. Phys. Rev. Lett. 104, 210502 (2010).","DOI":"10.1103\/PhysRevLett.104.210502"},{"key":"26","doi-asserted-by":"publisher","unstructured":"A. Fawzi et al. ``Discovering faster matrix multiplication algorithms with reinforcement learning&apos;&apos;. Nature 610, 47\u201353 (2022).","DOI":"10.1038\/s41586-022-05172-4"},{"key":"27","doi-asserted-by":"publisher","unstructured":"G. De las Cuevas, A. Klingler, and T. Netzer. ``Approximate tensor decompositions: disappearance of many separations&apos;&apos;. J. Math. Phys. 62, 093502 (2021).","DOI":"10.1063\/5.0033876"},{"key":"28","doi-asserted-by":"publisher","unstructured":"C. Eckart and G. Young. ``The approximation of one matrix by another of lower rank&apos;&apos;. Psychometrika 1, 211\u2013218 (1936).","DOI":"10.1007\/BF02288367"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Y. Qi, P. Comon, and L. H. Lim. ``Semialgebraic geometry of nonnegative tensor rank&apos;&apos;. SIAM J. Matrix Anal. 37, 1556\u20131580 (2016).","DOI":"10.1137\/16M1063708"},{"key":"30","doi-asserted-by":"publisher","unstructured":"J. J. Sylvester. ``On the principles of the calculus of forms&apos;&apos;. Cambridge and Dublin Math. J. 7, 52\u201397 (1852).","DOI":"10.1017\/CBO9781139151078.009"},{"key":"31","doi-asserted-by":"publisher","unstructured":"G. Comas and M. Seiguer. ``On the rank of a binary form&apos;&apos;. Found. Comput. Math. 11, 65\u201378 (2011).","DOI":"10.1007\/s10208-010-9077-x"},{"key":"32","doi-asserted-by":"publisher","unstructured":"E. Ballico and A. Bernardi. ``Tensor ranks on tangent developable of segre varieties&apos;&apos;. Linear Multilinear Algebra 61, 881\u2013894 (2013).","DOI":"10.1080\/03081087.2012.716430"},{"key":"33","doi-asserted-by":"publisher","unstructured":"L. H. Lim and P. Comon. ``Nonnegative approximations of nonnegative tensors&apos;&apos;. J. Chemom. 23, 432\u2013441 (2009).","DOI":"10.1002\/cem.1244"},{"key":"34","doi-asserted-by":"publisher","unstructured":"M. Sanz, D. P\u00e9rez-Garc\u00eda, M. M. Wolf, and J. I. Cirac. ``A quantum version of Wielandt&apos;s inequality&apos;&apos;. IEEE Trans. Inf. Theory 56, 4668\u20134673 (2010).","DOI":"10.1109\/TIT.2010.2054552"},{"key":"35","doi-asserted-by":"publisher","unstructured":"G. De las Cuevas, J. I. Cirac, N. Schuch, and D. P\u00e9rez-Garc\u00eda. ``Irreducible forms of matrix product states: Theory and applications&apos;&apos;. J. Math. Phys. 58, 121901 (2017).","DOI":"10.1063\/1.5000784"},{"key":"36","doi-asserted-by":"publisher","unstructured":"A. Sch\u00f6nhage. ``Partial and total matrix multiplication&apos;&apos;. SIAM J.Comput. 10, 434\u2013455 (1981).","DOI":"10.1137\/0210032"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Y. Shitov. ``Counterexamples to Strassen\u2019s direct sum conjecture&apos;&apos;. Acta Math. 222, 363\u2013379 (2019).","DOI":"10.4310\/ACTA.2019.v222.n2.a3"},{"key":"38","doi-asserted-by":"publisher","unstructured":"M. Christandl, F. Gesmundo, M. Micha\u0142ek, and J. Zuiddam. ``Border rank nonadditivity for higher order tensors&apos;&apos;. SIAM J. Matrix Anal. Appl. 42, 503\u2013527 (2021).","DOI":"10.1137\/20M1357366"},{"key":"39","doi-asserted-by":"publisher","unstructured":"M. Christandl, A. K. Jensen, and J. Zuiddam. ``Tensor rank is not multiplicative under the tensor product&apos;&apos;. Linear Algebra Appl. 543, 125\u2013139 (2018).","DOI":"10.1016\/j.laa.2017.12.020"},{"key":"40","doi-asserted-by":"publisher","unstructured":"M. Christandl, F. Gesmundo, and A. K. Jensen. ``Border rank is not multiplicative under the tensor product&apos;&apos;. SIAM J. Appl. Algebra Geom. 3, 231\u2013255 (2019).","DOI":"10.1137\/18M1174829"},{"key":"41","doi-asserted-by":"publisher","unstructured":"G. De las Cuevas, A. Klingler, and T. Netzer. ``Polynomial decompositions with invariance and positivity inspired by tensors&apos;&apos;. Linear Algebra Appl. 698, 537\u2013588 (2024).","DOI":"10.1016\/j.laa.2024.05.025"},{"key":"42","doi-asserted-by":"publisher","unstructured":"J. I. Cirac, D. P\u00e9rez-Garc\u00eda, N. Schuch, and F. Verstraete. ``Matrix product states and projected entangled pair states: Concepts, symmetries, and theorems&apos;&apos;. Rev. Mod. Phys. 93, 045003 (2021).","DOI":"10.1103\/RevModPhys.93.045003"},{"key":"43","doi-asserted-by":"publisher","unstructured":"M. Christandl, P. Vrana, and J. Zuiddam. ``Asymptotic tensor rank of graph tensors: beyond matrix multiplication&apos;&apos;. Computational Complexity 28, 57\u2013111 (2019).","DOI":"10.1007\/s00037-018-0172-8"},{"key":"44","doi-asserted-by":"publisher","unstructured":"R. A. Horn and C. R. Johnson. ``Matrix analysis&apos;&apos;. Cambridge University Press. (1985). 2nd edition.","DOI":"10.1017\/cbo9780511810817"},{"key":"45","doi-asserted-by":"publisher","unstructured":"C. Bocci, E. Carlini, and F. Rapallo. ``Perturbation of matrices and nonnegative rank with a view toward statistical models&apos;&apos;. SIAM J. Matrix Anal. Appl. 32, 1500\u20131512 (2011).","DOI":"10.1137\/110825455"},{"key":"46","doi-asserted-by":"publisher","unstructured":"G. H. Golub and C. F. Van Loan. ``Matrix computations&apos;&apos;. Johns Hopkins University Press. (1996). 3rd edition.","DOI":"10.56021\/9781421407944"},{"key":"47","doi-asserted-by":"publisher","unstructured":"R. Or\u00fas. ``A practical introduction to tensor networks: Matrix product states and projected entangled pair states&apos;&apos;. Ann. Physics 349, 117\u2013158 (2014).","DOI":"10.1016\/j.aop.2014.06.013"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-02-26-1649\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T16:15:13Z","timestamp":1740586513000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-02-26-1649\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,26]]},"references-count":48,"URL":"https:\/\/doi.org\/10.22331\/q-2025-02-26-1649","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,26]]},"article-number":"1649"}}