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

Low-Depth Random Unitaries without Ancillae

Zhenyu Du, Siyuan Cheng, Xiongfeng Ma

quant-phSubmitted Sep 6, 2026• Announced Sep 8, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
41 pages, 1 figure, comments are welcome!

Related papers

Random unitaries in extremely low depth

Thomas Schuster, Jonas Haferkamp, Hsin-Yuan Huang

Random unitaries are central to quantum technologies and the study of complex quantum many-body physics. However, existing protocols for generating random unitaries require long evolution times and deep circuits. In this work, we prove that local quantum circuits can form random unitaries in extremely low depth on any geometry. These shallow circuits have low complexity and create only short-range correlations, yet are indistinguishable from random unitaries with exponential complexity. This finding contrasts sharply with classical systems, in which a long evolution time is required to appear random. Our results have widespread applications across quantum science, from device benchmarking to quantum advantages. Moreover, they reveal that fundamental physical properties-including evolution time, causal structure, and phases of matter-are provably hard to learn.

arXiv:2407.07754•Science•Jul 3, 2025•71 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

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

Arts & crafts: Strong random unitaries and geometric locality

Marten Folkertsma, Lorenzo Grevink, Jonas Helsen +1 more

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.

quant-pharXiv:2605.03023•May 6, 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

Shallow Quantum Circuit for Generating Extremely Low-Entangled Approximate State Designs

Wonjun Lee, Minki Hhan, Gil Young Cho +1 more

Random quantum states have various applications in quantum information science. We discover a new ensemble of quantum states that serve as an ε-approximate state t-design while possessing extremely low entanglement, magic, and coherence. These resources can reach their theoretical lower bounds, Ω(log(t/ε)), which are also proven in this Letter. This implies that, for fixed t and ε, entanglement, magic, and coherence do not scale with the system size, i.e., O(1) with respect to the total number of qubits n. Moreover, we explicitly construct an ancilla-free shallow quantum circuit for generating such states by transforming k-qubit approximate state designs into n-qubit ones without increasing the support size. The depth of such a quantum circuit, O(t[logt]^{3}log n log[1/ε]), is the most efficient among existing algorithms without ancilla qubits. A class of quantum circuits proposed in our Letter offers reduced cost for classical simulation of random quantum states, leading to potential applications in quantum information processing. As a concrete example, we propose classical shadow tomography using an estimator with superpositions between only two states, from which almost all quantum states can be efficiently certified by requiring only O(1) measurements and classical postprocessing time.

arXiv:2507.17871•Physical Review Letters•Mar 24, 2026•1 citation
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.
Random unitaries are central to quantum technologies and the study of complex quantum many-body physics. However, existing protocols for generating random unitaries require long evolution times and deep circuits. In this work, we prove that local quantum circuits can form random unitaries in extremely low depth on any geometry. These shallow circuits have low complexity and create only short-range correlations, yet are indistinguishable from random unitaries with exponential complexity. This finding contrasts sharply with classical systems, in which a long evolution time is required to appear random. Our results have widespread applications across quantum science, from device benchmarking to quantum advantages. Moreover, they reveal that fundamental physical properties-including evolution time, causal structure, and phases of matter-are provably hard to learn.
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.
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.
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.
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.
Random quantum states have various applications in quantum information science. We discover a new ensemble of quantum states that serve as an ε-approximate state t-design while possessing extremely low entanglement, magic, and coherence. These resources can reach their theoretical lower bounds, Ω(log(t/ε)), which are also proven in this Letter. This implies that, for fixed t and ε, entanglement, magic, and coherence do not scale with the system size, i.e., O(1) with respect to the total number of qubits n. Moreover, we explicitly construct an ancilla-free shallow quantum circuit for generating such states by transforming k-qubit approximate state designs into n-qubit ones without increasing the support size. The depth of such a quantum circuit, O(t[logt]^{3}log n log[1/ε]), is the most efficient among existing algorithms without ancilla qubits. A class of quantum circuits proposed in our Letter offers reduced cost for classical simulation of random quantum states, leading to potential applications in quantum information processing. As a concrete example, we propose classical shadow tomography using an estimator with superpositions between only two states, from which almost all quantum states can be efficiently certified by requiring only O(1) measurements and classical postprocessing time.