T-count and T-depth of any multi-qubit unitary

Abstract

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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mfenced> <mml:mrow> <mml:msup> <mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:mfenced> </mml:mrow> </mml:math> and $$O\left({2}^{2n{{{{\mathcal{T}}}}}_{\epsilon }(W)+4n}\right)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mfenced> <mml:mrow> <mml:msup> <mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> <mml:msub> <mml:mrow> <mml:mi>T</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>W</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>+</mml:mo> <mml:mn>4</mml:mn> <mml:mi>n</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:mfenced> </mml:mrow> </mml:math> , respectively. $${{{{\mathcal{T}}}}}_{\epsilon }(W)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mrow> <mml:mi>T</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>W</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> ( ϵ -T-count) is the (minimum) T-count of an exactly implementable unitary U ( $${{{\mathcal{T}}}}(U)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>T</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>U</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> ), such that d ( U , W ) ≤ ϵ and $${{{\mathcal{T}}}}(U)\le {{{\mathcal{T}}}}({U}^{{\prime} })$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>T</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>U</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>≤</mml:mo> <mml:mi>T</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:msup> <mml:mrow> <mml:mi>U</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>′</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> where $${U}^{{\prime} }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>U</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>′</mml:mo> </mml:mrow> </mml:msup> </mml:math> is any exactly implementable unitary with $$d({U}^{{\prime} },W)\le \epsilon$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:msup> <mml:mrow> <mml:mi>U</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>′</mml:mo> </mml:mrow> </mml:msup> <mml:mo>,</mml:mo> <mml:mi>W</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>≤</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:math> . 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.

Topics & Concepts