Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits

Abstract

Random unitaries are useful in quantum information and related fields but hard to generate with limited resources. An approximate unitary $k$-design is a measure over an ensemble of unitaries such that the average is close to a Haar (uniformly) random ensemble up to the first $k$ moments. A strong notion of approximation bounds the distance from Haar randomness in relative error: the weighted twirl induced by an approximate design can be written as a convex combination involving that of an exact design and vice versa. The main focus of our work is on efficient constructions of approximate designs, in particular whether relative-error designs in sublinear depth are possible. We give a positive answer to this question as part of our main results:

1. 1.

   Twirl-Swap-Twirl: Let $A$ and $B$ be systems of the same size. Consider a protocol that locally applies $k$-design unitaries to $A^k$ and $B^k$ respectively, then exchanges $\mathrm{\ell }$ qudits between each copy of $A$ and $B$ respectively, then again applies local $k$-design unitaries. This protocol yields an $ϵ$-approximate relative $k$-design when $\mathrm{\ell }=O(k\log k+\log (1/ϵ))$. In particular, this bound is independent of the size of $A$ and $B$ as long as it is sufficiently large compared to $k$ and $1/ϵ$.

2. 2.

   Twirl-Crosstwirl: Let $A_1,\mathrm{\dots },A_P$ be subsystems of a multipartite system $A$. Consider the following protocol for $k$ copies of $A$: (1) locally apply a $k$-design unitary to each $A_p$ for $p=1,\mathrm{\dots },P$; (2) apply a “crosstwirl” $k$-design unitary across a joint system combining $\mathrm{\ell }$ qudits from each $A_p$. Assuming each $A_p$’s dimension is sufficiently large compared to other parameters, one can choose $\mathrm{\ell }$ to be of the form $2(Pk+1){\log }_{q}k+{\log }_{q}P+{\log }_q(1/ϵ)+O(1)$ to achieve an $ϵ$-approximate relative k-design. As an intermediate step, we show that this protocol achieves a $k$-tensor-product-expander, in which the approximation error is in $2\to 2$ norm, using communication logarithmic in $k$.

3. 3.

   Recursive Crosstwirl: Consider an $m$-qudit system with connectivity given by a lattice in spatial dimension $D$. For every $D=1,2,\mathrm{\dots }$, we give a construction of an $ϵ$-approximate relative $k$-design using unitaries of spatially local circuit depth

   $O\left((\log m+\log (1/ϵ)+k\log k)k\mathrm{polylog}(k)\right).$

   Moreover, across the boundaries of spatially contiguous sub-regions, unitaries used in the design ensemble require only area law communication up to corrections logarithmic in $m$. Hence they generate only that much entanglement on any product state input.

These constructions use the alternating projection method to analyze overlapping Haar twirls, giving a bound on the convergence speed to the full twirl with respect to the $2$-norm. Using von Neumann subalgebra indices to replace system dimension, the 2-norm distance converts to relative error without introducing system size. The Recursive Crosstwirl construction answers one variant of [1, Open Problem 1], showing that with a specific, layered architecture, random circuits produce relative error $k$-designs in sublinear depth. Moreover, it addresses [1, Open Problem 7], showing that structured circuits in spatial dimension $D$ of depth $\ll m^{1/D}$ may achieve approximate $k$-designs.