×

A finite-tame-wild trichotomy theorem for tensor diagrams. (English) Zbl 1505.16025

Summary: In this paper, we consider the problem of determining when two tensor networks are equivalent under a heterogeneous change of basis. In particular, to a tensor (or string) diagram in a certain monoidal category (which we call tensor diagrams), we formulate an associated abelian category of representations. Each representation corresponds to a tensor network on that diagram. We then classify which tensor diagrams give rise to categories that are finite, tame, or wild in the traditional sense of representation theory. For those tensor diagrams of finite and tame type, we classify the indecomposable representations. Our main result is that a tensor diagram is wild if and only if it contains a vertex of degree at least three. Otherwise, it is of tame or finite type.

MSC:

16G60 Representation type (finite, tame, wild, etc.) of associative algebras
15A69 Multilinear algebra, tensor calculus
18M35 Categories of networks and processes, compositionality
18M05 Monoidal categories, symmetric monoidal categories
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Belitskii, G. R.; Sergeichuk, V. V., Complexity of matrix problems, Linear Algebra Appl., 361, 203-222 (2003) · Zbl 1030.15011
[2] Biamonte, J.; Bergholm, V.; Lanzagorta, M., Tensor network methods for invariant theory, J. Phys. A, Math. Theor., 46, 47, Article 475301 pp. (2013) · Zbl 1280.81020
[3] Brion, M., Representations of Quivers (2008)
[4] Bulatov, A.; Grohe, M., The complexity of partition functions, Theor. Comput. Sci., 348, 2, 148-186 (2005) · Zbl 1081.68030
[5] Cai, J. Y.; Chen, X., Complexity of counting csp with complex weights, (Proceedings of the 44th Symposium on Theory of Computing (2012), ACM), 909-920 · Zbl 1286.68182
[6] Cai, J.-Y.; Chen, X.; Lu, P., Non-negatively weighted# csp: an effective complexity dichotomy, (2011 IEEE 26th Annual Conference on Computational Complexity (CCC) (2011), IEEE), 45-54
[7] Cai, J.-Y.; Fu, Z.; Guo, H.; Williams, T., A Holant dichotomy: is the fkt algorithm universal?, (2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) (2015), IEEE), 1259-1276
[8] Cai, J.-Y.; Guo, H.; Williams, T., A complete dichotomy rises from the capture of vanishing signatures, (Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing (2013), ACM), 635-644 · Zbl 1293.68162
[9] Cai, J.-Y.; Lu, P.; Xia, M., Holographic algorithms with matchgates capture precisely tractable planar_# csp, (2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2010), IEEE), 427-436
[10] de la Harpe, P.; Jones, V. F.R., Graph invariants related to statistical mechanical models: examples and problems, J. Comb. Theory, Ser. B, 57, 2, 207-227 (1993) · Zbl 0729.57003
[11] Drozd, J. A., Tame and wild matrix problems, (Representation Theory II (1980), Springer), 242-258 · Zbl 0457.16018
[12] Dür, W.; Vidal, G.; Cirac, J. I., Three qubits can be entangled in two inequivalent ways, Phys. Rev. A, 62, Article 062314 pp. (Nov 2000)
[13] Dyer, M.; Richerby, D., An effective dichotomy for the counting constraint satisfaction problem (2010), arXiv preprint
[14] Gabriel, P., Unzerlegbare darstellungen I, Manuscr. Math., 6, 1, 71-103 (1972) · Zbl 0232.08001
[15] Grassl, M.; Rötteler, M.; Beth, T., Computing local invariants of quantum-bit systems, Phys. Rev. A, 58, 3, 1833 (1998)
[16] Hero, M. W.; Willenbring, J. F., Stable Hilbert series as related to the measurement of quantum entanglement, Discrete Math., 309, 23, 6508-6514 (2009) · Zbl 1209.13019
[17] Johansson, M.; Ericsson, M.; Singh, K.; Sjöqvist, E.; Williamson, M. S., Topological phases and multiqubit entanglement, Phys. Rev. A, 85, 3, Article 032112 pp. (2012)
[18] Joyal, A.; Street, R., The geometry of tensor calculus. I, Adv. Math., 88, 1, 55-112 (1991) · Zbl 0738.18005
[19] A. Joyal, R. Street, The geometry of tensor calculus II, Unpublished draft, available from Ross Street’s website.
[20] A. Joyal, R. Street, Planar diagrams and tensor algebra. Unpublished manuscript, available from Ross Street’s website, 1988.
[21] Klyachko, A., Coherent states, entanglement, and geometric invariant theory (2002), arXiv preprint
[22] Kraus, B., Local unitary equivalence of multipartite pure states, Phys. Rev. Lett., 104, 2, Article 020504 pp. (2010) · Zbl 1255.81048
[23] Landsberg, J. M.; Morton, J.; Norine, S., Holographic algorithms without matchgates, Linear Algebra Appl., 438, 15 (2013) · Zbl 1257.05007
[24] Luque, J.-G.; Thibon, J.-Y., Polynomial invariants of four qubits, Phys. Rev. A (3), 67, 4, Article 042303 pp. (2003)
[25] Luque, J.-G.; Thibon, J.-Y., Algebraic invariants of five qubits, J. Phys. A, Math. Gen., 39, 2, 371 (2006) · Zbl 1084.81020
[26] Luque, J.-G.; Thibon, J.-Y.; Toumazet, F., Unitary invariants of qubit systems, Math. Struct. Comput. Sci., 17, 6, 1133-1151 (2007) · Zbl 1132.81009
[27] Mac Lane, S., Categories for the Working Mathematician (1998), Springer Verlag · Zbl 0906.18001
[28] Macicażek, T.; Oszmaniec, M.; Sawicki, A., How many invariant polynomials are needed to decide local unitary equivalence of qubit states? (2013), arXiv preprint · Zbl 1284.81065
[29] Margulies, S.; Morton, J., Polynomial-time solvable# csp problems via algebraic models and Pfaffian circuits, J. Symb. Comput., 74, 152-180 (2016) · Zbl 1346.68295
[30] Morton, J., Pfaffian circuits (2010), arXiv preprint
[31] Morton, J.; Turner, J., Computing the Tutte polynomial of lattice path matroids using determinantal circuits, Theor. Comput. Sci., 598, 150-156 (2015) · Zbl 1329.68120
[32] Morton, J.; Turner, J., Generalized counting constraint satisfaction problems with determinantal circuits, Linear Algebra Appl., 466, 357-381 (2015) · Zbl 1302.05108
[33] Orús, R., A practical introduction to tensor networks: matrix product states and projected entangled pair states, Ann. Phys., 349, 117-158 (2014) · Zbl 1343.81003
[34] Penrose, R., Applications of negative dimensional tensors, (Combinatorial Mathematics and Its Applications (1971)), 221-244 · Zbl 0216.43502
[35] Ringel, C. M., The representations of quivers of type a_n. a fast approach (2013), arXiv preprint
[36] Selinger, P., A survey of graphical languages for monoidal categories, (New Structures for Physics (2010), Springer), 289-355 · Zbl 1217.18002
[37] Turner, J., Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits, J. Comput. Syst. Sci., 86, 108-116 (2017) · Zbl 1370.68143
[38] Turner, J.; Morton, J., A complete set of invariants for LU-equivalence of density operators, SIGMA, 13, Article 028 pp. (2017) · Zbl 1385.81026
[39] Valiant, L., Quantum computers that can be simulated classically in polynomial time, (Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, New York (2001), ACM), 114-123, (electronic) · Zbl 1323.68283
[40] Valiant, L., Holographic algorithms (extended abstract), (Proceedings of the 45th Annual Symposium on Foundations of Computer Science (2004)), 306-315
[41] Valiant, L. G., Accidental algorithms, (Proc. 47th Annual IEEE Symposium on Foundations of Computer Science (2006), Citeseer), 509-517
[42] Verstraete, F.; Cirac, J. I., Renormalization algorithms for quantum-many body systems in two and higher dimensions (2004), arXiv preprint
[43] White, S. R., Density matrix formulation for quantum renormalization groups, Phys. Rev. Lett., 69, 19, 2863 (1992)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.