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, Vn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathbb{V}}}_{n}$$\end{document}, of T-depth 1 unitaries. T-depth-optimal decomposition of unitary U is eiϕ∏iViC\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${e}^{i\phi }\left({\prod }_{i}{V}_{i}\right)C$$\end{document}, Vi∈Vn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${V}_{i}\in {{\mathbb{V}}}_{n}$$\end{document}, C is Clifford and ∣Vn∣≤n⋅25.6n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$| {{\mathbb{V}}}_{n}| \,\le \,n\cdot {2}^{5.6n}$$\end{document}. 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((4n2)⌈d/c⌉)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O({({4}^{{n}^{2}})}^{\lceil d/c\rceil })$$\end{document} and O((4n2)(c−1)⌈d/c⌉)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O({({4}^{{n}^{2}})}^{(c-1)\lceil d/c\rceil })$$\end{document} respectively (d is the minimum T-depth, c ≥ 2 a constant). The previous best algorithm had complexity O((3n⋅2kn2)⌈d2⌉⋅2kn2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O({({3}^{n}\cdot {2}^{k{n}^{2}})}^{\lceil \frac{d}{2}\rceil }\cdot {2}^{k{n}^{2}})$$\end{document}(k > 2.5 a constant). We design a more efficient algorithm with space and time complexity poly(n, 25.6n, d) (or poly(nlogn,25.6n,d)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\rm{poly}}}}({n}^{\log n},{2}^{5.6n},d)$$\end{document} with weaker assumptions). The claimed efficiency, optimality depends on conjectures.