<p>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. </p>

<p>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.</p>

<p>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. </p>

<p>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$. </p>

<blockquote>
  <p>Yu Tanaka, EXACT NON-IDENTITY CHECK IS NQP-COMPLETE. International Journal of Quantum Information 08:05, 807-819 <a href="http://arxiv.org/abs/0903.0675">http://arxiv.org/abs/0903.0675</a>.</p>
</blockquote>

<p>In the other case where we're promised that they're not too close when unequal, the problem is indeed coQMA-complete. </p>

<blockquote>
  <p>D. Janzing, P. Wocjan, and T. Beth, Non-identity check is QMA-complete, International Journal
  of Quantum Information, 3(3), pp. 463–473, 2005; <a href="http://www.worldscientific.com/doi/abs/10.1142/S0219749905001067">http://www.worldscientific.com/doi/abs/10.1142/S0219749905001067</a></p>
</blockquote>

<p>(Note that the problem is equivalent to checking if $U_1U^\dagger_2$ is the identity matrix, which is called the identity check problem.)</p>

CC BY-SA 3.0
2014-05-11T02:31:42.087Z
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
CC BY-SA 3.0
2014-05-11T02:39:17.697Z
@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
CC BY-SA 3.0
2014-05-10T23:08:44.207Z
2014-05-10T23:08:44.207Z
Robin Kothari
<p>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$? </p>

<p>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?</p>

CC BY-SA 3.0
2014-05-10T17:24:38.493Z
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
CC BY-SA 3.0
2014-05-10T18:29:54.480Z
@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
CC BY-SA 3.0
2014-05-10T19:10:08.260Z
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
CC BY-SA 3.0
2014-05-10T19:11:39.273Z
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
<cc.complexity-theory><quantum-computing>
Hardness of quantum circuit equivalence?
Jonas Anderson
# Hardness of quantum circuit equivalence?

(Asked by: username_0 on 2014-05-10)

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?

**Tags:** cc.complexity-theory, quantum-computing

> **Comments:**
> **username_1**: 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. :)  
> **username_2**: @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?  
> **username_1**: 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  
> **username_1**: 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?)  

---

## 1 answers

### Answer by username_3 on 2014-05-10. Score: 13 | Accepted answer

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.)

> **Comments:**
> **username_0**: 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?  
> **username_3**: @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).  

---

