  Compiling quantum circuits lends itself to an elegant formulation in the
language of rewriting systems on non commutative polynomial algebras $\mathbb
Q\langle X\rangle$. The alphabet $X$ is the set of the allowed hardware 2-qubit
gates. The set of gates that we wish to implement from $X$ are elements of a
free monoid $X^*$ (obtained by concatenating the letters of $X$). In this
setting, compiling an idealized gate is equivalent to computing its unique
normal form with respect to the rewriting system $\mathcal R\subset \mathbb
Q\langle X\rangle$ that encodes the hardware constraints and capabilities. This
system $\mathcal R$ is generated using two different mechanisms: 1) using the
Knuth-Bendix completion algorithm on the algebra $\mathbb Q\langle X\rangle$,
and 2) using the Buchberger algorithm on the shuffle algebra $\mathbb Q[L]$
where $L$ is the set of Lyndon words on $X$.
