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:2608.13528

Ambient unitaries don't enable shallow group designs

Maxwell West, M. Cerezo, Martin Larocca

quant-phSubmitted Aug 13, 2026• Announced Aug 14, 2026• 3 citations
arXivHTMLPDF

Abstract

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.

Comments
10 pages, 1 figure

Related papers

No-go theorems for sublinear-depth group designs

Maxwell West, Diego García-Martín, N. L. Diaz +2 more

Constructing ensembles of circuits which efficiently approximate the Haar measure over various groups is a fundamental problem in quantum information theory, with breakthrough recent results showing that for the unitary group this can be achieved with depths scaling logarithmically in the system size. Here we prove that, for groups G possessing an invariant state $${G}^{\otimes k}\left\vert \Psi \right\rangle=\left\vert \Psi \right\rangle$$ satisfying certain conditions on its entanglement structure, no subset of G consisting of sublinear-depth one-dimensional circuits with constant-locality gates can form an approximate k-design over G. More generally, on a D-dimensional lattice of side-length n, our results imply that such group designs require depths scaling at least as n1/D. Among other examples, we show that there is a constant separation between the maximum depth and gate counts for which no circuit can approximate even the second moment of random matchgate circuits, and those required to implement the matchgate Haar distribution exactly. 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. Significant effort has been spent to find low-depth constructions of random unitaries that appear Haar-random to a restricted observer, and earlier works showed logarithmic-depth approximate designs over the full unitary group using local random circuits. In this paper, the authors provide a general criterion ruling out shallow designs on a wide variety of groups.

arXiv:2506.16005•Nature Communications•Nov 2, 2026•19 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•3 citations

Strong matchgate designs in nearly optimal depth — E8 Intelligence Research

Andrew Stewart Caldin

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 technica Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 10, 2026•0 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•2 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•3 citations

Unitary designs in nearly optimal depth

Cui, Laura, Thomas Schuster, Fernando G. S. L. Brandão +1 more

We construct $\varepsilon$-approximate unitary $k$-designs on $n$ qubits in circuit depth $O(\log k \log \log n k / \varepsilon)$. The depth is exponentially improved over all known results in all three parameters $n$, $k$, $\varepsilon$. We further show that each dependence is optimal up to exponentially smaller factors. Our construction uses $\tilde{O}(nk)$ ancilla qubits and ${O}(nk)$ bits of randomness, which are also optimal up to $\log(n k)$ factors. An alternative construction achieves a smaller ancilla count $\tilde{O}(n)$ with circuit depth ${O}(k \log \log nk/\varepsilon)$. To achieve these efficient unitary designs, we introduce a highly-structured random unitary ensemble that leverages long-range two-qubit gates and low-depth implementations of random classical hash functions. We also develop a new analytical framework for bounding errors in quantum experiments involving many queries to random unitaries. As an illustration of this framework's versatility, we provide a succinct alternative proof of the existence of pseudorandom unitaries.

arXiv:2507.06216•Jul 8, 2025•52 citations
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.
Constructing ensembles of circuits which efficiently approximate the Haar measure over various groups is a fundamental problem in quantum information theory, with breakthrough recent results showing that for the unitary group this can be achieved with depths scaling logarithmically in the system size. Here we prove that, for groups G possessing an invariant state G⊗k∣Ψ⟩=∣Ψ⟩{G}^{\otimes k}\left\vert \Psi \right\rangle=\left\vert \Psi \right\rangleG⊗k∣Ψ⟩=∣Ψ⟩ satisfying certain conditions on its entanglement structure, no subset of G consisting of sublinear-depth one-dimensional circuits with constant-locality gates can form an approximate k-design over G. More generally, on a D-dimensional lattice of side-length n, our results imply that such group designs require depths scaling at least as n1/D. Among other examples, we show that there is a constant separation between the maximum depth and gate counts for which no circuit can approximate even the second moment of random matchgate circuits, and those required to implement the matchgate Haar distribution exactly. 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. Significant effort has been spent to find low-depth constructions of random unitaries that appear Haar-random to a restricted observer, and earlier works showed logarithmic-depth approximate designs over the full unitary group using local random circuits. In this paper, the authors provide a general criterion ruling out shallow designs on a wide variety of groups.
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.
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 technica Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
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.
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.
We construct ε\varepsilonε-approximate unitary kkk-designs on nnn qubits in circuit depth O(log⁡klog⁡log⁡nk/ε)O(\log k \log \log n k / \varepsilon)O(logkloglognk/ε). The depth is exponentially improved over all known results in all three parameters nnn, kkk, ε\varepsilonε. We further show that each dependence is optimal up to exponentially smaller factors. Our construction uses O~(nk)\tilde{O}(nk)O~(nk) ancilla qubits and O(nk){O}(nk)O(nk) bits of randomness, which are also optimal up to log⁡(nk)\log(n k)log(nk) factors. An alternative construction achieves a smaller ancilla count O~(n)\tilde{O}(n)O~(n) with circuit depth O(klog⁡log⁡nk/ε){O}(k \log \log nk/\varepsilon)O(kloglognk/ε). To achieve these efficient unitary designs, we introduce a highly-structured random unitary ensemble that leverages long-range two-qubit gates and low-depth implementations of random classical hash functions. We also develop a new analytical framework for bounding errors in quantum experiments involving many queries to random unitaries. As an illustration of this framework's versatility, we provide a succinct alternative proof of the existence of pseudorandom unitaries.