On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups

• URL: http://arxiv.org/abs/2306.03135v2
• Date: Mon, 12 Aug 2024 11:01:08 GMT
• Title: On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups
• Authors: Zhili Chen, Joshua A. Grochow, Youming Qiao, Gang Tang, Chuanqi Zhang,
• Abstract summary: We study the complexity of isomorphism problems for d-way arrays, or tensors, under natural actions by classical groups. For unitary groups, the preceding result implies that LOCC classification of tripartite quantum states is at least as difficult as LOCC classification of d-partite quantum states for any d.
• Score: 5.10647201123061
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the complexity of isomorphism problems for d-way arrays, or tensors, under natural actions by classical groups such as orthogonal, unitary, and symplectic groups. Such problems arise naturally in statistical data analysis and quantum information. We study two types of complexity-theoretic questions. First, for a fixed action type (isomorphism, conjugacy, etc.), we relate the complexity of the isomorphism problem over a classical group to that over the general linear group. Second, for a fixed group type (orthogonal, unitary, or symplectic), we compare the complexity of the decision problems for different actions. Our main results are as follows. First, for orthogonal and symplectic groups acting on 3-way arrays, the isomorphism problems reduce to the corresponding problem over the general linear group. Second, for orthogonal and unitary groups, the isomorphism problems of five natural actions on 3-way arrays are polynomial-time equivalent, and the d-tensor isomorphism problem reduces to the 3-tensor isomorphism problem for any fixed d>3. For unitary groups, the preceding result implies that LOCC classification of tripartite quantum states is at least as difficult as LOCC classification of d-partite quantum states for any d. Lastly, we also show that the graph isomorphism problem reduces to the tensor isomorphism problem over orthogonal and unitary groups.

Related papers

• Computing Isomorphisms between Products of Supersingular Elliptic Curves [0.9467360130705919]
  Deligne-Ogus-Shioda theorem guarantees the existence of isomorphisms between products of supersingular elliptic curves over finite fields. We present methods for explicitly computing these isomorphisms in time, given the rings of the curves involved.
  arXiv  Detail & Related papers  (2025-03-27T14:26:31Z)
• The supersingular Endomorphism Ring and One Endomorphism problems are equivalent [5.01069065110753]
  The endomorphism ring problem is equivalent to the problem of computing arbitrary isogenies between supersingular elliptic curves. We introduce a flexible framework for the study of isogeny graphs with additional information.
  arXiv  Detail & Related papers  (2023-09-19T08:47:12Z)
• Infinite Permutation Groups and the Origin of Quantum Mechanics [0.0]
  When the lattice is atomistic, it is isomorphic to the lattice of definably closed sets of a finitary relational structure in First Order Logic. We show that the automorphism group must belong to a family of permutation groups known as geometric Jordan groups. We then use the classification theorem for Jordan groups to argue that the combined requirements of probability and atomicism leave uncountably infinite Steiner 2-systems.
  arXiv  Detail & Related papers  (2023-07-24T18:00:16Z)
• Telling compositeness at a distance with outer automorphisms and CP [0.0]
  We investigate charge-parity (CP) and non-CP outer automorphism of groups and the transformation behavior of group representations under them. We identify situations where composite and elementary states that transform in exactly the same representation of the group, transform differently under outer automorphisms.
  arXiv  Detail & Related papers  (2022-12-14T19:00:00Z)
• Composing topological domain walls and anyon mobility [0.0]
  Topological domain walls separating 2+1 dimensional topologically ordered phases can be understood in terms of Witt equivalences. We develop a framework for computing the decomposition of parallel domain walls into indecomposable superselection sectors.
  arXiv  Detail & Related papers  (2022-08-30T06:47:04Z)
• Equivariant Graph Mechanics Networks with Constraints [83.38709956935095]
  We propose Graph Mechanics Network (GMN) which is efficient, equivariant and constraint-aware. GMN represents, by generalized coordinates, the forward kinematics information (positions and velocities) of a structural object. Extensive experiments support the advantages of GMN compared to the state-of-the-art GNNs in terms of prediction accuracy, constraint satisfaction and data efficiency.
  arXiv  Detail & Related papers  (2022-03-12T14:22:14Z)
• A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups [115.58550697886987]
  We provide a completely general algorithm for solving for the equivariant layers of matrix groups. In addition to recovering solutions from other works as special cases, we construct multilayer perceptrons equivariant to multiple groups that have never been tackled before. Our approach outperforms non-equivariant baselines, with applications to particle physics and dynamical systems.
  arXiv  Detail & Related papers  (2021-04-19T17:21:54Z)
• LieTransformer: Equivariant self-attention for Lie Groups [49.9625160479096]
  Group equivariant neural networks are used as building blocks of group invariant neural networks. We extend the scope of the literature to self-attention, that is emerging as a prominent building block of deep learning models. We propose the LieTransformer, an architecture composed of LieSelfAttention layers that are equivariant to arbitrary Lie groups and their discrete subgroups.
  arXiv  Detail & Related papers  (2020-12-20T11:02:49Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• Algebraic Neural Networks: Stability to Deformations [179.55535781816343]
  We study algebraic neural networks (AlgNNs) with commutative algebras. AlgNNs unify diverse architectures such as Euclidean convolutional neural networks, graph neural networks, and group neural networks.
  arXiv  Detail & Related papers  (2020-09-03T03:41:38Z)
• Generalizing Convolutional Neural Networks for Equivariance to Lie Groups on Arbitrary Continuous Data [52.78581260260455]
  We propose a general method to construct a convolutional layer that is equivariant to transformations from any specified Lie group. We apply the same model architecture to images, ball-and-stick molecular data, and Hamiltonian dynamical systems.
  arXiv  Detail & Related papers  (2020-02-25T17:40:38Z)
• The Hidden Subgroup Problem for Universal Algebras [0.7832189413179361]
  The Hidden Subgroup Problem (HSP) is a computational problem which includes as special cases integer factorization, the discrete discrete problem, graph isomorphism, and the shortest vector problem.
  arXiv  Detail & Related papers  (2020-01-30T13:09:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.