8
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. :) $\endgroup$
    – Daniel Apon
    May 10, 2014 at 17:24
  • 2
    $\begingroup$ @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? $\endgroup$
    – Joshua Grochow
    May 10, 2014 at 18:29
  • $\begingroup$ 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 $\endgroup$
    – Daniel Apon
    May 10, 2014 at 19:10
  • $\begingroup$ 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?) $\endgroup$
    – Daniel Apon
    May 10, 2014 at 19:11

1 Answer 1

Reset to default
13
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Jonas Anderson
    May 11, 2014 at 2:31
  • 4
    $\begingroup$ @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). $\endgroup$
    – Robin Kothari
    May 11, 2014 at 2:39

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.