Annual Symposium on Foundations of Computer Science

Efficient Approximate Unitary Designs from Random Pauli Rotations

Jeongwan Haah, Yunchao Liu, Xinyu Tan

Published Oct 27, 2024• 14 citations

Abstract

We construct random walks on simple Lie groups that quickly converge to the Haar measure for all moments up to order$t$. Specifically, a step of the walk on the unitary or orthogonal group of dimension$2^{\mathrm{n}}$is a random Pauli rotation$e^{\mathrm{i}\theta P/2}$. The spectral gap of this random walk is shown to be$\Omega(1/t)$, which coincides with the best previously known bound for a random walk on the permutation group on$\{0,1\}^{\mathrm{n}}$. This implies that the walk gives an$\varepsilon$-approximate unitary t-design in depth$\mathcal{O}(\mathrm{n}t^{2}+t\log\frac{1}{\varepsilon})d$where$d=\mathrm{O}(\log \mathrm{n})$is the circuit depth to implement$e^{\mathrm{i}\theta P/2}$. Our simple proof uses quadratic Casimir operators of Lie algebras.

DOI: 10.1109/focs61266.2024.00036

Related papers

Random unitary circuits with constant spectral gap

Tim Baer, Jeongwan Haah

quant-pharXiv:2607.20919Jul 24, 20260 citations

Efficient approximate unitary designs from random Pauli rotations

Jeongwan Haah, Yunchao Liu, Xinyu Tan

arXiv:2402.05239Feb 7, 20241 citation

Spectral gaps and slow modes of Pauli rotations and random quantum circuits

Ziyuan Dong, Xiang Fan

quant-pharXiv:2609.40164Oct 1, 20260 citations

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

Jonas Haferkamp

arXiv:2203.16571QuantumSep 8, 202281 citations

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

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

arXiv:2002.09524Communications in Mathematical PhysicsNov 12, 202251 citations

Strong unitary designs in optimal depth and space

Teodor Parella-Dilmé, Júlia Barberà-Rodríguez, Salvatore F. E. Oliviero +1 more

quant-pharXiv:2608.13491Aug 14, 20260 citations

Annual Symposium on Foundations of Computer Science

Efficient Approximate Unitary Designs from Random Pauli Rotations

Jeongwan Haah, Yunchao Liu, Xinyu Tan

Published Oct 27, 2024• 14 citations

Publisher

Abstract

We construct random walks on simple Lie groups that quickly converge to the Haar measure for all moments up to order

t

. Specifically, a step of the walk on the unitary or orthogonal group of dimension

2^{\mathrm{n}}

is a random Pauli rotation

e^{\mathrm{i}\theta P/2}

. The spectral gap of this random walk is shown to be

\Omega(1/t)

, which coincides with the best previously known bound for a random walk on the permutation group on

\{0,1\}^{\mathrm{n}}

. This implies that the walk gives an

\varepsilon

-approximate unitary t-design in depth

\mathcal{O}(\mathrm{n}t^{2}+t\log\frac{1}{\varepsilon})d

where

d=\mathrm{O}(\log \mathrm{n})

is the circuit depth to implement

e^{\mathrm{i}\theta P/2}

. Our simple proof uses quadratic Casimir operators of Lie algebras.

DOI: 10.1109/focs61266.2024.00036

Related papers

Random unitary circuits with constant spectral gap

Tim Baer, Jeongwan Haah

We prove constant lower bounds for the spectral gap of the following random walks on unitary groups $\mathsf{SU}(2^n)$ on $n$ qubits. (i) Random Pauli Rotation: choose an $n$ -qubit Pauli operator $P$ and an angle $θ\in [0,2π)$ , both uniformly at random, and apply $e^{\mathrm i θP}$ . (ii) Brickwork Random Unitary Circuit: choose $n-1$ unitaries $U_{i}$ uniformly at random from $\mathsf{SU}(4)$ independently, and apply $U_{2j-1}$ on two qubits $2j-1, 2j$ and then $U_{2j}$ on two qubits $2j, 2j+1$ . Importantly, the spectral gap lower bounds are independent of $n$ and apply for all finite dimensional unitary representations of $\mathsf{SU}(2^n)$ uniformly, including those that appear in unitary $t$ -designs. We also prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit.We prove constant lower bounds for the spectral gap of the following random walks on unitary groups $\mathsf{SU}(2^n)$ on $n$ qubits. (i) Random Pauli Rotation: choose an $n$-qubit Pauli operator $P$ and an angle $θ\in [0,2π)$, both uniformly at random, and apply $e^{\mathrm i θP}$. (ii) Brickwork Random Unitary Circuit: choose $n-1$ unitaries $U_{i}$ uniformly at random from $\mathsf{SU}(4)$ independently, and apply $U_{2j-1}$ on two qubits $2j-1, 2j$ and then $U_{2j}$ on two qubits $2j, 2j+1$. Importantly, the spectral gap lower bounds are independent of $n$ and apply for all finite dimensional unitary representations of $\mathsf{SU}(2^n)$ uniformly, including those that appear in unitary $t$-designs. We also prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit.

quant-pharXiv:2607.20919Jul 24, 20260 citations

Efficient approximate unitary designs from random Pauli rotations

Jeongwan Haah, Yunchao Liu, Xinyu Tan

We construct random walks on simple Lie groups that quickly converge to the Haar measure for all moments up to order $t$ . Specifically, a step of the walk on the unitary or orthognoal group of dimension $2^{\mathsf n}$ is a random Pauli rotation $e^{\mathrm i θP /2}$ . The spectral gap of this random walk is shown to be $Ω(1/t)$ , which coincides with the best previously known bound for a random walk on the permutation group on $\{0,1\}^{\mathsf n}$ . This implies that the walk gives an $\varepsilon$ -approximate unitary $t$ -design in depth $O(\mathsf n t^2 + t \log 1/\varepsilon)d$ where $d=O(\log \mathsf n)$ is the circuit depth to implement $e^{\mathrm i θP /2}$ . Our simple proof uses quadratic Casimir operators of Lie algebras.We construct random walks on simple Lie groups that quickly converge to the Haar measure for all moments up to order $t$. Specifically, a step of the walk on the unitary or orthognoal group of dimension $2^{\mathsf n}$ is a random Pauli rotation $e^{\mathrm i θP /2}$. The spectral gap of this random walk is shown to be $Ω(1/t)$, which coincides with the best previously known bound for a random walk on the permutation group on $\{0,1\}^{\mathsf n}$. This implies that the walk gives an $\varepsilon$-approximate unitary $t$-design in depth $O(\mathsf n t^2 + t \log 1/\varepsilon)d$ where $d=O(\log \mathsf n)$ is the circuit depth to implement $e^{\mathrm i θP /2}$. Our simple proof uses quadratic Casimir operators of Lie algebras.

arXiv:2402.05239Feb 7, 20241 citation

Spectral gaps and slow modes of Pauli rotations and random quantum circuits

Ziyuan Dong, Xiang Fan

We determine which representation sectors control the slowest convergence of random Pauli rotations and several local random quantum circuits. For $d=2^n$ , the continuous Pauli walk has exact all-representation gaps $Δ_{\mathsf{SU}(d)}=\frac{d-8}{8(d-1)}\quad(n\ge4),\qquad Δ_{\mathsf{PU}(d)}=\frac{d(d-3)}{8(d^2-1)}\quad(n\ge3).$ The special-unitary gap is attained in $\bigwedge^8\mathbb{C}^d$ and is invisible to balanced moments, while the projective gap is already attained in a balanced fourth-moment representation. We obtain exact discrete and orthogonal Pauli analogues, exact finite-Clifford chain/path gaps, and dimension-independent all-representation Haar brickwork lower bounds; on three qubits every weighted Haar- $\mathsf{SU}(4)$ edge walk reduces to one universal principal-angle constant. For real complete-graph models, the entire ordinary fourth-tensor gap reduces to a quadratic-size occupation operator, is simple for every $n\ge4$ , and has an expansion beginning $Δ_n^{(4)}=\frac{10}{9n}-\frac{88}{105n^2}+O(n^{-3}),$ with competing branches separated only beyond all algebraic orders. For the two finite real Clifford complete-graph walks, this fourth-tensor mode is the exact all-representation group gap for every $n\ge144$ ; in the same range it simultaneously governs every ordinary even tensor degree $k\ge4$ . Thus different representation scopes can have genuinely different slow modes.We determine which representation sectors control the slowest convergence of random Pauli rotations and several local random quantum circuits. For $d=2^n$, the continuous Pauli walk has exact all-representation gaps $$Δ_{\mathsf{SU}(d)}=\frac{d-8}{8(d-1)}\quad(n\ge4),\qquad Δ_{\mathsf{PU}(d)}=\frac{d(d-3)}{8(d^2-1)}\quad(n\ge3).$$ The special-unitary gap is attained in $\bigwedge^8\mathbb{C}^d$ and is invisible to balanced moments, while the projective gap is already attained in a balanced fourth-moment representation. We obtain exact discrete and orthogonal Pauli analogues, exact finite-Clifford chain/path gaps, and dimension-independent all-representation Haar brickwork lower bounds; on three qubits every weighted Haar-$\mathsf{SU}(4)$ edge walk reduces to one universal principal-angle constant. For real complete-graph models, the entire ordinary fourth-tensor gap reduces to a quadratic-size occupation operator, is simple for every $n\ge4$, and has an expansion beginning $$Δ_n^{(4)}=\frac{10}{9n}-\frac{88}{105n^2}+O(n^{-3}),$$ with competing branches separated only beyond all algebraic orders. For the two finite real Clifford complete-graph walks, this fourth-tensor mode is the exact all-representation group gap for every $n\ge144$; in the same range it simultaneously governs every ordinary even tensor degree $k\ge4$. Thus different representation scopes can have genuinely different slow modes.

quant-pharXiv:2609.40164Oct 1, 20260 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.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.16571QuantumSep 8, 202281 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.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.09524Communications in Mathematical PhysicsNov 12, 202251 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.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.13491Aug 14, 20260 citations

We construct random walks on simple Lie groups that quickly converge to the Haar measure for all moments up to order

t

. Specifically, a step of the walk on the unitary or orthogonal group of dimension

2^{\mathrm{n}}

is a random Pauli rotation

e^{\mathrm{i}\theta P/2}

. The spectral gap of this random walk is shown to be

\Omega(1/t)

, which coincides with the best previously known bound for a random walk on the permutation group on

\{0,1\}^{\mathrm{n}}

. This implies that the walk gives an

\varepsilon

-approximate unitary t-design in depth

\mathcal{O}(\mathrm{n}t^{2}+t\log\frac{1}{\varepsilon})d

where

d=\mathrm{O}(\log \mathrm{n})

is the circuit depth to implement

e^{\mathrm{i}\theta P/2}

. Our simple proof uses quadratic Casimir operators of Lie algebras.

We prove constant lower bounds for the spectral gap of the following random walks on unitary groups

\mathsf{SU}(2^n)

n

qubits. (i) Random Pauli Rotation: choose an

n

-qubit Pauli operator

P

and an angle

θ\in [0,2π)

, both uniformly at random, and apply

e^{\mathrm i θP}

. (ii) Brickwork Random Unitary Circuit: choose

n-1

unitaries

U_{i}

uniformly at random from

\mathsf{SU}(4)

independently, and apply

U_{2j-1}

on two qubits

2j-1, 2j

and then

U_{2j}

on two qubits

2j, 2j+1

. Importantly, the spectral gap lower bounds are independent of

n

and apply for all finite dimensional unitary representations of

\mathsf{SU}(2^n)

uniformly, including those that appear in unitary

t

-designs. We also prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit.

We construct random walks on simple Lie groups that quickly converge to the Haar measure for all moments up to order

t

. Specifically, a step of the walk on the unitary or orthognoal group of dimension

2^{\mathsf n}

is a random Pauli rotation

e^{\mathrm i θP /2}

. The spectral gap of this random walk is shown to be

Ω(1/t)

, which coincides with the best previously known bound for a random walk on the permutation group on

\{0,1\}^{\mathsf n}

. This implies that the walk gives an

\varepsilon

-approximate unitary

t

-design in depth

O(\mathsf n t^2 + t \log 1/\varepsilon)d

where

d=O(\log \mathsf n)

is the circuit depth to implement

e^{\mathrm i θP /2}

. Our simple proof uses quadratic Casimir operators of Lie algebras.

We determine which representation sectors control the slowest convergence of random Pauli rotations and several local random quantum circuits. For

d=2^n

, the continuous Pauli walk has exact all-representation gaps

Δ_{\mathsf{SU}(d)}=\frac{d-8}{8(d-1)}\quad(n\ge4),\qquad Δ_{\mathsf{PU}(d)}=\frac{d(d-3)}{8(d^2-1)}\quad(n\ge3).

The special-unitary gap is attained in

\bigwedge^8\mathbb{C}^d

and is invisible to balanced moments, while the projective gap is already attained in a balanced fourth-moment representation. We obtain exact discrete and orthogonal Pauli analogues, exact finite-Clifford chain/path gaps, and dimension-independent all-representation Haar brickwork lower bounds; on three qubits every weighted Haar-

\mathsf{SU}(4)

edge walk reduces to one universal principal-angle constant. For real complete-graph models, the entire ordinary fourth-tensor gap reduces to a quadratic-size occupation operator, is simple for every

n\ge4

, and has an expansion beginning

Δ_n^{(4)}=\frac{10}{9n}-\frac{88}{105n^2}+O(n^{-3}),

with competing branches separated only beyond all algebraic orders. For the two finite real Clifford complete-graph walks, this fourth-tensor mode is the exact all-representation group gap for every

n\ge144

; in the same range it simultaneously governs every ordinary even tensor degree

k\ge4

. Thus different representation scopes can have genuinely different slow modes.

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.

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.