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

arXiv:2506.16005

No-go theorems for sublinear-depth group designs

West, Maxwell, García-Martín, Diego, Diaz, N. L., Cerezo, M., Larocca, Martin

Published Jun 19, 2025• 1 citation
arXivHTMLPDF

Abstract

Constructing ensembles of circuits which efficiently approximate the Haar measure over various groups is a long-standing and fundamental problem in quantum information theory. Recently it was shown that one can obtain approximate designs over the unitary group with depths scaling logarithmically in the number of qubits, but that no sublinear-depth approximate designs exist over the orthogonal group. Here we derive, for any group $G$ possessing an invariant state $G^{\otimes k} \lvertΨ\rangle= \lvertΨ\rangle$, a lower bound on the diamond distance between the $k$\textsuperscript{th} moment operator of any ensemble of elements of $G$, and that of the Haar measure over $G$. We then use this bound to prove that for many groups of interest, no subset of $G$ consisting of sublinear-depth one-dimensional circuits with local gates can form an approximate $k$-design over $G$. More generally, on a $D$-dimensional lattice, our results imply that such group designs require depths scaling at least as $n^{1/D}$. Moreover, for most of the groups we consider we find that such ensembles can, with high probability, be distinguished from $k$-designs by a single shot of a constant-depth measurement. Among other examples, we show that there is a constant separation between (a) the maximum depth and gate count for which no circuit can approximate even the second moment of random matchgate circuits, and (b) the depth and gate count required to implement the matchgate Haar distribution exactly. We furthermore rule out the existence of sublinear-depth $8$-designs over the Clifford group. Finally, we relax the assumption of working with local gates, and prove the impossibility of obtaining approximate designs over $G$ using any circuit comprised of a sublinear number of gates generated by Pauli strings.

DOI
10.48550/arxiv.2506.16005

Related papers

Ambient unitaries don't enable shallow group designs

Maxwell West, M. Cerezo, Martin Larocca

Characterising the efficiency with which designs over various subsets of the unitary group may be constructed is an important goal of quantum information theory. While it is now known that approximate unitary designs can be realised in depth logarithmic in the system size, it has recently been shown that ensembles of local nearest-neighbour sublinear-depth one-dimensional circuits over the matchgate, orthogonal, and symplectic groups cannot form approximate 2-designs over their parent groups; similarly, sublinear-depth ensembles of Cliffords cannot form a Clifford 4-design. In this note we show that this remarkable exponential separation is not merely an artefact of restricting to ensembles consisting of unitaries from the subgroups themselves, but rather that no ensemble of local nearest-neighbour sublinear-depth unitaries can realise approximate designs in the aforementioned cases, even when employing "ambient" unitaries from beyond the subgroup itself (possibly acting on ancilla qubits). This implies that various natural tomography and benchmarking schemes which involves sampling from these groups suffer from a dramatic circuit depth overhead compared to similar protocols which involve sampling from the full unitary group. We additionally conclude that, in all of the above cases, the known linear-depth design constructions are up to constant factors optimal.

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

Strong matchgate designs in nearly optimal depth

Maxwell West, M. Cerezo, Martin Larocca

Understanding the resources required to generate approximately random unitaries over various groups is a natural goal of quantum information theory. With respect to one notion of approximation, that of a design, it is known that the full unitary group can be approximated in logarithmic depth by one-dimensional circuits of nearest-neighbour 2-local gates. On the other hand, remarkably, circuits with this connectivity cannot form designs over the matchgate group in sublinear depth. Here we show that this dramatic slowdown can disappear when using a general qubit connectivity graph $\mathsf{G}$ of routing number ${\rm rt}(\mathsf{G})$. Indeed, in this setting one can obtain (strong) $\varepsilon$-approximate relative error matchgate $k$-designs in depth $\mathcal{O}(k^2{\rm rt}(\mathsf{G})\log n\log(n/\varepsilon))$. For all-to-all connectivity, ${\rm rt}(\mathsf{G})=2$. Our construction is conceptually simple, involving a random walk on the matchgate group, and no ancillae. As a technical byproduct, we improve upon the state of the art for fermionic routing, obtaining an $\mathcal{O}({\rm rt}(\mathsf{G})\log n)$ depth router. Additionally, for $k=3$, we obtain an exact strong matchgate design in $\mathcal{O}({\rm rt}(\mathsf{G})\log n)$ depth, again without ancillae. Under all-to-all connectivity, our fermionic router and 3-designs are optimal. Notably, our results imply that quantum algorithms for fermionic tomography which require drawing from a matchgate 3-design may be exponentially sped up on quantum computers with all-to-all connectivity, relative to their strictly one-dimensional counterparts.

quant-pharXiv:2609.26677•Sep 23, 2026•0 citations

(Almost) quadruply optimal unitary designs in 1D

Guoding Liu, Jonas Helsen

We construct $n$-qubit approximate unitary $k$-designs in 1D systems, achieving circuit depth $O(\log(n/\varepsilon) + k\log k)$ with relative error $\varepsilon$ and requiring $O(nk\log k)$ magic gates. This matches existing lower bounds $Ω(\log(n/\varepsilon) + k)$ for circuit depth, and $\widetildeΩ(nk)$ for the required number of $T$ gates, up to a $\log k$ factor, achieving simultaneous near-optimality in all parameters. Our construction is based on a combination and refinement of two existing results. We reduce the required magic block size for breaking Clifford symmetries in the magic-augmented circuit construction of Zhang et al. from $O(k\log k)$ to $O(\log k)$. We also improve the breakthrough construction of Chen et al. to construct a generating set of 1D local constant-depth circuits for the unitary group with a constant spectral gap, making $O(\log k)$-local random unitaries realizable in depth $O(k\log k)$. As a by-product, we provide a constant-size 1D-local generating set for the Clifford group, which we expect to be of independent interest. Combining the two results with the gluing lemma, we prove the final result.

quant-pharXiv:2608.18650•Aug 20, 2026•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

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
Constructing ensembles of circuits which efficiently approximate the Haar measure over various groups is a long-standing and fundamental problem in quantum information theory. Recently it was shown that one can obtain approximate designs over the unitary group with depths scaling logarithmically in the number of qubits, but that no sublinear-depth approximate designs exist over the orthogonal group. Here we derive, for any group GGG possessing an invariant state G⊗k∣Ψ⟩=∣Ψ⟩G^{\otimes k} \lvertΨ\rangle= \lvertΨ\rangleG⊗k∣Ψ⟩=∣Ψ⟩, a lower bound on the diamond distance between the kkk\textsuperscript{th} moment operator of any ensemble of elements of GGG, and that of the Haar measure over GGG. We then use this bound to prove that for many groups of interest, no subset of GGG consisting of sublinear-depth one-dimensional circuits with local gates can form an approximate kkk-design over GGG. More generally, on a DDD-dimensional lattice, our results imply that such group designs require depths scaling at least as n1/Dn^{1/D}n1/D. Moreover, for most of the groups we consider we find that such ensembles can, with high probability, be distinguished from kkk-designs by a single shot of a constant-depth measurement. Among other examples, we show that there is a constant separation between (a) the maximum depth and gate count for which no circuit can approximate even the second moment of random matchgate circuits, and (b) the depth and gate count required to implement the matchgate Haar distribution exactly. We furthermore rule out the existence of sublinear-depth 888-designs over the Clifford group. Finally, we relax the assumption of working with local gates, and prove the impossibility of obtaining approximate designs over GGG using any circuit comprised of a sublinear number of gates generated by Pauli strings.
Characterising the efficiency with which designs over various subsets of the unitary group may be constructed is an important goal of quantum information theory. While it is now known that approximate unitary designs can be realised in depth logarithmic in the system size, it has recently been shown that ensembles of local nearest-neighbour sublinear-depth one-dimensional circuits over the matchgate, orthogonal, and symplectic groups cannot form approximate 2-designs over their parent groups; similarly, sublinear-depth ensembles of Cliffords cannot form a Clifford 4-design. In this note we show that this remarkable exponential separation is not merely an artefact of restricting to ensembles consisting of unitaries from the subgroups themselves, but rather that no ensemble of local nearest-neighbour sublinear-depth unitaries can realise approximate designs in the aforementioned cases, even when employing "ambient" unitaries from beyond the subgroup itself (possibly acting on ancilla qubits). This implies that various natural tomography and benchmarking schemes which involves sampling from these groups suffer from a dramatic circuit depth overhead compared to similar protocols which involve sampling from the full unitary group. We additionally conclude that, in all of the above cases, the known linear-depth design constructions are up to constant factors optimal.
Understanding the resources required to generate approximately random unitaries over various groups is a natural goal of quantum information theory. With respect to one notion of approximation, that of a design, it is known that the full unitary group can be approximated in logarithmic depth by one-dimensional circuits of nearest-neighbour 2-local gates. On the other hand, remarkably, circuits with this connectivity cannot form designs over the matchgate group in sublinear depth. Here we show that this dramatic slowdown can disappear when using a general qubit connectivity graph G\mathsf{G}G of routing number rt(G){\rm rt}(\mathsf{G})rt(G). Indeed, in this setting one can obtain (strong) ε\varepsilonε-approximate relative error matchgate kkk-designs in depth O(k2rt(G)log⁡nlog⁡(n/ε))\mathcal{O}(k^2{\rm rt}(\mathsf{G})\log n\log(n/\varepsilon))O(k2rt(G)lognlog(n/ε)). For all-to-all connectivity, rt(G)=2{\rm rt}(\mathsf{G})=2rt(G)=2. Our construction is conceptually simple, involving a random walk on the matchgate group, and no ancillae. As a technical byproduct, we improve upon the state of the art for fermionic routing, obtaining an O(rt(G)log⁡n)\mathcal{O}({\rm rt}(\mathsf{G})\log n)O(rt(G)logn) depth router. Additionally, for k=3k=3k=3, we obtain an exact strong matchgate design in O(rt(G)log⁡n)\mathcal{O}({\rm rt}(\mathsf{G})\log n)O(rt(G)logn) depth, again without ancillae. Under all-to-all connectivity, our fermionic router and 3-designs are optimal. Notably, our results imply that quantum algorithms for fermionic tomography which require drawing from a matchgate 3-design may be exponentially sped up on quantum computers with all-to-all connectivity, relative to their strictly one-dimensional counterparts.
We construct nnn-qubit approximate unitary kkk-designs in 1D systems, achieving circuit depth O(log⁡(n/ε)+klog⁡k)O(\log(n/\varepsilon) + k\log k)O(log(n/ε)+klogk) with relative error ε\varepsilonε and requiring O(nklog⁡k)O(nk\log k)O(nklogk) magic gates. This matches existing lower bounds Ω(log⁡(n/ε)+k)Ω(\log(n/\varepsilon) + k)Ω(log(n/ε)+k) for circuit depth, and Ω~(nk)\widetildeΩ(nk)Ω(nk) for the required number of TTT gates, up to a log⁡k\log klogk factor, achieving simultaneous near-optimality in all parameters. Our construction is based on a combination and refinement of two existing results. We reduce the required magic block size for breaking Clifford symmetries in the magic-augmented circuit construction of Zhang et al. from O(klog⁡k)O(k\log k)O(klogk) to O(log⁡k)O(\log k)O(logk). We also improve the breakthrough construction of Chen et al. to construct a generating set of 1D local constant-depth circuits for the unitary group with a constant spectral gap, making O(log⁡k)O(\log k)O(logk)-local random unitaries realizable in depth O(klog⁡k)O(k\log k)O(klogk). As a by-product, we provide a constant-size 1D-local generating set for the Clifford group, which we expect to be of independent interest. Combining the two results with the gluing lemma, we prove the final result.
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.
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.