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

Arts & crafts: Strong random unitaries and geometric locality

Marten Folkertsma, Lorenzo Grevink, Jonas Helsen, Alicja Dutkiewicz

quant-phSubmitted May 4, 2026• Announced May 6, 2026• 0 citations
arXivHTMLPDF

Abstract

We study the problem of constructing strong approximate unitary $k$-designs on $D$-dimensional grids (and more generally on Cartesian products of graphs), building on the work of Schuster et al. arXiv:2509.26310 which establishes strong unitary designs in 1D and in all-to-all connectivity. We provide two constructions. The first construction leverages the existing all-to-all connectivity result with general routing theory to provide flexible (but slightly suboptimal) strong $k$-designs in arbitrary connectivities. The second construction is more direct, requires no auxiliaries and has provably optimal depth (in the number of qubits $n$) for $D$-dimensional grids with constant dimension. Combining these techniques also allows us to construct strong pseudorandom unitaries on $D$-dimensional grids with provably optimal depth.

Comments
12 + 2 pages, 2 figures

Related papers

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

Low-Depth Random Unitaries without Ancillae

Zhenyu Du, Siyuan Cheng, Xiongfeng Ma

Random unitaries are fundamental to quantum information and many-body physics, with widespread applications ranging from quantum learning and metrology to device benchmarking. A central pursuit is to minimize the space and circuit depth required to generate them. However, existing methods for generating low-depth random unitaries rely heavily on an extensive number of ancillary qubits, imposing severe spatial overhead. In this work, we prove that random unitaries can be generated in optimal depth without ancillae. For multiplicative-error approximate $k$-designs on $n$ qubits, our circuits achieve a depth of $\widetilde{O} (k) (\log n)^{1/δ}$ on $δ$-dimensional architectures and $\widetilde{O}(k) \log \log n$ with all-to-all connectivity. Furthermore, by introducing a general exactification lemma, we lift our construction to optimal-depth exact $k$-designs, yielding an exponential resource reduction over state-of-the-art exact constructions. Our results minimize the space-time costs for a wide range of quantum protocols.

quant-pharXiv:2609.06528•Sep 8, 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

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•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

Efficient Unitary Designs from Random Sums and Permutations

Chi-Fang Chen, Jordan Docter, Michelle Xu +3 more

A unitary k-design is an ensemble of unitaries that matches the first$k$moments of the Haar measure. In this work, we provide two efficient constructions of k-designs on n-qubits using new random matrix theory techniques. Our first construction is based on exponentiating sums of random i.i.d. Hermitian matrices and uses O(k2n2)-many gates. In the spirit of central limit theorems, we show that this random sum approximates the Gaussian Unitary Ensemble (GUE). We then show that the product of just two exponentiated GUE matrices is already approximately Haar random. Our second construction is based on products of exponentiated sums of random permutations and uses Õ($k$poly ($n$)) many gates. The$k$dependence is optimal (up to polylogarithmic factors) and is inherited from the efficiency of existing k-wise independent permutations. Furthermore, replacing random permutations with quantum-secure pseudorandom permutations (PRPs), we also obtain a pseudorandom unitary (PRU) ensemble that is secure under nonadaptive queries. A central feature of both proofs is a new connection between the polynomial method in quantum query complexity and the large-dimension ($N$) expansion in random matrix theory. In particular, the first construction uses the polynomial method to control high moments of certain random matrix ensembles without requiring delicate Weingarten calculations. In doing so, we define and solve a moment problem on the unit circle, asking whether a finite number of equally weighted points can reproduce a given set of moments. In our second construction, the key step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large-$N$expansion. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimension$N$.

Annual Symposium on Foundations of Computer Science•Oct 27, 2024•13 citations
We study the problem of constructing strong approximate unitary kkk-designs on DDD-dimensional grids (and more generally on Cartesian products of graphs), building on the work of Schuster et al. arXiv:2509.26310 which establishes strong unitary designs in 1D and in all-to-all connectivity. We provide two constructions. The first construction leverages the existing all-to-all connectivity result with general routing theory to provide flexible (but slightly suboptimal) strong kkk-designs in arbitrary connectivities. The second construction is more direct, requires no auxiliaries and has provably optimal depth (in the number of qubits nnn) for DDD-dimensional grids with constant dimension. Combining these techniques also allows us to construct strong pseudorandom unitaries on DDD-dimensional grids with provably optimal depth.
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.
Random unitaries are fundamental to quantum information and many-body physics, with widespread applications ranging from quantum learning and metrology to device benchmarking. A central pursuit is to minimize the space and circuit depth required to generate them. However, existing methods for generating low-depth random unitaries rely heavily on an extensive number of ancillary qubits, imposing severe spatial overhead. In this work, we prove that random unitaries can be generated in optimal depth without ancillae. For multiplicative-error approximate kkk-designs on nnn qubits, our circuits achieve a depth of O~(k)(log⁡n)1/δ\widetilde{O} (k) (\log n)^{1/δ}O(k)(logn)1/δ on δδδ-dimensional architectures and O~(k)log⁡log⁡n\widetilde{O}(k) \log \log nO(k)loglogn with all-to-all connectivity. Furthermore, by introducing a general exactification lemma, we lift our construction to optimal-depth exact kkk-designs, yielding an exponential resource reduction over state-of-the-art exact constructions. Our results minimize the space-time costs for a wide range of quantum protocols.
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.
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.
A unitary k-design is an ensemble of unitaries that matches the firstkkkmoments of the Haar measure. In this work, we provide two efficient constructions of k-designs on n-qubits using new random matrix theory techniques. Our first construction is based on exponentiating sums of random i.i.d. Hermitian matrices and uses O(k2n2)-many gates. In the spirit of central limit theorems, we show that this random sum approximates the Gaussian Unitary Ensemble (GUE). We then show that the product of just two exponentiated GUE matrices is already approximately Haar random. Our second construction is based on products of exponentiated sums of random permutations and uses Õ(kkkpoly (nnn)) many gates. Thekkkdependence is optimal (up to polylogarithmic factors) and is inherited from the efficiency of existing k-wise independent permutations. Furthermore, replacing random permutations with quantum-secure pseudorandom permutations (PRPs), we also obtain a pseudorandom unitary (PRU) ensemble that is secure under nonadaptive queries. A central feature of both proofs is a new connection between the polynomial method in quantum query complexity and the large-dimension (NNN) expansion in random matrix theory. In particular, the first construction uses the polynomial method to control high moments of certain random matrix ensembles without requiring delicate Weingarten calculations. In doing so, we define and solve a moment problem on the unit circle, asking whether a finite number of equally weighted points can reproduce a given set of moments. In our second construction, the key step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large-NNNexpansion. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimensionNNN.