A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits

Understand

We investigate the problem of synthesizing T-depth optimal quantum circuits over the Clifford+T gate set.

• First we construct a special subset of T-depth 1 unitaries, such that it is possible to express the T-depth-optimal decomposition of any unitary as product of unitaries from this subset and a Clifford (up to global phase).
• The cardinality of this subset is at most $n\cdot 2^{5.6n}$.
• We use nested meet-in-the-middle (MITM) technique to develop algorithms for synthesizing provably \emph{depth-optimal} and \emph{T-depth-optimal} circuits for exactly implementable unitaries.