Suppose that $U_1$ and $U_2$ are two (entangling) operators that act on a quantum system consisting of several subsystems. Is there any criterion to tell if these two are equivalent up to applying operators acting only locally to the subsystem?

For example the 2-qubit Control-Z phase gate can be transform to the Control-NOT via applying (local) Hadamard gates to the second (target) qubit before and after. However this is trivial. How one can tell in more complicated cases?

Cross-posted on physics.SE


2 Answers 2


Equivalent $U_1$ and $U_2$ should have the same spectrum. If eigenvalues of $U_1$ are all different, then there is essentially a unique unitary $V$ (up to a set of phases) which gives the equivalence $VU_1V^\dagger = U_2$. If $U_1,U_2$ are written in the eigenbasis, then matrices $V' = DV$, where $D$ is any diagonal unitary, form the set of all unitaries that give the equivalence between $U_1$ and $U_2$. We then can check if $V' = V_1 \otimes V_2$ for some $D$, which should be easy.

On the other hand, I don't think there is an efficient algorithm in a general situation. Let $S_1$, $S_2$ be eigensubspaces of $U_1$, $U_2$ that correspond to some eigenvalue $\lambda$. Clearly, $\dim S_1 = \dim S_2$. If $U_1$ and $U_2$ are equivalent by some $V_1 \otimes V_2$, then the minimum (and maximum) Schmidt rank of a vector in $S_1$ and in $S_2$ should coincide. In general, finding Schmidt rank of a mixed state is a hard problem. The separability problem is simpler, but it's known that it's NP-hard. I don't know if it's proven that finding Schmidt rank of a projector $P$ is also NP-hard, but I haven't seen efficient solutions of this problem either.


I assumed that $U_1$ and $U_2$ are locally equivalent if $$ (V_1 \otimes V_2)U_1(V_1 \otimes V_2)^\dagger = U_2 $$ for some local unitaries $V_1,V_2$. More broadly, we can define local equivalence by $$ (V_1 \otimes V_2)U_1(V_3 \otimes V_4) = U_2. $$ Under this definition the problem looks even harder, I think.


Even checking if a quantum circuit is equal to the identity circuit is already QMA-hard. Thus, the general problem on $N$ qubits, provided that the unitary is specified by a circuit, is a computationally hard problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.