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

Approximate 3-designs and partial decomposition of the Clifford group representation using transvections

Tanmay Singal, Min-Hsiu Hsieh

Published Nov 26, 2021• 2 citations
arXivHTMLPDF

Abstract

We study a scheme to implement an asymptotic unitary 3-design. The scheme implements a random Pauli once followed by the implementation of a random transvection Clifford by using state twirling. Thus the scheme is implemented in the form of a quantum channel. We show that when this scheme is implemented $k$ times, then, in the $k \rightarrow \infty$ limit, the overall scheme implements a unitary $3$-design. This is proved by studying the eigendecomposition of the scheme: the $+1$ eigenspace of the scheme coincides with that of an exact unitary $3$-design, and the remaining eigenvalues are bounded by a constant. Using this we prove that the scheme has to be implemented approximately $\mathcal{O}(m + \log 1/ε)$ times to obtain an $ε$-approximate unitary $3$-design, where $m$ is the number of qubits, and $ε$ is the diamond-norm distance of the exact unitary $3$-design. Also, the scheme implements an asymptotic unitary $2$-design with the following convergence rate: it has to be sampled $\mathcal{O}(\log 1/ε)$ times to be an $ε$-approximate unitary $2$-design. Since transvection Cliffords are a conjugacy class of the Clifford group, the eigenspaces of the scheme's quantum channel coincide with the irreducible invariant subspaces of the adjoint representation of the Clifford group. Some of the subrepresentations we obtain are the same as were obtained in J. Math. Phys. 59, 072201 (2018), whereas the remaining are new invariant subspaces. Thus we obtain a partial decomposition of the adjoint representation for $3$ copies for the Clifford group. Thus, aside from providing a scheme for the implementation of unitary $3$-design, this work is of interest for studying representation theory of the Clifford group, and the potential applications of this topic. The paper ends with open questions regarding the scheme and representation theory of the Clifford group.

DOI
10.48550/arxiv.2111.13678

Related papers

Clifford Approximation of Unitary Matrices

Kalle Volanto, Mahdi Bayanifar, Olav Tirkkonen

Approximating a given unitary operator into a discrete set of gates is of great importance in quantum computation. This problem can be seen as a source quantization problem where the unitary operator is considered as the source. Elements of the Clifford hierarchy can be implemented fault-tolerantly using quantum gate teleportation. This motivates the development of algorithms that quantize unitary operators into Clifford hierarchy elements. In this paper, we present a fast algorithm for approximating arbitrary n-qubit unitaries with Clifford matrices. The algorithm relies on the Clifford transvection decomposition of the Clifford group. The algorithm greedily applies Clifford transvections taking the input unitary closer to the identity matrix. To make the algorithm fast, we take advantage of the Pauli basis representation for unitary matrices to parallelize matrix distance computations. The complexity of the proposed algorithm is O(n 4n). Based on simulation results, the proposed algorithm outperforms the state of the art method.

Globecom•Dec 8, 2025•0 citations

Efficient Unitary Designs with a System-Size Independent Number of Non-Clifford Gates

Jonas Haferkamp, Felipe Montealegre‐Mora, Markus Heinrich +3 more

Abstract Many quantum information protocols require the implementation of random unitaries. Because it takes exponential resources to produce Haar-random unitaries drawn from the full n -qubit group, one often resorts to t -designs. Unitary t -designs mimic the Haar-measure up to t -th moments. It is known that Clifford operations can implement at most 3-designs. In this work, we quantify the non-Clifford resources required to break this barrier. We find that it suffices to inject $$O(t^{4}\log ^{2}(t)\log (1/\varepsilon ))$$ O ( t 4 log 2 ( t ) log ( 1 / ε ) ) many non-Clifford gates into a polynomial-depth random Clifford circuit to obtain an $$\varepsilon $$ ε -approximate t -design. Strikingly, the number of non-Clifford gates required is independent of the system size – asymptotically, the density of non-Clifford gates is allowed to tend to zero. We also derive novel bounds on the convergence time of random Clifford circuits to the t -th moment of the uniform distribution on the Clifford group. Our proofs exploit a recently developed variant of Schur-Weyl duality for the Clifford group, as well as bounds on restricted spectral gaps of averaging operators.

arXiv:2002.09524•Communications in Mathematical Physics•Nov 12, 2022•114 citations

Clifford Group and Unitary Designs under Symmetry

Yosuke Mitsuhashi, Nobuyuki Yoshioka

We have generalized the well-known statement that the Clifford group is a unitary 3-design into symmetric cases by extending the notion of unitary design.Concretely, we have proven that a symmetric Clifford group is a symmetric unitary 3-design if and only if the symmetry constraint is described by some Pauli subgroup.We have also found a complete and unique construction method of symmetric Clifford groups with simple quantum gates for Pauli symmetries.For the overall understanding, we have also considered physically relevant U(1) and SU(2) symmetry constraints, which cannot be described by a Pauli subgroup, and have proven that the symmetric Clifford group is a symmetric unitary 1-design but not a 2-design under those symmetries.Our findings are numerically verified by computing the frame potentials, which measure the difference in randomness between the uniform ensemble on the symmetric group of interest and the symmetric unitary group.This work will open a new perspective into quantum information processing, such as randomized benchmarking, and give a deep understanding to many-body systems, such as monitored random circuits.

arXiv:2306.17559•PRX Quantum•Nov 27, 2023•14 citations

Qudit Designs and Where to Find Them

Namit Anand, Jeffrey Marshall, Jason Saied +2 more

Unitary t-designs are some of the most versatile tools in quantum information theory. Their applications range from randomized benchmarking and shadow tomography, to more fundamental ones such as emulating quantum chaos and establishing exponential separations between classical and quantum query complexity. While unitary designs originating from a group structure, such as the Clifford group, have proven to be incredibly useful for qubit systems, unfortunately, this is no longer true for qudits. In fact, the classification of finite-group representations rules out the existence of unitary 2-designs for arbitrary qudit dimensions. This severely limits the applicability of standard quantum information primitives when it comes to qudit systems. We overcome these limitations with a three-fold contribution. First, we introduce a general technique to construct families of weighted state t-designs in arbitrary qudit dimensions. These weighted state-designs generalize classical shadow tomography protocol from qubits to qudits. Second, we introduce a Clifford character RB that allows us to benchmark the qudit Clifford group in any dimension, including non-prime-power dimensions. And third, we establish bounds on the quantum circuit complexity of generating approximate unitary-designs from native gates in existing quantum hardware such as high-spin and cavity-QED qudits. Our work further highlights the analogy between spin and optical coherent states by proving that spin-GKP codewords form a state 2-design while spin coherent states do not; in direct analogy with the optical case. This work is structured as a pedagogical and self-contained introduction to unitary designs and their applications to qudit systems.

quant-pharXiv:2603.02659•Mar 4, 2026•3 citations

The Clifford group forms a unitary 3-design

Zak Webb

Unitary k-designs are finite ensembles of unitary matrices that approximate the Haar distribution over unitary matrices. Several ensembles are known to be 2-designs, including the uniform distribution over the Clifford group, but no family of ensembles was previously known to form a 3-design. We prove that the Clifford group is a 3-design, showing that it is a better approximation to Haar-random unitaries than previously expected. Our proof strategy works for any distribution of unitaries satisfying a property we call Pauli 2-mixing and proceeds without the use of heavy mathematical machinery. We also show that the Clifford group does not form a 4-design, thus characterizing how well random Clifford elements approximate Haar-random unitaries. Additionally, we show that the generalized Clifford group for qudits is not a 3-design unless the dimension of the qudit is a power of 2.

arXiv:1510.02769•Quantum Information and Computation•Nov 1, 2016•253 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•3 citations
We study a scheme to implement an asymptotic unitary 3-design. The scheme implements a random Pauli once followed by the implementation of a random transvection Clifford by using state twirling. Thus the scheme is implemented in the form of a quantum channel. We show that when this scheme is implemented kkk times, then, in the k→∞k \rightarrow \inftyk→∞ limit, the overall scheme implements a unitary 333-design. This is proved by studying the eigendecomposition of the scheme: the +1+1+1 eigenspace of the scheme coincides with that of an exact unitary 333-design, and the remaining eigenvalues are bounded by a constant. Using this we prove that the scheme has to be implemented approximately O(m+log⁡1/ε)\mathcal{O}(m + \log 1/ε)O(m+log1/ε) times to obtain an εεε-approximate unitary 333-design, where mmm is the number of qubits, and εεε is the diamond-norm distance of the exact unitary 333-design. Also, the scheme implements an asymptotic unitary 222-design with the following convergence rate: it has to be sampled O(log⁡1/ε)\mathcal{O}(\log 1/ε)O(log1/ε) times to be an εεε-approximate unitary 222-design. Since transvection Cliffords are a conjugacy class of the Clifford group, the eigenspaces of the scheme's quantum channel coincide with the irreducible invariant subspaces of the adjoint representation of the Clifford group. Some of the subrepresentations we obtain are the same as were obtained in J. Math. Phys. 59, 072201 (2018), whereas the remaining are new invariant subspaces. Thus we obtain a partial decomposition of the adjoint representation for 333 copies for the Clifford group. Thus, aside from providing a scheme for the implementation of unitary 333-design, this work is of interest for studying representation theory of the Clifford group, and the potential applications of this topic. The paper ends with open questions regarding the scheme and representation theory of the Clifford group.
Approximating a given unitary operator into a discrete set of gates is of great importance in quantum computation. This problem can be seen as a source quantization problem where the unitary operator is considered as the source. Elements of the Clifford hierarchy can be implemented fault-tolerantly using quantum gate teleportation. This motivates the development of algorithms that quantize unitary operators into Clifford hierarchy elements. In this paper, we present a fast algorithm for approximating arbitrary n-qubit unitaries with Clifford matrices. The algorithm relies on the Clifford transvection decomposition of the Clifford group. The algorithm greedily applies Clifford transvections taking the input unitary closer to the identity matrix. To make the algorithm fast, we take advantage of the Pauli basis representation for unitary matrices to parallelize matrix distance computations. The complexity of the proposed algorithm is O(n 4n). Based on simulation results, the proposed algorithm outperforms the state of the art method.
Abstract Many quantum information protocols require the implementation of random unitaries. Because it takes exponential resources to produce Haar-random unitaries drawn from the full n -qubit group, one often resorts to t -designs. Unitary t -designs mimic the Haar-measure up to t -th moments. It is known that Clifford operations can implement at most 3-designs. In this work, we quantify the non-Clifford resources required to break this barrier. We find that it suffices to inject O(t4log⁡2(t)log⁡(1/ε))O(t^{4}\log ^{2}(t)\log (1/\varepsilon ))O(t4log2(t)log(1/ε)) O ( t 4 log 2 ( t ) log ( 1 / ε ) ) many non-Clifford gates into a polynomial-depth random Clifford circuit to obtain an ε\varepsilon ε ε -approximate t -design. Strikingly, the number of non-Clifford gates required is independent of the system size – asymptotically, the density of non-Clifford gates is allowed to tend to zero. We also derive novel bounds on the convergence time of random Clifford circuits to the t -th moment of the uniform distribution on the Clifford group. Our proofs exploit a recently developed variant of Schur-Weyl duality for the Clifford group, as well as bounds on restricted spectral gaps of averaging operators.
We have generalized the well-known statement that the Clifford group is a unitary 3-design into symmetric cases by extending the notion of unitary design.Concretely, we have proven that a symmetric Clifford group is a symmetric unitary 3-design if and only if the symmetry constraint is described by some Pauli subgroup.We have also found a complete and unique construction method of symmetric Clifford groups with simple quantum gates for Pauli symmetries.For the overall understanding, we have also considered physically relevant U(1) and SU(2) symmetry constraints, which cannot be described by a Pauli subgroup, and have proven that the symmetric Clifford group is a symmetric unitary 1-design but not a 2-design under those symmetries.Our findings are numerically verified by computing the frame potentials, which measure the difference in randomness between the uniform ensemble on the symmetric group of interest and the symmetric unitary group.This work will open a new perspective into quantum information processing, such as randomized benchmarking, and give a deep understanding to many-body systems, such as monitored random circuits.
Unitary t-designs are some of the most versatile tools in quantum information theory. Their applications range from randomized benchmarking and shadow tomography, to more fundamental ones such as emulating quantum chaos and establishing exponential separations between classical and quantum query complexity. While unitary designs originating from a group structure, such as the Clifford group, have proven to be incredibly useful for qubit systems, unfortunately, this is no longer true for qudits. In fact, the classification of finite-group representations rules out the existence of unitary 2-designs for arbitrary qudit dimensions. This severely limits the applicability of standard quantum information primitives when it comes to qudit systems. We overcome these limitations with a three-fold contribution. First, we introduce a general technique to construct families of weighted state t-designs in arbitrary qudit dimensions. These weighted state-designs generalize classical shadow tomography protocol from qubits to qudits. Second, we introduce a Clifford character RB that allows us to benchmark the qudit Clifford group in any dimension, including non-prime-power dimensions. And third, we establish bounds on the quantum circuit complexity of generating approximate unitary-designs from native gates in existing quantum hardware such as high-spin and cavity-QED qudits. Our work further highlights the analogy between spin and optical coherent states by proving that spin-GKP codewords form a state 2-design while spin coherent states do not; in direct analogy with the optical case. This work is structured as a pedagogical and self-contained introduction to unitary designs and their applications to qudit systems.
Unitary k-designs are finite ensembles of unitary matrices that approximate the Haar distribution over unitary matrices. Several ensembles are known to be 2-designs, including the uniform distribution over the Clifford group, but no family of ensembles was previously known to form a 3-design. We prove that the Clifford group is a 3-design, showing that it is a better approximation to Haar-random unitaries than previously expected. Our proof strategy works for any distribution of unitaries satisfying a property we call Pauli 2-mixing and proceeds without the use of heavy mathematical machinery. We also show that the Clifford group does not form a 4-design, thus characterizing how well random Clifford elements approximate Haar-random unitaries. Additionally, we show that the generalized Clifford group for qudits is not a 3-design unless the dimension of the qudit is a power of 2.
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.