Polynomial Algorithms for Simultaneous Unitary Similarity and Equivalence

We present an algorithm to solve the Simultaneous Unitary Similarity(S.U.S) problem which is to check if there exists a Similarity transformation determined by a Unitary U s.t UA_lU^*=B_l, l in \{1,...,p\}, where A_l and B_l are nxn complex matrices. We observe that the problem is simplest when U is diagonal, where we see that the `paths' in the graph defined by non-zero elements of A<sub>l</sub> and B<sub>l</sub> determine the solution. Inspired by this we generalize this to the case when U is block-diagonal to identify a form refered to as the `Solution-form' using `paths' determined by non-zero sub-matrices of A_l,B_l which are non-zero multiples of Unitary. When not in Solution form we find an equivalent problem to solve by diagonalizing a Hermitian or a Normal matrix related to the sub-matrices. The problem is solved in a maximum of n steps. The same idea can be extended to solve the Simultaneous Unitary Equivalence (S.U.Eq) problem where we solve for U,V in UA_lV^*=B_l, A_l,B_l being mxn Complex rectangular matrices. Here we work with the 'paths' in the related bi-graph to define the Solution-form. The algorithms have a complexity of O\(pn⁴\). This work finds application in Quantum Evolution, Quantum gate design and Simulation. The salient features of each step of the algorithm can be retained as Canonical features to classify a given collection of complex matrices up to Unitary Similarity.