Search

Abstract We design an algorithm to determine the (minimum) T-count of any n-qubit (n ≥ 1) unitary W of size 2 n × 2 n , over the Clifford+T gate set. The space and time complexity of our algorithm are $$O\left({2}^{2n}\right)$$ O 2 2 n and $$O\left({2}^{2n{{{{\mathcal{T}}}}}_{\epsilon }(W)+4n}\right)$$ O 2 2 n T ϵ ( W ) + 4 n , respectively. $${{{{\mathcal{T}}}}}_{\epsilon }(W)$$ T ϵ ( W ) (ϵ-T-count) is the (minimum) T-count of an exactly implementable unitary U ( $${{{\mathcal{T}}}}(U)$$ T ( U ) ), such that d(U,W) ≤ ϵ and $${{{\mathcal{T}}}}(U)\le {{{\mathcal{T}}}}({U}^{{\prime} })$$ T ( U ) ≤ T ( U ′ ) where $${U}^{{\prime} }$$ U ′ is any exactly implementable unitary with $$d({U}^{{\prime} },W)\le \epsilon$$ d ( U ′ , W ) ≤ ϵ . d(. , .) is the global phase invariant distance. Our algorithm can also be used to determine the (minimum) T-depth as well as the minimum non-Clifford-gate count or depth required to implement any multi-qubit unitary with a finite universal gate set like Clifford+CS, Clifford+V, etc. For small enough ϵ, we can synthesize the 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}$$ V n , of T-depth 1 unitaries. T-depth-optimal decomposition of unitary U is $${e}^{i\phi }\left({\prod }_{i}{V}_{i}\right)C$$ e i ϕ ∏ i V i C , $${V}_{i}\in {{\mathbb{V}}}_{n}$$ V i ∈ V n , C is Clifford and $$| {{\mathbb{V}}}_{n}| \,\le \,n\cdot {2}^{5.6n}$$ ∣ V n ∣ ≤ n ⋅ 2 5.6 n . 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 ( ( 4 n 2 ) ⌈ d / c ⌉ ) and $$O({({4}^{{n}^{2}})}^{(c-1)\lceil d/c\rceil })$$ O ( ( 4 n 2 ) ( c − 1 ) ⌈ d / c ⌉ ) respectively (d is 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 ( ( 3 n ⋅ 2 k n 2 ) ⌈ d 2 ⌉ ⋅ 2 k n 2 ) (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 ( n log n , 2 5.6 n , d ) with weaker assumptions). The claimed efficiency, optimality depends on conjectures.