  It is well-known that deciding equivalence of logic circuits is a
coNP-complete problem. As a corollary, the problem of deciding weak equivalence
of reversible circuits, i.e. ignoring the ancilla bits, is also coNP-complete.
The complexity of deciding strong equivalence, including the ancilla bits, is
less obvious and may depend on gate set. Here we use Barrington's theorem to
show that deciding strong equivalence of reversible circuits built from the
Fredkin gate is coNP-complete. This implies coNP-completeness of deciding
strong equivalence for other commonly used universal reversible gate sets,
including any gate set that includes the Toffoli or Fredkin gate.
