Knuth-Bendix Completion Algorithm and Shuffle Algebras For Compiling NISQ Circuits

Compiling quantum circuits lends itself to an elegant formulation in the language of rewriting systems on non commutative polynomial algebras $mathbb Qlangle Xrangle$. 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 Rsubset mathbb Qlangle Xrangle$ 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 Qlangle Xrangle$, and 2) using the Buchberger algorithm on the shuffle algebra $mathbb Q[L]$ where $L$ is the set of Lyndon words on $X$.