On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
Joshua A. Grochow, Youming Qiao
Abstract
.We study the complexity of isomorphism problems for tensors, groups, and polynomials. These problems have been studied in multivariate cryptography, machine learning, quantum information, and computational group theory. We show that these problems are all polynomial-time equivalent, creating bridges between problems traditionally studied in myriad research areas. This prompts us to define the complexity class \(\mathsf{TI}\) , namely problems that reduce to the tensor isomorphism problem in polynomial time. Our main technical result is a polynomial-time reduction from \(d\) -tensor isomorphism to 3-tensor isomorphism. In the context of quantum information, this result gives a multipartite-to-tripartite entanglement transformation procedure that preserves equivalence under stochastic local operations and classical communication.Keywordsisomorphism problemstensor isomorphismgroup isomorphismpolynomial isomorphismcomplexity classcompletenessMSC codes68Q1581P4568Q17