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

Exact spectral gaps for random Pauli rotations

Ziyuan Dong, Xiang Fan

quant-phmath.PRSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
v1 · Sep 30, 2026v2 · Oct 4, 2026
arXivHTMLPDF

Abstract

We resolve the spectral-gap problem posed by Baer and Haah for random Pauli rotations. In this walk, a nonidentity $n$-qubit Pauli operator $P$ and an angle $θ$ modulo $2π$ are chosen independently and uniformly, and the step is $e^{\mathrm{i}θP}$. Writing $d=2^n$, we prove that the gap on $\mathsf{SU}(d)$ is $(d-8)/(8(d-1))$ for $n\ge4$. This disproves their conjectured formula on the full special unitary group. We also prove that the conjectured value, $d(d-3)/(8(d^2-1))$, is exactly the gap on $\mathsf{PU}(d)$ for $n\ge3$. The special-unitary gap is attained by an explicit vector in $\bigwedge^8\mathbb C^d$, constructed from affine three-dimensional subspaces of $\mathbb F_2^n$. Its nontrivial central action explains why balanced tensor representations do not detect this smaller gap. On the projective group, the gap is attained in $U\mapsto U^{\otimes4}\otimes\bar U^{\otimes4}$. The matching lower bounds hold uniformly over all finite-dimensional unitary representations. They combine the spectrum of the graph of anticommuting Pauli operators, a minimum-weight bound for binary polynomials, and a local inequality on a single-qubit Clifford-fixed subspace. The proof is analytic and requires no computational verification.

DOI
10.5281/zenodo.23099545
Comments
12 pages

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.

quant-pharXiv:2607.20919•Jul 24, 2026•0 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 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.

Annual Symposium on Foundations of Computer Science•Oct 27, 2024•14 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.

arXiv:2402.05239•Feb 7, 2024•1 citation

Exact Clifford Optimality for Two-Sided Locally Randomized Classical Shadows

Xiaotian Nie, Tao Zhang, Yadong Wu +1 more

Entangling measurements can reduce the cost of learning many-body correlations. We consider classical shadows in which a fixed unitary on a $k$-qubit region is sandwiched between two layers of random single-qubit Clifford gates, and ask which middle unitary best estimates Pauli strings with full support on the region. Combining symplectic support counting with a constraint from operator-size parity, we prove that within this architecture the minimum squared shadow norm over all Clifford middle unitaries is $C_k^{\rm opt}=4\cdot 9^k/(3\cdot 5^k+3^k-6)$ for odd $k$ and $C_k^{\rm opt}=4\cdot 9^k/(3\cdot 5^k-3^k+2)$ for even $k$. A dual-axis rotation circuit $U_*$ attains this minimum for every $k$. Asymptotically $C_k^{\rm opt}\simeq(4/3)\cdot(9/5)^k$: the exponential base of Wu et al.'s contractive unitary is optimal, and the prefactor improves from $2$ to $4/3$. For $1\leq k\leq7$, exact certificates show that $U_*$ is optimal over the entire unitary group $\mathrm U(2^k)$, and we conjecture that this holds for every $k$.

quant-pharXiv:2610.04621•Oct 6, 2026•0 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•81 citations

Architectures and random properties of symplectic quantum circuits

Diego García-Martín, Paolo Braccia, Marco Cerezo

Abstract Parametrized and random unitary (or orthogonal) n -qubit circuits play a central role in quantum information. As such, one could naturally assume that circuits implementing symplectic transformations would attract similar attention. However, this is not the case, as S P ( d / 2 ) —the group of d × d unitary symplectic matrices—has thus far been overlooked. In this work, we aim at starting to fill this gap. We begin by presenting a universal set of generators G for the symplectic algebra sp ( d / 2 ) , consisting of one- and two-qubit Pauli operators acting on neighboring sites in a one-dimensional lattice. Here, we uncover two critical differences between such set, and equivalent ones for unitary and orthogonal circuits. Namely, we find that the operators in G cannot generate arbitrary local symplectic unitaries and that they are not translationally invariant. We then review the Schur–Weyl duality between the symplectic group and the Brauer algebra, and use tools from Weingarten calculus to prove that Pauli measurements at the output of Haar random symplectic circuits can converge to Gaussian processes. As a by-product, such analysis provides us with concentration bounds for Pauli measurements in circuits that form t -designs over S P ( d / 2 ) . To finish, we present tensor-network tools to analyze shallow random symplectic circuits, and we use these to numerically show that computational-basis measurements anti-concentrate at logarithmic depth.

arXiv:2405.10264•Quantum Science and Technology•Nov 18, 2025•4 citations
We resolve the spectral-gap problem posed by Baer and Haah for random Pauli rotations. In this walk, a nonidentity nnn-qubit Pauli operator PPP and an angle θθθ modulo 2π2π2π are chosen independently and uniformly, and the step is eiθPe^{\mathrm{i}θP}eiθP. Writing d=2nd=2^nd=2n, we prove that the gap on SU(d)\mathsf{SU}(d)SU(d) is (d−8)/(8(d−1))(d-8)/(8(d-1))(d−8)/(8(d−1)) for n≥4n\ge4n≥4. This disproves their conjectured formula on the full special unitary group. We also prove that the conjectured value, d(d−3)/(8(d2−1))d(d-3)/(8(d^2-1))d(d−3)/(8(d2−1)), is exactly the gap on PU(d)\mathsf{PU}(d)PU(d) for n≥3n\ge3n≥3. The special-unitary gap is attained by an explicit vector in ⋀8Cd\bigwedge^8\mathbb C^d⋀8Cd, constructed from affine three-dimensional subspaces of F2n\mathbb F_2^nF2n​. Its nontrivial central action explains why balanced tensor representations do not detect this smaller gap. On the projective group, the gap is attained in U↦U⊗4⊗Uˉ⊗4U\mapsto U^{\otimes4}\otimes\bar U^{\otimes4}U↦U⊗4⊗Uˉ⊗4. The matching lower bounds hold uniformly over all finite-dimensional unitary representations. They combine the spectrum of the graph of anticommuting Pauli operators, a minimum-weight bound for binary polynomials, and a local inequality on a single-qubit Clifford-fixed subspace. The proof is analytic and requires no computational verification.
We prove constant lower bounds for the spectral gap of the following random walks on unitary groups SU(2n)\mathsf{SU}(2^n)SU(2n) on nnn qubits. (i) Random Pauli Rotation: choose an nnn-qubit Pauli operator PPP and an angle θ∈[0,2π)θ\in [0,2π)θ∈[0,2π), both uniformly at random, and apply eiθPe^{\mathrm i θP}eiθP. (ii) Brickwork Random Unitary Circuit: choose n−1n-1n−1 unitaries UiU_{i}Ui​ uniformly at random from SU(4)\mathsf{SU}(4)SU(4) independently, and apply U2j−1U_{2j-1}U2j−1​ on two qubits 2j−1,2j2j-1, 2j2j−1,2j and then U2jU_{2j}U2j​ on two qubits 2j,2j+12j, 2j+12j,2j+1. Importantly, the spectral gap lower bounds are independent of nnn and apply for all finite dimensional unitary representations of SU(2n)\mathsf{SU}(2^n)SU(2n) uniformly, including those that appear in unitary ttt-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 orderttt. Specifically, a step of the walk on the unitary or orthogonal group of dimension2n2^{\mathrm{n}}2nis a random Pauli rotationeiθP/2e^{\mathrm{i}\theta P/2}eiθP/2. The spectral gap of this random walk is shown to beΩ(1/t)\Omega(1/t)Ω(1/t), which coincides with the best previously known bound for a random walk on the permutation group on{0,1}n\{0,1\}^{\mathrm{n}}{0,1}n. This implies that the walk gives anε\varepsilonε-approximate unitary t-design in depthO(nt2+tlog⁡1ε)d\mathcal{O}(\mathrm{n}t^{2}+t\log\frac{1}{\varepsilon})dO(nt2+tlogε1​)dwhered=O(log⁡n)d=\mathrm{O}(\log \mathrm{n})d=O(logn)is the circuit depth to implementeiθP/2e^{\mathrm{i}\theta P/2}eiθ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 ttt. Specifically, a step of the walk on the unitary or orthognoal group of dimension 2n2^{\mathsf n}2n is a random Pauli rotation eiθP/2e^{\mathrm i θP /2}eiθP/2. The spectral gap of this random walk is shown to be Ω(1/t)Ω(1/t)Ω(1/t), which coincides with the best previously known bound for a random walk on the permutation group on {0,1}n\{0,1\}^{\mathsf n}{0,1}n. This implies that the walk gives an ε\varepsilonε-approximate unitary ttt-design in depth O(nt2+tlog⁡1/ε)dO(\mathsf n t^2 + t \log 1/\varepsilon)dO(nt2+tlog1/ε)d where d=O(log⁡n)d=O(\log \mathsf n)d=O(logn) is the circuit depth to implement eiθP/2e^{\mathrm i θP /2}eiθP/2. Our simple proof uses quadratic Casimir operators of Lie algebras.
Entangling measurements can reduce the cost of learning many-body correlations. We consider classical shadows in which a fixed unitary on a kkk-qubit region is sandwiched between two layers of random single-qubit Clifford gates, and ask which middle unitary best estimates Pauli strings with full support on the region. Combining symplectic support counting with a constraint from operator-size parity, we prove that within this architecture the minimum squared shadow norm over all Clifford middle unitaries is Ckopt=4⋅9k/(3⋅5k+3k−6)C_k^{\rm opt}=4\cdot 9^k/(3\cdot 5^k+3^k-6)Ckopt​=4⋅9k/(3⋅5k+3k−6) for odd kkk and Ckopt=4⋅9k/(3⋅5k−3k+2)C_k^{\rm opt}=4\cdot 9^k/(3\cdot 5^k-3^k+2)Ckopt​=4⋅9k/(3⋅5k−3k+2) for even kkk. A dual-axis rotation circuit U∗U_*U∗​ attains this minimum for every kkk. Asymptotically Ckopt≃(4/3)⋅(9/5)kC_k^{\rm opt}\simeq(4/3)\cdot(9/5)^kCkopt​≃(4/3)⋅(9/5)k: the exponential base of Wu et al.'s contractive unitary is optimal, and the prefactor improves from 222 to 4/34/34/3. For 1≤k≤71\leq k\leq71≤k≤7, exact certificates show that U∗U_*U∗​ is optimal over the entire unitary group U(2k)\mathrm U(2^k)U(2k), and we conjecture that this holds for every kkk.
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.
Abstract Parametrized and random unitary (or orthogonal) n -qubit circuits play a central role in quantum information. As such, one could naturally assume that circuits implementing symplectic transformations would attract similar attention. However, this is not the case, as S P ( d / 2 ) —the group of d × d unitary symplectic matrices—has thus far been overlooked. In this work, we aim at starting to fill this gap. We begin by presenting a universal set of generators G for the symplectic algebra sp ( d / 2 ) , consisting of one- and two-qubit Pauli operators acting on neighboring sites in a one-dimensional lattice. Here, we uncover two critical differences between such set, and equivalent ones for unitary and orthogonal circuits. Namely, we find that the operators in G cannot generate arbitrary local symplectic unitaries and that they are not translationally invariant. We then review the Schur–Weyl duality between the symplectic group and the Brauer algebra, and use tools from Weingarten calculus to prove that Pauli measurements at the output of Haar random symplectic circuits can converge to Gaussian processes. As a by-product, such analysis provides us with concentration bounds for Pauli measurements in circuits that form t -designs over S P ( d / 2 ) . To finish, we present tensor-network tools to analyze shallow random symplectic circuits, and we use these to numerically show that computational-basis measurements anti-concentrate at logarithmic depth.