  We present an algorithm for computing depth-optimal decompositions of logical
operations, leveraging a meet-in-the-middle technique to provide a significant
speed-up over simple brute force algorithms. As an illustration of our method
we implemented this algorithm and found factorizations of the commonly used
quantum logical operations into elementary gates in the Clifford+T set. In
particular, we report a decomposition of the Toffoli gate over the set of
Clifford and T gates. Our decomposition achieves a total T-depth of 3, thereby
providing a 40% reduction over the previously best known decomposition for the
Toffoli gate. Due to the size of the search space the algorithm is only
practical for small parameters, such as the number of qubits, and the number of
gates in an optimal implementation.
