Jordan, S.
(2013),
Strong equivalence of reversible circuits is coNP-complete, Quantum Information & Computation, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=913896
(Accessed October 21, 2025)
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
Strong equivalence of reversible circuits is coNP-complete
Published
Author(s)
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. 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 the Toffoli or Fredkin gate.Citation
Quantum Information & Computation
Pub Type
Journals
Download Paper
Keywords
computational complexity, reversible computating, quantum computing
Citation
Issues
If you have any questions about this publication or are having problems accessing it, please contact [email protected].
Created July 2, 2013, Updated February 19, 2017