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

Efficient approximate unitary t-designs from partially invertible universal sets and their application to quantum speedup

Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, Damian Markham

Published May 4, 2019• 17 citations
arXivHTMLPDF

Abstract

At its core a $t$-design is a method for sampling from a set of unitaries in a way which mimics sampling randomly from the Haar measure on the unitary group, with applications across quantum information processing and physics. We construct new families of quantum circuits on $n$-qubits giving rise to $\varepsilon$-approximate unitary $t$-designs efficiently in $O(n^3t^{12})$ depth. These quantum circuits are based on a relaxation of technical requirements in previous constructions. In particular, the construction of circuits which give efficient approximate $t$-designs by Brandao, Harrow, and Horodecki (F.G.S.L Brandao, A.W Harrow, and M. Horodecki, Commun. Math. Phys. (2016).) required choosing gates from ensembles which contained inverses for all elements, and that the entries of the unitaries are algebraic. We reduce these requirements, to sets that contain elements without inverses in the set, and non-algebraic entries, which we dub partially invertible universal sets. We then adapt this circuit construction to the framework of measurement based quantum computation(MBQC) and give new explicit examples of $n$-qubit graph states with fixed assignments of measurements (graph gadgets) giving rise to unitary $t$-designs based on partially invertible universal sets, in a natural way. We further show that these graph gadgets demonstrate a quantum speedup, up to standard complexity theoretic conjectures. We provide numerical and analytical evidence that almost any assignment of fixed measurement angles on an $n$-qubit cluster state give efficient $t$-designs and demonstrate a quantum speedup.

DOI
10.48550/arxiv.1905.01504

Related papers

On Unitary t-Designs from Relaxed Seeds

Rawad Mezher, Joe Ghalbouni, Joseph Dgheim +1 more

The capacity to randomly pick a unitary across the whole unitary group is a powerful tool across physics and quantum information. A unitary t-design is designed to tackle this challenge in an efficient way, yet constructions to date rely on heavy constraints. In particular, they are composed of ensembles of unitaries which, for technical reasons, must contain inverses and whose entries are algebraic. In this work, we reduce the requirements for generating an ε -approximate unitary t-design. To do so, we first construct a specific n-qubit random quantum circuit composed of a sequence of randomly chosen 2-qubit gates, chosen from a set of unitaries which is approximately universal on U ( 4 ) , yet need not contain unitaries and their inverses nor are in general composed of unitaries whose entries are algebraic; dubbed r e l a x e d seed. We then show that this relaxed seed, when used as a basis for our construction, gives rise to an ε -approximate unitary t-design efficiently, where the depth of our random circuit scales as p o l y ( n , t , l o g ( 1 / ε ) ) , thereby overcoming the two requirements which limited previous constructions. We suspect the result found here is not optimal and can be improved; particularly because the number of gates in the relaxed seeds introduced here grows with n and t. We conjecture that constant sized seeds such as those which are usually present in the literature are sufficient.

arXiv:1911.03704•Entropy•Jan 12, 2020•5 citations

Epsilon-Nets, Unitary Designs, and Random Quantum Circuits

Michał Oszmaniec, Adam Sawicki, Michał Horodecki

Epsilon-nets and approximate unitary$t$-designs are natural notions that capture properties of unitary operations relevant for numerous applications in quantum information and quantum computing. In this work we study quantitative connections between these two notions. Specifically, we prove that, for$d$dimensional Hilbert space, unitaries constituting$\delta $-approximate$t$-expanders form$\epsilon $-nets for$t\simeq \frac {d^{5/2}}{ \epsilon }$and$\delta \simeq \left ({\frac { \epsilon ^{3/2}}{d}}\right)^{d^{2}}$. We also show that for arbitrary$t$,$\epsilon $-nets can be used to construct$\delta $-approximate unitary$t$-designs for$\delta \simeq \epsilon t$, where the notion of approximation is based on the diamond norm. Finally, we prove that the degree of an exact unitary$t$design necessary to obtain an$\epsilon $-net must grow at least as fast as$\frac {1}{ \epsilon }$(for fixed dimension) and not slower than$d^{2}$(for fixed$\epsilon $). This shows near optimality of our result connecting$t$-designs and$\epsilon $-nets. We apply our findings in the context of quantum computing. First, we show that that approximate t-designs can be generated by shallow random circuits formed from a set of universal two-qudit gates in the parallel and sequential local architectures considered in (Brandão et al., 2016). Importantly, our gate sets need not to be symmetric (i.e., contains gates together with their inverses) or consist of gates with algebraic entries. Second, we consider compilation of quantum gates and prove a non-constructive Solovay-Kitaev theorem for general universal gate sets. Our main technical contribution is a new construction of efficient polynomial approximations to the Dirac delta in the space of quantum channels, which can be of independent interest.

arXiv:2007.10885•IEEE Transactions on Information Theory•Nov 13, 2021•41 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•5 citations

Random quantum circuits are approximate unitary t -designs in depth O(nt5+o(1))

Jonas Haferkamp

The applications of random quantum circuits range from quantum computing and quantum many-body systems to the physics of black holes. Many of these applications are related to the generation of quantum pseudorandomness: Random quantum circuits are known to approximate unitary t -designs. Unitary t -designs are probability distributions that mimic Haar randomness up to t th moments. In a seminal paper, Brandão, Harrow and Horodecki prove that random quantum circuits on qubits in a brickwork architecture of depth O(nt10.5) are approximate unitary t -designs. In this work, we revisit this argument, which lower bounds the spectral gap of moment operators for local random quantum circuits by Ω(n−1t−9.5) . We improve this lower bound to Ω(n−1t−4−o(1)) , where the o(1) term goes to 0 as t→∞ . A direct consequence of this scaling is that random quantum circuits generate approximate unitary t -designs in depth O(nt5+o(1)) . Our techniques involve Gao's quantum union bound and the unreasonable effectiveness of the Clifford group. As an auxiliary result, we prove fast convergence to the Haar measure for random Clifford unitaries interleaved with Haar random single qubit unitaries.

arXiv:2203.16571•Quantum•Sep 8, 2022•117 citations

Exact and approximate unitary 2-designs and their application to fidelity estimation

Christoph Dankert, Richard Cleve, Joseph Emerson +1 more

We develop the concept of a unitary $t$-design as a means of expressing operationally useful subsets of the stochastic properties of the uniform (Haar) measure on the unitary group $U({2}^{n})$ on $n$ qubits. In particular, sets of unitaries forming 2-designs have wide applicability to quantum information protocols. We devise an $O(n)$-size in-place circuit construction for an approximate unitary 2-design. We then show that this can be used to construct an efficient protocol for experimentally characterizing the fidelity of a quantum process on $n$ qubits with quantum circuits of size $O(n)$ without requiring any ancilla qubits, thereby improving upon previous approaches.

arXiv:quant-ph/0606161•Physical Review A•Jul 6, 2009•787 citations

Derandomizing Quantum Circuits with Measurement-Based Unitary Designs

Peter S. Turner, Damian Markham

Entangled multipartite states are resources for universal quantum computation, but they can also give rise to ensembles of unitary transformations, a topic usually studied in the context of random quantum circuits. Using several graph state techniques, we show that these resources can "derandomize" circuit results by sampling the same kinds of ensembles quantum mechanically, analogously to a quantum random number generator. Furthermore, we find simple examples that give rise to new ensembles whose statistical moments exactly match those of the uniformly random distribution over all unitaries up to order t, while foregoing adaptive feedforward entirely. Such ensembles-known as t designs-often cannot be distinguished from the "truly" random ensemble, and so they find use in many applications that require this implied notion of pseudorandomness.

arXiv:1511.00714•Physical Review Letters•May 19, 2016•18 citations
At its core a ttt-design is a method for sampling from a set of unitaries in a way which mimics sampling randomly from the Haar measure on the unitary group, with applications across quantum information processing and physics. We construct new families of quantum circuits on nnn-qubits giving rise to ε\varepsilonε-approximate unitary ttt-designs efficiently in O(n3t12)O(n^3t^{12})O(n3t12) depth. These quantum circuits are based on a relaxation of technical requirements in previous constructions. In particular, the construction of circuits which give efficient approximate ttt-designs by Brandao, Harrow, and Horodecki (F.G.S.L Brandao, A.W Harrow, and M. Horodecki, Commun. Math. Phys. (2016).) required choosing gates from ensembles which contained inverses for all elements, and that the entries of the unitaries are algebraic. We reduce these requirements, to sets that contain elements without inverses in the set, and non-algebraic entries, which we dub partially invertible universal sets. We then adapt this circuit construction to the framework of measurement based quantum computation(MBQC) and give new explicit examples of nnn-qubit graph states with fixed assignments of measurements (graph gadgets) giving rise to unitary ttt-designs based on partially invertible universal sets, in a natural way. We further show that these graph gadgets demonstrate a quantum speedup, up to standard complexity theoretic conjectures. We provide numerical and analytical evidence that almost any assignment of fixed measurement angles on an nnn-qubit cluster state give efficient ttt-designs and demonstrate a quantum speedup.
The capacity to randomly pick a unitary across the whole unitary group is a powerful tool across physics and quantum information. A unitary t-design is designed to tackle this challenge in an efficient way, yet constructions to date rely on heavy constraints. In particular, they are composed of ensembles of unitaries which, for technical reasons, must contain inverses and whose entries are algebraic. In this work, we reduce the requirements for generating an ε -approximate unitary t-design. To do so, we first construct a specific n-qubit random quantum circuit composed of a sequence of randomly chosen 2-qubit gates, chosen from a set of unitaries which is approximately universal on U ( 4 ) , yet need not contain unitaries and their inverses nor are in general composed of unitaries whose entries are algebraic; dubbed r e l a x e d seed. We then show that this relaxed seed, when used as a basis for our construction, gives rise to an ε -approximate unitary t-design efficiently, where the depth of our random circuit scales as p o l y ( n , t , l o g ( 1 / ε ) ) , thereby overcoming the two requirements which limited previous constructions. We suspect the result found here is not optimal and can be improved; particularly because the number of gates in the relaxed seeds introduced here grows with n and t. We conjecture that constant sized seeds such as those which are usually present in the literature are sufficient.
Epsilon-nets and approximate unitaryttt-designs are natural notions that capture properties of unitary operations relevant for numerous applications in quantum information and quantum computing. In this work we study quantitative connections between these two notions. Specifically, we prove that, forddddimensional Hilbert space, unitaries constituting$\delta −approximate-approximate−approximatet−expandersform-expanders form−expandersform\epsilon −netsfor-nets for−netsfort\simeq \frac {d^{5/2}}{ \epsilon }andandand\delta \simeq \left ({\frac { \epsilon ^{3/2}}{d}}\right)^{d^{2}}.Wealsoshowthatforarbitrary. We also show that for arbitrary.Wealsoshowthatforarbitraryt,,,\epsilon −netscanbeusedtoconstruct-nets can be used to construct−netscanbeusedtoconstruct\delta −approximateunitary-approximate unitary−approximateunitaryt−designsfor-designs for−designsfor\delta \simeq \epsilon t,wherethenotionofapproximationisbasedonthediamondnorm.Finally,weprovethatthedegreeofanexactunitary, where the notion of approximation is based on the diamond norm. Finally, we prove that the degree of an exact unitary,wherethenotionofapproximationisbasedonthediamondnorm.Finally,weprovethatthedegreeofanexactunitarytdesignnecessarytoobtainandesign necessary to obtain andesignnecessarytoobtainan\epsilon −netmustgrowatleastasfastas-net must grow at least as fast as−netmustgrowatleastasfastas\frac {1}{ \epsilon }(forfixeddimension)andnotslowerthan(for fixed dimension) and not slower than(forfixeddimension)andnotslowerthand^{2}(forfixed(for fixed(forfixed\epsilon ).Thisshowsnearoptimalityofourresultconnecting). This shows near optimality of our result connecting).Thisshowsnearoptimalityofourresultconnectingt−designsand-designs and−designsand\epsilon $-nets. We apply our findings in the context of quantum computing. First, we show that that approximate t-designs can be generated by shallow random circuits formed from a set of universal two-qudit gates in the parallel and sequential local architectures considered in (Brandão et al., 2016). Importantly, our gate sets need not to be symmetric (i.e., contains gates together with their inverses) or consist of gates with algebraic entries. Second, we consider compilation of quantum gates and prove a non-constructive Solovay-Kitaev theorem for general universal gate sets. Our main technical contribution is a new construction of efficient polynomial approximations to the Dirac delta in the space of quantum channels, which can be of independent interest.
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.
The applications of random quantum circuits range from quantum computing and quantum many-body systems to the physics of black holes. Many of these applications are related to the generation of quantum pseudorandomness: Random quantum circuits are known to approximate unitary t -designs. Unitary t -designs are probability distributions that mimic Haar randomness up to t th moments. In a seminal paper, Brandão, Harrow and Horodecki prove that random quantum circuits on qubits in a brickwork architecture of depth O(nt10.5) are approximate unitary t -designs. In this work, we revisit this argument, which lower bounds the spectral gap of moment operators for local random quantum circuits by Ω(n−1t−9.5) . We improve this lower bound to Ω(n−1t−4−o(1)) , where the o(1) term goes to 0 as t→∞ . A direct consequence of this scaling is that random quantum circuits generate approximate unitary t -designs in depth O(nt5+o(1)) . Our techniques involve Gao's quantum union bound and the unreasonable effectiveness of the Clifford group. As an auxiliary result, we prove fast convergence to the Haar measure for random Clifford unitaries interleaved with Haar random single qubit unitaries.
We develop the concept of a unitary ttt-design as a means of expressing operationally useful subsets of the stochastic properties of the uniform (Haar) measure on the unitary group U(2n)U({2}^{n})U(2n) on nnn qubits. In particular, sets of unitaries forming 2-designs have wide applicability to quantum information protocols. We devise an O(n)O(n)O(n)-size in-place circuit construction for an approximate unitary 2-design. We then show that this can be used to construct an efficient protocol for experimentally characterizing the fidelity of a quantum process on nnn qubits with quantum circuits of size O(n)O(n)O(n) without requiring any ancilla qubits, thereby improving upon previous approaches.
Entangled multipartite states are resources for universal quantum computation, but they can also give rise to ensembles of unitary transformations, a topic usually studied in the context of random quantum circuits. Using several graph state techniques, we show that these resources can "derandomize" circuit results by sampling the same kinds of ensembles quantum mechanically, analogously to a quantum random number generator. Furthermore, we find simple examples that give rise to new ensembles whose statistical moments exactly match those of the uniformly random distribution over all unitaries up to order t, while foregoing adaptive feedforward entirely. Such ensembles-known as t designs-often cannot be distinguished from the "truly" random ensemble, and so they find use in many applications that require this implied notion of pseudorandomness.