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

Abstract We investigate the problem of synthesizing T-depth optimal quantum circuits for exactly implementable unitaries over the Clifford+T gate set. We construct a subset, $${{\mathbb{V}}}_{n}$$ Vn , of T-depth 1 unitaries. T-depth-optimal decomposition of unitaryUis $${e}^{i\phi }\left({\prod }_{i}{V}_{i}\right)C$$ eiϕ∏iViC , $${V}_{i}\in {{\mathbb{V}}}_{n}$$ Vi∈Vn ,Cis Clifford and $$| {{\mathbb{V}}}_{n}| \,\le \,n\cdot {2}^{5.6n}$$ ∣Vn∣≤n⋅25.6n . We use nested meet-in-the-middle technique to synthesize provably depth-optimal and T-depth-optimal circuits. For the latter, we achieve space and time complexity $$O({({4}^{{n}^{2}})}^{\lceil d/c\rceil })$$ O((4n2)⌈d/c⌉) and $$O({({4}^{{n}^{2}})}^{(c-1)\lceil d/c\rceil })$$ O((4n2)(c−1)⌈d/c⌉) respectively (dis the minimum T-depth,c ≥ 2 a constant). The previous best algorithm had complexity $$O({({3}^{n}\cdot {2}^{k{n}^{2}})}^{\lceil \frac{d}{2}\rceil }\cdot {2}^{k{n}^{2}})$$ O((3n⋅2kn2)⌈d2⌉⋅2kn2) (k > 2.5 a constant). We design a more efficient algorithm with space and time complexity poly(n, 25.6n, d) (or $${{{\rm{poly}}}}({n}^{\log n},{2}^{5.6n},d)$$ poly(nlogn,25.6n,d) with weaker assumptions). The claimed efficiency, optimality depends on conjectures.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.