



@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 = {<p><span style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 12.8px;">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 \&quot;garbage\&quot; 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.</span></p>},
	keywords = {complexity, reversible circuits},
	issn = {1533-7146},
	url = {http://dl.acm.org/citation.cfm?id=2685179.2685182},
	author = {Stephen P. Jordan}
}
