Tensor Isomorphism over Some Matrix Groups and Its Applications
- Publication Type:
- Thesis
- Issue Date:
- 2023
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
We study the complexity of isomorphism problems for 𝑑-way arrays under natural actions by different matrix groups such as the general linear group, unitary group, orthogonal group, and symplectic group. Such problems naturally relate to statistical data analysis and quantum information. We study two types of complexity-theoretic questions. First, for a fixed action type (congruence, conjugacy, etc.), we relate the complexity of the isomorphism problem over classical groups to that over symmetric group or general linear group. Second, for a fixed group type (orthogonal or unitary), we compare the complexity of deciding isomorphism under different actions.
Our main results are as follows. First, for orthogonal (symplectic) group acting on 3-way arrays, the isomorphism problem reduces to the corresponding problem over the general linear group. Second, for orthogonal (unitary) group, the isomorphism problems of five natural actions on 3-way arrays are polynomial-time equivalent, and the 𝑑-tensor isomorphism problem reduces to the 3-tensor isomorphism problem for any fixed 𝑑 > 3. The preceding result for unitary groups implies that determining tripartite quantum states equivalence under local operations and classical communication (LOCC) is at least as difficult as determining 𝑑-partite quantum states equivalence under LOCC for any constant 𝑑. Lastly, we also show that the graph isomorphism problem reduces to the tensor isomorphism problem over orthogonal and unitary groups.
Please use this identifier to cite or link to this item: