  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. First, we show that a
technique introduced by Kliuchnikov in 2013 for Clifford+$T$ circuits can be
straightforwardly adapted to Toffoli-Hadamard circuits, reducing the complexity
of the synthesized circuit from $O(2^n \log(n)k)$ to $O(n^2 \log(n)k)$. Then,
we present an alternative synthesis method of similarly improved cost, but
whose application is restricted to circuits on no more than three qubits. Our
results also apply to orthogonal matrices over the dyadic fractions, which
correspond to circuits using the 2-qubit gate $H\otimes H$, rather than the
usual single-qubit Hadamard gate $H$.
