Efficient Unitary Designs with a System-Size Independent Number of Non-Clifford Gates
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 ))$$ O ( t 4 log 2 ( t ) log ( 1 / ε ) ) many non-Clifford gates into a polynomial-depth random Clifford circuit to obtain an $$\varepsilon $$ ε -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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Nov 12, 2022
- Source ID
- 10.1007/s00220-022-04507-6
Entities
People
- Dustin E. Gross
- F. Montealegre-mora
- I. Roth
- J. Eisert
- J. Haferkamp
- Mary Katherine Heinrich
Organizations
- Army Research Office
- German Research Foundation
- John Templeton Foundation