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

Unitary designs in nearly optimal depth

Cui, Laura, Thomas Schuster, Fernando G. S. L. Brandão, Hsin-Yuan Huang

Published Jul 8, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2507.06216

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

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

All Unitaries Have Constant Depth Quantum Circuits

Barak Nehoran, Joseph Slote, Henry Yuen

It is well-known that every $n$-qubit unitary can be implemented by a $2^{O(n)}$-depth quantum circuit using single- and two-qubit gates. It has been open whether exponential depth is *necessary* for general unitaries, even when allowing an unlimited number of ancilla qubits. Here we show, perhaps surprisingly, that all unitaries can be implemented exactly by a circuit of one- and two-qubit gates of depth $\mathsf{poly}(n)$ with $2^{O(n)}$ ancilla qubits. In other words, every $n$-qubit unitary can be parallelized to polynomial depth. In fact, our depth bound is *linear* in $n$, which is the best possible, and an exponential improvement on the previous best bound of $2^{n/2}$ due to Rosenthal [TQC 2022, Quantum 2026]. Moreover, if we allow unbounded fan-out gates, these circuits can be further reduced to *constant* depth. Our construction takes advantage of a novel relationship connecting the unitary synthesis problem of Aaronson and Kuperberg to locally-decodable codes and private information retrieval from complexity theory and cryptography, and has a natural interpretation in bosonic quantum computation.

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

Random Unitaries in Constant (Quantum) Time

Ben Foxman, Natalie Parham, Francisca Vasconcelos +1 more

Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work has constructed unitary designs and pseudorandom unitaries (PRUs) using Θ(log log n)-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of constant-time quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit TOFFOLI gates, (b) many-qubit FANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit TOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class QAC⁰. Finally, our results suggest a new approach towards proving that PARITY is not computable in QAC⁰, a long-standing question in quantum complexity theory.

Leibniz international proceedings in informatics•Jan 1, 2026•0 citations
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.
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.
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.
It is well-known that every nnn-qubit unitary can be implemented by a 2O(n)2^{O(n)}2O(n)-depth quantum circuit using single- and two-qubit gates. It has been open whether exponential depth is *necessary* for general unitaries, even when allowing an unlimited number of ancilla qubits. Here we show, perhaps surprisingly, that all unitaries can be implemented exactly by a circuit of one- and two-qubit gates of depth poly(n)\mathsf{poly}(n)poly(n) with 2O(n)2^{O(n)}2O(n) ancilla qubits. In other words, every nnn-qubit unitary can be parallelized to polynomial depth. In fact, our depth bound is *linear* in nnn, which is the best possible, and an exponential improvement on the previous best bound of 2n/22^{n/2}2n/2 due to Rosenthal [TQC 2022, Quantum 2026]. Moreover, if we allow unbounded fan-out gates, these circuits can be further reduced to *constant* depth. Our construction takes advantage of a novel relationship connecting the unitary synthesis problem of Aaronson and Kuperberg to locally-decodable codes and private information retrieval from complexity theory and cryptography, and has a natural interpretation in bosonic quantum computation.
Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work has constructed unitary designs and pseudorandom unitaries (PRUs) using Θ(log log n)-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of constant-time quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit TOFFOLI gates, (b) many-qubit FANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit TOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class QAC⁰. Finally, our results suggest a new approach towards proving that PARITY is not computable in QAC⁰, a long-standing question in quantum complexity theory.