Efficient Unitary Designs with a System-Size Independent Number of Non-Clifford Gates
Jonas Haferkamp, Felipe Montealegre‐Mora, Markus Heinrich, Jens Eisert, D. Gross, Ingo Roth
Abstract
Abstract Many quantum information protocols require the implementation of random unitaries. Because it takes exponential resources to produce Haar-random unitaries drawn from the full n -qubit group, one often resorts to t -designs. Unitary t -designs mimic the Haar-measure up to t -th moments. It is known that Clifford operations can implement at most 3-designs. In this work, we quantify the non-Clifford resources required to break this barrier. We find that it suffices to inject $$O(t^{4}\log ^{2}(t)\log (1/\varepsilon ))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>t</mml:mi> <mml:mn>4</mml:mn> </mml:msup> <mml:msup> <mml:mo>log</mml:mo> <mml:mn>2</mml:mn> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>t</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>log</mml:mo> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mi>ε</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> many non-Clifford gates into a polynomial-depth random Clifford circuit to obtain an $$\varepsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> -approximate t -design. Strikingly, the number of non-Clifford gates required is independent of the system size – asymptotically, the density of non-Clifford gates is allowed to tend to zero. We also derive novel bounds on the convergence time of random Clifford circuits to the t -th moment of the uniform distribution on the Clifford group. Our proofs exploit a recently developed variant of Schur-Weyl duality for the Clifford group, as well as bounds on restricted spectral gaps of averaging operators.