We investigate the problem of synthesizing T-depth-optimal quantum circuits over the universal fault-tolerant Clifford+T gate set, where the implementation of the non-Clifford T-gate is the most expensive. We apply the nested-meet-in-the-middle(MITM) technique of Mosca,Mukhopadhyay(2020) and obtain a space-time trade-off to provably synthesize both depth and T-depth-optimal circuits. Specifically, using channel representation we design $Oleft(|mathbb{V}_n|^{leftlceilfrac{d}{c}rightrceil} right)$ time algorithm for T-depth-optimal circuits. $mathbb{V}_n$ is the set of some special T-depth-1 unitaries and $d$ is the minimum T-depth of input unitary. The MITM technique of Amy.et.al.(2013) has a complexity $left(left|mathcal{V}_nright|^{d/2}right)$, where $mathcal{V}_n$ is the set of T-depth-1 circuits. Since $|mathbb{V}_n| ll|mathcal{V}_{n}|$, our algorithm is much more efficient. For example, we take 2.152 seconds to generate $mathbb{V}_3$ (size 2282), Amy et al. takes about 4 days ($approx 3.5times 10^6$ seconds) to generate $mathcal{V}_{3}$ (size > 92,897,280). Inspired by the observations made by Mosca and Mukhopadhyay(2020), we design a $poly((log N)!,N,d)$ complexity heuristic algorithm for synthesizing T-depth-optimal circuits, where $N=2^n$. We synthesized previously unknown T-depth-optimal circuits for Fredkin, Peres, Negated-Toffoli and Quantum-XOR in $approx$ 27-28 minutes, and random 2 and 3-qubit unitaries with input T-depth in the range 2-20 and 2-7 respectively, and obtained output T-depth $leq$ input. There are no efficient T-depth-optimal synthesis algorithm to verify our results, but it is a good indication about the correctness of our claims for most unitaries.
Download