# Hardness of quantum circuit equivalence?

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?

• In the classical world (with a PPT bounded 'checker'), this is a hard problem for general circuits. In fact, checking (classically) whether two Boolean formulas (i.e. log-depth circuits) are equivalent is 'Graph Isomorphism'-complete. Hopefully an answer will also tell us whether a quantum 'checker' can decide this for classical circuits. :) – Daniel Apon May 10 '14 at 17:24
• @DanielApon: I'm pretty sure checking whether two formulas are equivalent is coNP-complete. The fact that it's in coNP is clear. To show completeness, note that asking whether a formula is equivalent to the constant 1 formula, i.e. whether a formula is a tautology, is a sub-case. Were you thinking of a different result? – Joshua Grochow May 10 '14 at 18:29
• You're right -- I guess the version I was thinking of is whether there exists a permutation of literals/clauses and bijection between variables so that two formulas are syntactically equivalent – Daniel Apon May 10 '14 at 19:10
• In any case, if it's coNP-complete, I expect having a quantum computer isn't expected to help much, yes? (Which would answer this question by default?) – Daniel Apon May 10 '14 at 19:11

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. 463–473, 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.)

• Thanks Robin, great answer! I have a quick follow-up: when the circuit elements are taken from a discrete set (whose element are not exponentially close) such as Clifford + T is it possible to have two poly-sized circuits which are exponentially close? – Jonas Anderson May 11 '14 at 2:31
• @Jonas: Yes, that's possible. For example, choose some $2 \times 2$ matrix that is exponentially close to the identity matrix. By the Solovay-Kitaev theorem, you can approximate this gate to exponential precision using only polynomially many gates from any universal gate set (e.g., Clifford + T). – Robin Kothari May 11 '14 at 2:39