Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Approximate Unitary k-Designs from Shallow, Low-Communication Circuits (Extended Abstract)

Nicholas D. LaRacuente, Felix Leditzky

Published Jan 1, 2025• 2 citations
Publisher

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. 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 l 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 l = 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. Twirl-Crosstwirl: Let A_1, … , 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, … , P; (2) apply a "crosstwirl" k-design unitary across a joint system combining l qudits from each A_p. Assuming each A_p’s dimension is sufficiently large compared to other parameters, one can choose l 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 → 2 norm, using communication logarithmic in k. 3. Recursive Crosstwirl: Consider an m-qudit system with connectivity given by a lattice in spatial dimension D. For every D = 1, 2, …, we give a construction of an ε-approximate relative k-design using unitaries of spatially local circuit depth O ((log m + log(1/ε) + k log k ) k polylog(k)). 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 [Harrow and Mehraban, 2023, Open Problem 1], showing that with a specific, layered architecture, random circuits produce relative error k-designs in sublinear depth. Moreover, it addresses [Harrow and Mehraban, 2023, Open Problem 7], showing that structured circuits in spatial dimension D of depth << m^{1/D} may achieve approximate k-designs.

DOI
10.4230/lipics.itcs.2025.69

Related papers

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

Nicholas D. LaRacuente, Felix Leditzky

Abstract Random unitaries are useful in quantum information and related fields, but hard to generate with limited resources. An approximate unitary k -design is an ensemble of unitaries with an underlying measure over which the average is close to a Haar random ensemble up to the first k moments. A particularly strong notion of approximation bounds the distance from Haar randomness in relative error. Such relative-error approximate designs are secure against queries by an adaptive adversary trying to distinguish it from a Haar ensemble. We construct relative-error approximate unitary k -design ensembles for which communication between subsystems is O (1) in the system size. These constructions use the alternating projection method to analyze overlapping Haar averages, giving a bound on the convergence speed to the full averaging 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 any additional dimension dependence. We use these constructions as the building blocks of a two-step protocol that achieves a relative-error design in $$O \big ( (\log m + \log (1/\epsilon ) + k \log k ) k\, \text {polylog}(k) \big )$$ O ( ( log m + log ( 1 / ϵ ) + k log k ) k polylog ( k ) ) depth, where m is the number of qudits in the complete system and $$\epsilon $$ ϵ the approximation error. This sublinear depth construction answers a variant of [21, Harrow and Mehraban 2023, Section 1.5, Open Question 1] and [21, Harrow and Mehraban 2023, Section 1.5, Open Question 7]. Moreover, entanglement generated by the sublinear depth scheme follows area laws on spatial lattices up to corrections logarithmic in the full system size.

arXiv:2407.07876•Communications in Mathematical Physics•Feb 5, 2026•8 citations

Strong unitary designs in optimal depth and space

Teodor Parella-Dilmé, Júlia Barberà-Rodríguez, Salvatore F. E. Oliviero +1 more

Unitary designs provide finite-moment approximations to Haar-random unitaries, with wide-ranging applications across physics and quantum information, from scrambling and black-hole dynamics to foundational primitives in quantum algorithms. Strong unitary designs capture a more demanding operational notion of approximation, requiring indistinguishability from Haar randomness even for quantum algorithms that may access a unitary not only in the forward direction, but also through its inverse, transpose, and complex conjugate. Motivated by the physical requirement that scrambling arise within the system itself, Schuster, Ma, Lombardi, Brandão, and Huang (arXiv:2509.26310) left open whether strong unitary designs can be generated in logarithmic depth using only the system qubits. For every fixed design order $k$ and measurable-error tolerance, we construct strong approximate unitary $k$-designs in optimal $Θ(\log n)$ all-to-all circuit depth using only the $n$ original system qubits. Our new ingredient is a logarithmic-depth Pauli-mixing bound for the perfect-matching ensemble, whose layers pair the qubits uniformly at random and apply independent random two-qubit gates. This bound controls the mixed forward-reverse two-query case, which we combine with existing design and gluing results to obtain strong unitary designs of arbitrary fixed order.

quant-pharXiv:2608.13491•Aug 14, 2026•0 citations

Shallow Approximate Unitary Designs from Relative Entropy Decay of Unstructured Random Circuits

Nicholas D. LaRacuente

Approximate unitary k-designs are ensembles of unitary matrices whose first k statistical moments approximate the Haar (uniform) measure. Shallow, random quantum circuits with temporally and spatially structured architectures are known to yield approximate k-designs in depth that is logarithmic in the number of qubits. It was open whether this structure is physically necessary. Shown here is shallow relative entropy convergence for standard notions of less structured, time-periodic circuits, implying additive-error approximate k-designs in nearly logarithmic depth (up to sub-logarithmic factors). These architectures include 1-dimensional brickwork and gates placed randomly according to a connected, bounded-degree graph. Relative entropy recombination methods derived herein are potentially of independent interest.

arXiv:2510.08537•Oct 9, 2025•0 citations

Efficient Unitary Designs with a System-Size Independent Number of Non-Clifford Gates

Jonas Haferkamp, Felipe Montealegre‐Mora, Markus Heinrich +3 more

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.

arXiv:2002.09524•Communications in Mathematical Physics•Nov 12, 2022•51 citations

Quantum state learning beyond approximate unitary designs

Gyungmin Cho, Changhun Oh, Dohun Kim

Approximate unitary designs reproduce the statistics of Haar-random unitaries to a given order and accuracy. Recent constructions realize such designs with logarithmic-depth circuits, enabling shallow measurement protocols for various quantum state-learning tasks while preserving performance. These results raise the question of whether approximate designs can replace exact designs more generally. We show that even exponentially small design error need not preserve the learning guarantees of exact designs. This motivates deriving learning guarantees directly from the measurement circuit structure. For observable estimation with classical shadows, we prove that logarithmic-depth two-layer Clifford circuits yield an unbiased estimator matching the global Clifford variance scaling for every state and Hermitian observable. Beyond observable estimation, this bound allows shallow measurements to retain global Clifford guarantees for other tasks, including setting-efficient tomography, mixed-state metrology, and stabilizer structure learning. We complement these statistical guarantees with a compact, exact tensor-network representation of the inverse shadow channel. When measurement bases are reused, approximate unitary designs of arbitrarily high order need not uniformly match the Haar variance in the many-shot limit. For the all-to-all random two-local circuits considered, doing so requires nearly linear depth. Together, our results reveal the capabilities and limitations of shallow quantum state learning, highlighting the distinction between approximating Haar randomness and reproducing its learning guarantees.

quant-pharXiv:2609.39994•Oct 1, 2026•0 citations

Epsilon-Nets, Unitary Designs, and Random Quantum Circuits

Michał Oszmaniec, Adam Sawicki, Michał Horodecki

Epsilon-nets and approximate unitary$t$-designs are natural notions that capture properties of unitary operations relevant for numerous applications in quantum information and quantum computing. In this work we study quantitative connections between these two notions. Specifically, we prove that, for$d$dimensional Hilbert space, unitaries constituting$\delta $-approximate$t$-expanders form$\epsilon $-nets for$t\simeq \frac {d^{5/2}}{ \epsilon }$and$\delta \simeq \left ({\frac { \epsilon ^{3/2}}{d}}\right)^{d^{2}}$. We also show that for arbitrary$t$,$\epsilon $-nets can be used to construct$\delta $-approximate unitary$t$-designs for$\delta \simeq \epsilon t$, where the notion of approximation is based on the diamond norm. Finally, we prove that the degree of an exact unitary$t$design necessary to obtain an$\epsilon $-net must grow at least as fast as$\frac {1}{ \epsilon }$(for fixed dimension) and not slower than$d^{2}$(for fixed$\epsilon $). This shows near optimality of our result connecting$t$-designs and$\epsilon $-nets. We apply our findings in the context of quantum computing. First, we show that that approximate t-designs can be generated by shallow random circuits formed from a set of universal two-qudit gates in the parallel and sequential local architectures considered in (Brandão et al., 2016). Importantly, our gate sets need not to be symmetric (i.e., contains gates together with their inverses) or consist of gates with algebraic entries. Second, we consider compilation of quantum gates and prove a non-constructive Solovay-Kitaev theorem for general universal gate sets. Our main technical contribution is a new construction of efficient polynomial approximations to the Dirac delta in the space of quantum channels, which can be of independent interest.

arXiv:2007.10885•IEEE Transactions on Information Theory•Nov 13, 2021•27 citations
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. 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 l 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 l = 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. Twirl-Crosstwirl: Let A_1, … , 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, … , P; (2) apply a "crosstwirl" k-design unitary across a joint system combining l qudits from each A_p. Assuming each A_p’s dimension is sufficiently large compared to other parameters, one can choose l 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 → 2 norm, using communication logarithmic in k. 3. Recursive Crosstwirl: Consider an m-qudit system with connectivity given by a lattice in spatial dimension D. For every D = 1, 2, …, we give a construction of an ε-approximate relative k-design using unitaries of spatially local circuit depth O ((log m + log(1/ε) + k log k ) k polylog(k)). 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 [Harrow and Mehraban, 2023, Open Problem 1], showing that with a specific, layered architecture, random circuits produce relative error k-designs in sublinear depth. Moreover, it addresses [Harrow and Mehraban, 2023, Open Problem 7], showing that structured circuits in spatial dimension D of depth << m^{1/D} may achieve approximate k-designs.
Abstract Random unitaries are useful in quantum information and related fields, but hard to generate with limited resources. An approximate unitary k -design is an ensemble of unitaries with an underlying measure over which the average is close to a Haar random ensemble up to the first k moments. A particularly strong notion of approximation bounds the distance from Haar randomness in relative error. Such relative-error approximate designs are secure against queries by an adaptive adversary trying to distinguish it from a Haar ensemble. We construct relative-error approximate unitary k -design ensembles for which communication between subsystems is O (1) in the system size. These constructions use the alternating projection method to analyze overlapping Haar averages, giving a bound on the convergence speed to the full averaging 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 any additional dimension dependence. We use these constructions as the building blocks of a two-step protocol that achieves a relative-error design in O((log⁡m+log⁡(1/ϵ)+klog⁡k)k polylog(k))O \big ( (\log m + \log (1/\epsilon ) + k \log k ) k\, \text {polylog}(k) \big )O((logm+log(1/ϵ)+klogk)kpolylog(k)) O ( ( log m + log ( 1 / ϵ ) + k log k ) k polylog ( k ) ) depth, where m is the number of qudits in the complete system and ϵ\epsilon ϵ ϵ the approximation error. This sublinear depth construction answers a variant of [21, Harrow and Mehraban 2023, Section 1.5, Open Question 1] and [21, Harrow and Mehraban 2023, Section 1.5, Open Question 7]. Moreover, entanglement generated by the sublinear depth scheme follows area laws on spatial lattices up to corrections logarithmic in the full system size.
Unitary designs provide finite-moment approximations to Haar-random unitaries, with wide-ranging applications across physics and quantum information, from scrambling and black-hole dynamics to foundational primitives in quantum algorithms. Strong unitary designs capture a more demanding operational notion of approximation, requiring indistinguishability from Haar randomness even for quantum algorithms that may access a unitary not only in the forward direction, but also through its inverse, transpose, and complex conjugate. Motivated by the physical requirement that scrambling arise within the system itself, Schuster, Ma, Lombardi, Brandão, and Huang (arXiv:2509.26310) left open whether strong unitary designs can be generated in logarithmic depth using only the system qubits. For every fixed design order kkk and measurable-error tolerance, we construct strong approximate unitary kkk-designs in optimal Θ(log⁡n)Θ(\log n)Θ(logn) all-to-all circuit depth using only the nnn original system qubits. Our new ingredient is a logarithmic-depth Pauli-mixing bound for the perfect-matching ensemble, whose layers pair the qubits uniformly at random and apply independent random two-qubit gates. This bound controls the mixed forward-reverse two-query case, which we combine with existing design and gluing results to obtain strong unitary designs of arbitrary fixed order.
Approximate unitary k-designs are ensembles of unitary matrices whose first k statistical moments approximate the Haar (uniform) measure. Shallow, random quantum circuits with temporally and spatially structured architectures are known to yield approximate k-designs in depth that is logarithmic in the number of qubits. It was open whether this structure is physically necessary. Shown here is shallow relative entropy convergence for standard notions of less structured, time-periodic circuits, implying additive-error approximate k-designs in nearly logarithmic depth (up to sub-logarithmic factors). These architectures include 1-dimensional brickwork and gates placed randomly according to a connected, bounded-degree graph. Relative entropy recombination methods derived herein are potentially of independent interest.
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(t4log⁡2(t)log⁡(1/ε))O(t^{4}\log ^{2}(t)\log (1/\varepsilon ))O(t4log2(t)log(1/ε)) 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.
Approximate unitary designs reproduce the statistics of Haar-random unitaries to a given order and accuracy. Recent constructions realize such designs with logarithmic-depth circuits, enabling shallow measurement protocols for various quantum state-learning tasks while preserving performance. These results raise the question of whether approximate designs can replace exact designs more generally. We show that even exponentially small design error need not preserve the learning guarantees of exact designs. This motivates deriving learning guarantees directly from the measurement circuit structure. For observable estimation with classical shadows, we prove that logarithmic-depth two-layer Clifford circuits yield an unbiased estimator matching the global Clifford variance scaling for every state and Hermitian observable. Beyond observable estimation, this bound allows shallow measurements to retain global Clifford guarantees for other tasks, including setting-efficient tomography, mixed-state metrology, and stabilizer structure learning. We complement these statistical guarantees with a compact, exact tensor-network representation of the inverse shadow channel. When measurement bases are reused, approximate unitary designs of arbitrarily high order need not uniformly match the Haar variance in the many-shot limit. For the all-to-all random two-local circuits considered, doing so requires nearly linear depth. Together, our results reveal the capabilities and limitations of shallow quantum state learning, highlighting the distinction between approximating Haar randomness and reproducing its learning guarantees.
Epsilon-nets and approximate unitaryttt-designs are natural notions that capture properties of unitary operations relevant for numerous applications in quantum information and quantum computing. In this work we study quantitative connections between these two notions. Specifically, we prove that, forddddimensional Hilbert space, unitaries constituting$\delta −approximate-approximate−approximatet−expandersform-expanders form−expandersform\epsilon −netsfor-nets for−netsfort\simeq \frac {d^{5/2}}{ \epsilon }andandand\delta \simeq \left ({\frac { \epsilon ^{3/2}}{d}}\right)^{d^{2}}.Wealsoshowthatforarbitrary. We also show that for arbitrary.Wealsoshowthatforarbitraryt,,,\epsilon −netscanbeusedtoconstruct-nets can be used to construct−netscanbeusedtoconstruct\delta −approximateunitary-approximate unitary−approximateunitaryt−designsfor-designs for−designsfor\delta \simeq \epsilon t,wherethenotionofapproximationisbasedonthediamondnorm.Finally,weprovethatthedegreeofanexactunitary, where the notion of approximation is based on the diamond norm. Finally, we prove that the degree of an exact unitary,wherethenotionofapproximationisbasedonthediamondnorm.Finally,weprovethatthedegreeofanexactunitarytdesignnecessarytoobtainandesign necessary to obtain andesignnecessarytoobtainan\epsilon −netmustgrowatleastasfastas-net must grow at least as fast as−netmustgrowatleastasfastas\frac {1}{ \epsilon }(forfixeddimension)andnotslowerthan(for fixed dimension) and not slower than(forfixeddimension)andnotslowerthand^{2}(forfixed(for fixed(forfixed\epsilon ).Thisshowsnearoptimalityofourresultconnecting). This shows near optimality of our result connecting).Thisshowsnearoptimalityofourresultconnectingt−designsand-designs and−designsand\epsilon $-nets. We apply our findings in the context of quantum computing. First, we show that that approximate t-designs can be generated by shallow random circuits formed from a set of universal two-qudit gates in the parallel and sequential local architectures considered in (Brandão et al., 2016). Importantly, our gate sets need not to be symmetric (i.e., contains gates together with their inverses) or consist of gates with algebraic entries. Second, we consider compilation of quantum gates and prove a non-constructive Solovay-Kitaev theorem for general universal gate sets. Our main technical contribution is a new construction of efficient polynomial approximations to the Dirac delta in the space of quantum channels, which can be of independent interest.