Completeness conjecture for generalized controlled-not identities on Boolean isomorphisms

Let FinSet2\mathsf{FinSet}_2 denote the finite-set prop on the two-element set, and let {X,x}\{X,x\} denote the generalized controlled-not gate controlled by wires indexed by XX and operating on xx. Let Iso(FinSet2)\operatorname{Iso}(\mathsf{FinSet}_2) denote the prop generated by all such gates modulo the following identities:

{X,x}{X,x}=1.\{X,x\}\{X,x\}=1.

If xYx\notin Y and yXy\notin X, then

{X,x}{Y,y}={Y,y}{X,x}.\{X,x\}\{Y,y\}=\{Y,y\}\{X,x\}.

If xYx\notin Y, then

{X,x}{{x}Y,y}={XY,y}{{x}Y,y}{X,x}.\{X,x\}\{\{x\}\sqcup Y,y\}=\{X\cup Y,y\}\{\{x\}\sqcup Y,y\}\{X,x\}.

If xYx\notin Y, then

{{x}Y,y}{X,x}={X,x}{{x}Y,y}{XY,y}.\{\{x\}\sqcup Y,y\}\{X,x\}=\{X,x\}\{\{x\}\sqcup Y,y\}\{X\cup Y,y\}.

If xYx\in Y and yXy\in X, then

{X,x}{Y,y}{X,x}={Y,y}{X,x}{Y,y}.\{X,x\}\{Y,y\}\{X,x\}=\{Y,y\}\{X,x\}\{Y,y\}.

Completeness conjecture for generalized controlled-not identities. These identities are complete for Iso(FinSet2)\operatorname{Iso}(\mathsf{FinSet}_2): every equality of Boolean isomorphisms generated by generalized controlled-not gates follows from them.

Generalized controlled-not gates generate Boolean isomorphisms, and the conjecture proposes a complete presentation by local identities extending commutation and braid-type relations. The supplied text gives no resolution status, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Cole Comfort, “Distributive Laws, Spans and the ZX-Calculus”, arXiv:2102.04386 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.