  We present new optimal and heuristic algorithms for exact synthesis of
multi-qubit unitaries and isometries. For example, our algorithms find Clifford
and T circuits for unitaries with entries in $\mathbb{Z}[i,1/\sqrt{2}]$. The
optimal algorithms are the A* search instantiated with a new data structure for
graph vertices and new consistent heuristic functions. We also prove that for
some gate sets, best-first search synthesis relying on the same heuristic is
efficient. For example, for two-qubit Clifford and T circuits, our best-first
search runtime is proportional to the T-count of the unitary. Our algorithms
rely on Hermite and Smith Normal Forms of matrices with entries in a ring of
integers of a number field, and we leverage the theory of and algorithms for
Hermitian lattices over number fields to prove efficiency. These new techniques
are of independent interest for future work on multi-qubit exact circuit
synthesis and related questions.
