By word problem I mean the decision problem of whether a given reversible circuit is functionally equivalent to the empty one. It is in co-NP. The broader conjugacy problem asks whether, given $f$ and $g$, there exists a circuit $h$ such that $f=h^{-1} g h$. I prefer the right action definition of conjugation when working with circuits.
For these problems, does the computational complexity depend more on the circuit width $n$, or on the circuit depth $d$ and the size of the gate alphabet? After all, an algorithm polynomial in the order of a permutation group on $2^n$ elements is not practical.
But building a circuit from some subset of the universal classical (i.e., non-quantum) gates, as is typical, greatly restricts the permutations accessible. Suppose we restrict further, to gates whose number of inputs bounded by some constant $k$--does that help? For example, 'NCT'--the set of NOT, CNOT, and Toffoli gates--has $k=3$. Further still: only the conservative SWAP and Fredkin gates?
For my part, I find the word problem stubbornly resistant to being proved co-NP complete.
27/9/2021
I'm looking now at 'T', the Toffoli-only circuits. Let $\mathbf{T}_n$ designate the group generated by all Toffolis on $n$ circuit lines, and $\mathbf{E}_n$ be the group generated by only SWAPs--called 'exchangers' by (1), and isomorphic to $\mathbf{S}_n$. $\mathbf{T}_n$ and $\mathbf{E}_n$ are disjoint save for the identity.
Conjecture: If, for any word $t \in \mathbf{T}_n$, it is possible to calculate the centralizer $C_{\mathbf{E}_n}(t)$ efficiently (in polynomial time), then the word problem for $\mathbf{T}_n$ is also in P.
References
- Vos, A. D., Raa, B., & Storme, L. (2002). Generating the group of reversible logic gates. Journal of Physics A: Mathematical and General, 35(33), 7063–7078. https://doi.org/10.1088/0305-4470/35/33/307