Improved Synthesis of Toffoli-Hadamard Circuits

Understand

The matrices that can be exactly represented by a circuit over the Toffoli-Hadamard gate set are the orthogonal matrices of the form $M/ \sqrt{2}{}^k$, where $M$ is an integer matrix and $k$ is a nonnegative integer.

• The exact synthesis problem for this gate set is the problem of constructing a circuit for a given such matrix.
• Existing methods produce circuits consisting of $O(2^n \log(n)k)$ gates, where $n$ is the dimension of the matrix.
• In this paper, we provide two improved synthesis methods.