Given two poly-sized quantum circuits $C_1$ and $C_2$ on $n$ qubits with a universal gate set generated by some finite set of one and two qubit gates. I'm thinking of the gates $\langle H, T, CNOT\rangle$, but other universal gate sets should work as well. Notice that $C_1$ and $C_2$ each correspond to a $2^n \times 2^n$ unitary matrix, $U_1$ and $U_2$, respectively. How hard is it to determine if $U_1 == U_2$, given the circuits $C_1$ and $C_2$? Clearly the problem is in coQMA since if $U_1$ and $U_2$ are different there exists an input state $r$ such that $C_1(r)$ not equal to $C_2(r)$ which can be checked with a quantum computer. Has this problem been studied? Is it complete for this class? Is this class known as something else in the literature, since I cannot find much about it?
Hardness of quantum circuit equivalence?
cc.complexity theory;quantum computing
The problem isn't clearly in coQMA. If $U_1$ and $U_2$ are different, and you're given a state on which they act differently, it is not necessary that a polynomial-time quantum computer can check that the output states are different. In fact, it is easy to show that if these two quantum states are different, but exponentially close in trace norm, then no polynomial-time quantum algorithm can distinguish the two. This is analogous to how no polynomial-time classical algorithm can distinguish two probability distributions that are exponentially close.On the other hand, if we're promised that $U_1$ and $U_2$ are not too close when they are not equal, then the problem is in coQMA. The complexity of either variant is known. In the exact case, this problem is complete for coNQP, which is the same as the class $C_=P$. Yu Tanaka, EXACT NON-IDENTITY CHECK IS NQP-COMPLETE. International Journal of Quantum Information 08:05, 807-819 http://arxiv.org/abs/0903.0675.In the other case where we're promised that they're not too close when unequal, the problem is indeed coQMA-complete. D. Janzing, P. Wocjan, and T. Beth, Non-identity check is QMA-complete, International Journal  of Quantum Information, 3(3), pp. 463473, 2005; http://www.worldscientific.com/doi/abs/10.1142/S0219749905001067(Note that the problem is equivalent to checking if $U_1U^\dagger_2$ is the identity matrix, which is called the identity check problem.)