Deciding Unitary Equivalence Between Matrix Polynomials and Sets of Bipartite Quantum States

In this brief report, we consider the equivalence between two sets of $m+1$ bipartite quantum states under local unitary transformations. For pure states, this problem corresponds to the matrix algebra question of whether two degree $m$ matrix polynomials are unitarily equivalent; i.e. $U{A}_i{V}^{†}=B_i$ for $0\le i\le m$ where $U$ and $V$ are unitary and $(A_i,B_i)$ are arbitrary pairs of rectangular matrices. We present a randomized polynomial-time algorithm that solves this problem with an arbitrarily high success probability and outputs transforming matrices $U$ and $V$.