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

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 qc.SE

  • $\begingroup$ Can you give a mathematical condition? I..e, it would help if you can put your question into math... $\endgroup$ Commented Dec 10, 2023 at 8:36
  • $\begingroup$ Sure. What I mean is if the system is consisted of N subsystems so that the Hilbert space is partitioned as $H = H_1 + H_2 + ... + H_N$, then can we tell if $U_1 = U_2 A_1 A2 \dots$ where $A_1 = $, $A_2$, ... are operators acting only localy on each subspace $\endgroup$ Commented Dec 10, 2023 at 10:10
  • $\begingroup$ @georgedoultsinos Please edit the question accordingly. $\endgroup$ Commented Dec 10, 2023 at 15:28
  • $\begingroup$ My feeling is that the general problem is computationally hard (DQC1?). It is certainly a problem people thought about, so there should be information out there on the internet. ("LU equivalent"). Still, you need to specify (i) if this is for a fixed # of qubit (in which case it is probably not computationally hard), or a large number, and (ii) if the latter, how the gate is even specified (in that case, e.g., it could be a problem on the LU equivalence of two circuits.) $\endgroup$ Commented Dec 10, 2023 at 15:30

1 Answer 1


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.