Skip to main content
U.S. flag

An official website of the United States government

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



Stephen P. Jordan


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.
Quantum Information & Computation


computational complexity, reversible computating, quantum computing


Jordan, S. (2013), Strong equivalence of reversible circuits is coNP-complete, Quantum Information & Computation, [online], (Accessed June 24, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created July 2, 2013, Updated February 19, 2017