I am trying to define a mathematical framework that starts from a generic function $f$, which I can synthesis as a circuit of generalised Toffoli gates -- i.e. $m$ controls, 1 target.

I would like to read of a framework similar to the one used for the group of linear reversible boolean functions. Which relates to circuits of CNOTs only.

For the case of linear reversible boolean functions, we have $$f: \mathbb{F}_2^n \mapsto \mathbb{F}_2^n,$$ which is also defined by an invertible boolean $n$-by-$n$ matrix.

Assuming a boolean function group defined by a matrix $M_{f}$. I am looking for a decomposition of such matrix, where each component can be translated into a Toffoli.

Hence the steps are:

  1. Defining a boolean function $f$;
  2. defining the matrix operator $M_f$;
  3. defining a method to decompose $M_f$.
  • 2
    $\begingroup$ Would it not be $S_{2^n}$, the symmetric group on $2^n$ elements, by virtue of the universality of Toffoli gates? I think I'm missing something. $\endgroup$ Jan 29 at 20:16
  • $\begingroup$ I don't know to be fair. May you explain what you think in an answer? $\endgroup$ Jan 29 at 21:00
  • 1
    $\begingroup$ You should define what a generalized Toffoli gate is. Is it a Toffoli gate that acts on arbitrary triplets of commuting Pauli products instead of specifically on the single qubit Z operators of its controls and the X operator of its target? $\endgroup$ Jan 29 at 22:56
  • $\begingroup$ It would be also interesting to see how linear reversible boolean function can be synthesised into generalised Toffoli gates, rather than CNOTs. $\endgroup$ Jan 30 at 13:49

1 Answer 1


Further to your definition, an early result in quantum computing shows that for $m\gt 1$ the generalized Toffoli gate (or C$^m$NOT gate) is computationally universal, at least because judicious choice of the control inputs instantiates AND, OR, or NOT gates.

More importantly any circuit acting on $n$ qubits (or, bits) comprising only CCNOT gates can be represented as a permutation matrix on $2^n$ inputs (and not, as indicated in the question, an $n\times n$ boolean matrix), and further all such $2^n\times 2^n$ matrices can be realized with generalized Toffoli gates.

Each such matrix is a representation of an element of the symmetric group $S_{2^n}$, with composition being the group operation. This is a big group! It has $(2^n)!$ elements.

With three bits (qubits) there are $\Vert S_8\Vert=8!=40320$ such permutation matrices.

Analogously for $m\ge 1$ the generalized Fredkin gate (or C$^m$SWAP gate) is computationally universal, and each circuit can similarly be represented as a permutation matrix; however, for the generalized Fredkin gate, not all such $2^n\times 2^n$ matrices can be realized, because SWAP gates must leave the Hamming weight invariant (the number of $1$'s in the input to the circuit must be the same as the number of $1$'s in the output).

With only three bits (qubits) and not allowing any ancilla, I find that there are only $1\times 3\times 2\times 3\times 1\times 2\times 1\times 1=36$ such matrices; I do not know what, if any, group this corresponds to.

You may also enjoy Gajewski's PhD thesis (PDF), or Aaronson, Grier, and Schaeffer's classification of reversible circuits (arXiv abstract).

  • $\begingroup$ Thank you! Please notice that the n-to-n boolean matrix is correct and can encode linear reversible boolean functions. $\endgroup$ Jan 30 at 16:24
  • $\begingroup$ @DanieleCuomo How? Even a truth-table on $n$ bits has $2^n$ rows...? $\endgroup$ Jan 30 at 16:53
  • $\begingroup$ See, for example, "Reducing the depth of linear reversible quantum circuits" $\endgroup$ Jan 30 at 17:49
  • 1
    $\begingroup$ @DanieleCuomo Oh I think I see your point. An $n$-bit input $x$ gets mapped into an $n$-bit output $f(x)$ through a matrix $A$ such that $f(x)=A x$. But for each of the $2^n$ different inputs $x$ there's a different matrix $A$. $\endgroup$ Jan 30 at 18:43
  • $\begingroup$ Exactly. I am looking for something similar. Some compact definition (as $f(x) = Ax$ is), which relates to Toffoli circuits. $\endgroup$ Jan 30 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.