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:quant-ph/0606161 · Physical Review A

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

Christoph Dankert, Richard Cleve, Joseph Emerson, Etera R. Livine

Published Jul 6, 2009• 787 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.80.012304

Related papers

Exact and Approximate Unitary 2-Designs: Constructions and Applications

Dankert, Christoph, Cleve, Richard, Joseph Emerson +1 more

We consider an extension of the concept of spherical t-designs to the unitary group in order to develop a unified framework for analyzing the resource requirements of randomized quantum algorithms. We show that certain protocols based on twirling require a unitary 2-design. We describe an efficient construction for an exact unitary 2-design based on the Clifford group, and then develop a method for generating an epsilon-approximate unitary 2-design that requires only O(n log(1/epsilon)) gates, where n is the number of qubits and epsilon is an appropriate measure of precision. These results lead to a protocol with exponential resource savings over existing experimental methods for estimating the characteristic fidelities of physical quantum processes.

•Jun 20, 2006•10 citations

Random Quantum Circuits Beyond Moment Matching

Shih-Han Hung

Random quantum circuits aim to efficiently reproduce the statistical properties of ideal random quantum evolution. One approach is to construct approximate unitary designs, which match the moments of Haar-random unitaries up to a prescribed order with controlled error. We establish quantitative guarantees for how accurately these designs reproduce the distribution of each output probability. We show that, for every strong $\varepsilon$-approximate unitary $k$-design on $n$ qubits, the distribution of each output probability is within $O(k^{-1/2}(1+k/2^n)^{-1/2}+\varepsilon)$ in Kolmogorov distance of the Porter-Thomas distribution, a beta distribution with parameters $1$ and $2^n-1$. This bound is optimal up to constant factors, implying that a substantially better uniform bound requires additional structure. We then show that a mild form of local invariance suffices. We prove that any such design that is invariant under unitary translations acting on a single qubit approximates Porter-Thomas to total variation distance $O(k^{-1/2}+\varepsilon)$. Every strong $\varepsilon$-approximate unitary $k$-design invariant on $\log k+O(1)$ qubits achieves error $2^{-Ω(k)}+O(\varepsilon)$ in Kolmogorov distance and $2^{-Ω(k)}+O(\varepsilon\log(2/\varepsilon))$ in total variation distance. These results identify the distributional accuracy guaranteed by moment matching and the structure that improves it. As an application, we show that the Shannon entropy of the output distribution of a strong $\varepsilon$-approximate $k$-design is concentrated around its Haar value $n-Θ(1)$: its mean differs from the Haar mean by $O(k^{-1/4}+\varepsilon^{1/2})$ and its standard deviation is $O(2^{-n/2}+k^{-1/8}+\varepsilon^{1/4})$. Consequently, a trusted device sampling such circuits generates $n-O(1)$ bits of entropy per sample, which makes them useful for random number generation.

quant-pharXiv:2610.02135•Oct 2, 2026•0 citations

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

Rawad Mezher, Joe Ghalbouni, Joseph Dgheim +1 more

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.

arXiv:1905.01504•May 4, 2019•17 citations

Randomized Benchmarking Using Unitary t-Design for Average Fidelity Estimation of Practical Quantum Circuit

Zhang Linxi, Chuanghua Zhu, Changxing Pei

Randomized benchmarking is a useful scheme for evaluation the average fidelity of a noisy quantum circuit. However, it is insensitive to the unitary error. Here, we propose a method of randomized benchmarking in which a unitary t-design is applied and by which the unitary error estimation can be converted to analysis of pseudo-randomness on a set of unitary operators. We give a bound on the number of randomized benchmarking sequences, when performing a unitary t-design on n-qubit d-dimensional system. By applying local random unitary operators, a decomposition of a unitary t-design, the bound is more practical than the previous bound for multi-qubit circuit. We also give a rigorous bound of a diamond norm between arbitrary and uniform distributions of a set of unitary operators to form an ε-approximate unitary t-design. It can be used to quantitatively analyze the corresponding average fidelity and errors in a large-scale quantum circuit.

arXiv:1711.08098•Nov 22, 2017•5 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

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
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.
We consider an extension of the concept of spherical t-designs to the unitary group in order to develop a unified framework for analyzing the resource requirements of randomized quantum algorithms. We show that certain protocols based on twirling require a unitary 2-design. We describe an efficient construction for an exact unitary 2-design based on the Clifford group, and then develop a method for generating an epsilon-approximate unitary 2-design that requires only O(n log(1/epsilon)) gates, where n is the number of qubits and epsilon is an appropriate measure of precision. These results lead to a protocol with exponential resource savings over existing experimental methods for estimating the characteristic fidelities of physical quantum processes.
Random quantum circuits aim to efficiently reproduce the statistical properties of ideal random quantum evolution. One approach is to construct approximate unitary designs, which match the moments of Haar-random unitaries up to a prescribed order with controlled error. We establish quantitative guarantees for how accurately these designs reproduce the distribution of each output probability. We show that, for every strong ε\varepsilonε-approximate unitary kkk-design on nnn qubits, the distribution of each output probability is within O(k−1/2(1+k/2n)−1/2+ε)O(k^{-1/2}(1+k/2^n)^{-1/2}+\varepsilon)O(k−1/2(1+k/2n)−1/2+ε) in Kolmogorov distance of the Porter-Thomas distribution, a beta distribution with parameters 111 and 2n−12^n-12n−1. This bound is optimal up to constant factors, implying that a substantially better uniform bound requires additional structure. We then show that a mild form of local invariance suffices. We prove that any such design that is invariant under unitary translations acting on a single qubit approximates Porter-Thomas to total variation distance O(k−1/2+ε)O(k^{-1/2}+\varepsilon)O(k−1/2+ε). Every strong ε\varepsilonε-approximate unitary kkk-design invariant on log⁡k+O(1)\log k+O(1)logk+O(1) qubits achieves error 2−Ω(k)+O(ε)2^{-Ω(k)}+O(\varepsilon)2−Ω(k)+O(ε) in Kolmogorov distance and 2−Ω(k)+O(εlog⁡(2/ε))2^{-Ω(k)}+O(\varepsilon\log(2/\varepsilon))2−Ω(k)+O(εlog(2/ε)) in total variation distance. These results identify the distributional accuracy guaranteed by moment matching and the structure that improves it. As an application, we show that the Shannon entropy of the output distribution of a strong ε\varepsilonε-approximate kkk-design is concentrated around its Haar value n−Θ(1)n-Θ(1)n−Θ(1): its mean differs from the Haar mean by O(k−1/4+ε1/2)O(k^{-1/4}+\varepsilon^{1/2})O(k−1/4+ε1/2) and its standard deviation is O(2−n/2+k−1/8+ε1/4)O(2^{-n/2}+k^{-1/8}+\varepsilon^{1/4})O(2−n/2+k−1/8+ε1/4). Consequently, a trusted device sampling such circuits generates n−O(1)n-O(1)n−O(1) bits of entropy per sample, which makes them useful for random number generation.
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.
Randomized benchmarking is a useful scheme for evaluation the average fidelity of a noisy quantum circuit. However, it is insensitive to the unitary error. Here, we propose a method of randomized benchmarking in which a unitary t-design is applied and by which the unitary error estimation can be converted to analysis of pseudo-randomness on a set of unitary operators. We give a bound on the number of randomized benchmarking sequences, when performing a unitary t-design on n-qubit d-dimensional system. By applying local random unitary operators, a decomposition of a unitary t-design, the bound is more practical than the previous bound for multi-qubit circuit. We also give a rigorous bound of a diamond norm between arbitrary and uniform distributions of a set of unitary operators to form an ε-approximate unitary t-design. It can be used to quantitatively analyze the corresponding average fidelity and errors in a large-scale quantum circuit.
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.
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.