arXiv:2310.13597

Explicit orthogonal and unitary designs

Ryan O’Donnell, Rocco A. Servedio, Pedro Paredes

Published Oct 20, 2023• 0 citations

Abstract

We give a strongly explicit construction of $\varepsilon$-approximate $k$-designs for the orthogonal group $\mathrm{O}(N)$ and the unitary group $\mathrm{U}(N)$, for $N=2^n$. Our designs are of cardinality $\mathrm{poly}(N^k/\varepsilon)$ (equivalently, they have seed length $O(nk + \log(1/\varepsilon)))$; up to the polynomial, this matches the number of design elements used by the construction consisting of completely random matrices.

DOI: 10.48550/arxiv.2310.13597

Related papers

Explicit orthogonal and unitary designs

Ryan O’Donnell, Rocco A. Servedio, Pedro Paredes

Annual Symposium on Foundations of Computer ScienceNov 6, 20238 citations

Efficient unitary designs and pseudorandom unitaries from permutations

Chi-Fang Chen, Adam Bouland, Fernando G. S. L. Brandão +3 more

arXiv:2404.16751Apr 25, 20244 citations

On Unitary t-Designs from Relaxed Seeds

Rawad Mezher, Joe Ghalbouni, Joseph Dgheim +1 more

arXiv:1911.03704EntropyJan 12, 20206 citations

Arts & crafts: Strong random unitaries and geometric locality

Marten Folkertsma, Lorenzo Grevink, Jonas Helsen +1 more

quant-pharXiv:2605.03023May 6, 20260 citations

On the explicit constructions of certain unitary t -designs

Eiichi Bannai, Mikio Nakahara, Zhao Da +1 more

arXiv:1906.04583Journal of Physics A Mathematical and TheoreticalOct 22, 201912 citations

(Almost) quadruply optimal unitary designs in 1D

Guoding Liu, Jonas Helsen

quant-pharXiv:2608.18650Aug 20, 20260 citations

arXiv:2310.13597

Explicit orthogonal and unitary designs

Ryan O’Donnell, Rocco A. Servedio, Pedro Paredes

Published Oct 20, 2023• 0 citations

arXiv HTML PDF

Abstract

We give a strongly explicit construction of

\varepsilon

-approximate

k

-designs for the orthogonal group

\mathrm{O}(N)

and the unitary group

\mathrm{U}(N)

, for

N=2^n

. Our designs are of cardinality

\mathrm{poly}(N^k/\varepsilon)

(equivalently, they have seed length

O(nk + \log(1/\varepsilon)))

; up to the polynomial, this matches the number of design elements used by the construction consisting of completely random matrices.

DOI: 10.48550/arxiv.2310.13597

Related papers

Explicit orthogonal and unitary designs

Ryan O’Donnell, Rocco A. Servedio, Pedro Paredes

We give a strongly explicit construction of ϵ approximate k-designs for the orthogonal group O(N) and the unitary group U(N), for $N=2^{n}$ . Our designs are of cardinality $\operatorname{poly}(N^{k}/\epsilon)$ (equivalently, they have seed length $O(nk+\log(1/\epsilon)))$ ; up to the polynomial, this matches the number of design elements used by the construction consisting of completely random matrices.We give a strongly explicit construction of ϵ approximate k-designs for the orthogonal group O(N) and the unitary group U(N), for $N=2^{n}$. Our designs are of cardinality $\operatorname{poly}(N^{k}/\epsilon)$ (equivalently, they have seed length $O(nk+\log(1/\epsilon)))$; up to the polynomial, this matches the number of design elements used by the construction consisting of completely random matrices.

Annual Symposium on Foundations of Computer ScienceNov 6, 20238 citations

Efficient unitary designs and pseudorandom unitaries from permutations

Chi-Fang Chen, Adam Bouland, Fernando G. S. L. Brandão +3 more

In this work we give an efficient construction of unitary $k$ -designs using $\tilde{O}(k\cdot poly(n))$ quantum gates, as well as an efficient construction of a parallel-secure pseudorandom unitary (PRU). Both results are obtained by giving an efficient quantum algorithm that lifts random permutations over $S(N)$ to random unitaries over $U(N)$ for $N=2^n$ . In particular, we show that products of exponentiated sums of $S(N)$ permutations with random phases approximately match the first $2^{Ω(n)}$ moments of the Haar measure. By substituting either $\tilde{O}(k)$ -wise independent permutations, or quantum-secure pseudorandom permutations (PRPs) in place of the random permutations, we obtain the above results. The heart of our proof is a conceptual connection between the large dimension (large- $N$ ) expansion in random matrix theory and the polynomial method, which allows us to prove query lower bounds at finite- $N$ by interpolating from the much simpler large- $N$ limit. The key technical step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large- $N$ expansion. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimension $N$ .In this work we give an efficient construction of unitary $k$-designs using $\tilde{O}(k\cdot poly(n))$ quantum gates, as well as an efficient construction of a parallel-secure pseudorandom unitary (PRU). Both results are obtained by giving an efficient quantum algorithm that lifts random permutations over $S(N)$ to random unitaries over $U(N)$ for $N=2^n$. In particular, we show that products of exponentiated sums of $S(N)$ permutations with random phases approximately match the first $2^{Ω(n)}$ moments of the Haar measure. By substituting either $\tilde{O}(k)$-wise independent permutations, or quantum-secure pseudorandom permutations (PRPs) in place of the random permutations, we obtain the above results. The heart of our proof is a conceptual connection between the large dimension (large-$N$) expansion in random matrix theory and the polynomial method, which allows us to prove query lower bounds at finite-$N$ by interpolating from the much simpler large-$N$ limit. The key technical step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large-$N$ expansion. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimension $N$.

arXiv:2404.16751Apr 25, 20244 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.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.03704EntropyJan 12, 20206 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.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.03023May 6, 20260 citations

On the explicit constructions of certain unitary t -designs

Eiichi Bannai, Mikio Nakahara, Zhao Da +1 more

Abstract Unitary t -designs are ‘good’ finite subsets of the unitary group that approximate the whole unitary group well. Unitary t -designs have been applied in randomized benchmarking, tomography, quantum cryptography and many other areas of quantum information science. If a unitary t -design itself is a group then it is called a unitary t -group. Although it is known that unitary t -designs in exist for any t and d , the unitary t -groups do not exist for if , as it is shown by Guralnick–Tiep (Guralnick and Tiep 2005 Represent. Theory 9 138–208) and Bannai–Navarro–Rizo–Tiep (Bannai et al 2018 J. Math. Soc. Japan (accepted) ). Explicit constructions of exact unitary t -designs in are not easy in general. In particular, explicit constructions of unitary 4-designs in have been an open problem in quantum information theory. We prove that some exact unitary -designs in the unitary group are constructed from unitary t -groups in that satisfy certain specific conditions. Based on this result, we specifically construct exact unitary 3-designs in from the unitary 2-group in and also unitary 4-designs in from the unitary 3-group in numerically. We also discuss some related problems and a few applications to physics problems.Abstract Unitary t -designs are ‘good’ finite subsets of the unitary group that approximate the whole unitary group well. Unitary t -designs have been applied in randomized benchmarking, tomography, quantum cryptography and many other areas of quantum information science. If a unitary t -design itself is a group then it is called a unitary t -group. Although it is known that unitary t -designs in exist for any t and d , the unitary t -groups do not exist for if , as it is shown by Guralnick–Tiep (Guralnick and Tiep 2005 Represent. Theory 9 138–208) and Bannai–Navarro–Rizo–Tiep (Bannai et al 2018 J. Math. Soc. Japan (accepted) ). Explicit constructions of exact unitary t -designs in are not easy in general. In particular, explicit constructions of unitary 4-designs in have been an open problem in quantum information theory. We prove that some exact unitary -designs in the unitary group are constructed from unitary t -groups in that satisfy certain specific conditions. Based on this result, we specifically construct exact unitary 3-designs in from the unitary 2-group in and also unitary 4-designs in from the unitary 3-group in numerically. We also discuss some related problems and a few applications to physics problems.

arXiv:1906.04583Journal of Physics A Mathematical and TheoreticalOct 22, 201912 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.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.18650Aug 20, 20260 citations

We give a strongly explicit construction of

\varepsilon

-approximate

k

-designs for the orthogonal group

\mathrm{O}(N)

and the unitary group

\mathrm{U}(N)

, for

N=2^n

. Our designs are of cardinality

\mathrm{poly}(N^k/\varepsilon)

(equivalently, they have seed length

O(nk + \log(1/\varepsilon)))

; up to the polynomial, this matches the number of design elements used by the construction consisting of completely random matrices.

We give a strongly explicit construction of ϵ approximate k-designs for the orthogonal group O(N) and the unitary group U(N), for

N=2^{n}

. Our designs are of cardinality

\operatorname{poly}(N^{k}/\epsilon)

(equivalently, they have seed length

O(nk+\log(1/\epsilon)))

; up to the polynomial, this matches the number of design elements used by the construction consisting of completely random matrices.

In this work we give an efficient construction of unitary

k

-designs using

\tilde{O}(k\cdot poly(n))

quantum gates, as well as an efficient construction of a parallel-secure pseudorandom unitary (PRU). Both results are obtained by giving an efficient quantum algorithm that lifts random permutations over

S(N)

to random unitaries over

U(N)

for

N=2^n

. In particular, we show that products of exponentiated sums of

S(N)

permutations with random phases approximately match the first

2^{Ω(n)}

moments of the Haar measure. By substituting either

\tilde{O}(k)

-wise independent permutations, or quantum-secure pseudorandom permutations (PRPs) in place of the random permutations, we obtain the above results. The heart of our proof is a conceptual connection between the large dimension (large-

N

) expansion in random matrix theory and the polynomial method, which allows us to prove query lower bounds at finite-

N

by interpolating from the much simpler large-

N

limit. The key technical step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large-

N

expansion. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimension

N

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.

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)

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.