@article {1871, title = {Strong Equivalence of Reversible Circuits is coNP-complete}, journal = {Quantum Information Computation}, volume = {14}, year = {2014}, month = {2014/11/01}, pages = {1302{\textendash}1307}, abstract = {

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. allowing initialized ancilla bits in the input and ignoring \"garbage\" ancilla bits in the output, 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\&$\#$39;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.

}, keywords = {complexity, reversible circuits}, issn = {1533-7146}, url = {http://dl.acm.org/citation.cfm?id=2685179.2685182}, author = {Stephen P. Jordan} }