PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient approximate unitary designs from random Pauli rotations

Jeongwan Haah, Yunchao Liu, Xinyu Tan

arXiv:2402.05239v1quant-phcs.CC

TL;DR

Because prior local random-circuit constructions had steep dependence on t, this paper studies walks built from random Pauli rotations. Products of these rotations converge to approximate unitary t-designs as the number of steps grows.

  • Problem

    Existing approximate unitary t-design constructions using local random circuits had steep dependence on t.

    Source: §1 · p. 1

  • Method

    The paper analyzes random walks whose steps are random Pauli rotations, using Lie-algebra representations and quadratic bounds on kernel projectors.

    Source: §1 · p. 1, §1.3 · p. 3

  • Results

    Products of independent random Pauli rotations converge to a unitary t-design as the number of steps increases.

    Source: §1 · p. 1

  • Takeaways & Limitations

    The approach also yields results for special orthogonal groups through parallel arguments.

    Source: §1 · p. 1, §6 · p. 16

    Whether poly(n)-size SU(2^n) distributions can achieve a spectral gap at least 1/poly(n) independent of t remains an open question.

    Source: §1.2 · p. 3

Abstract

from arXiv · show

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 \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\}^{\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 \theta P /2}$. Our simple proof uses quadratic Casimir operators of Lie algebras.

1 Introduction

The paper studies random walks formed from random Pauli rotations, whose products converge to approximate unitary t-designs. It places this construction against prior spectral-gap bounds and outlines extensions and a Lie-algebra-based proof strategy.

1 Introduction

  • Products of random Pauli rotations converge to approximate unitary t-designs, with t-dependence matching the symmetric group's best-known Ω(t^-1) spectral gap.An approximate unitary t-design behaves like the Haar ensemble up to t-th moments.Source: §1 · p. 1, §1.1 · p. 2

1.1 Previous spectral gap bounds

  • Earlier local brickwall designs had steep t-dependence, and the best previously reported unitary spectral-gap bound was Ω(t^-4-o(1)).The cited brickwall construction uses local gates in a one-dimensional lattice, unlike this paper's ensemble, which has no geometric locality.Source: §1.1 · p. 2

1.2 Implications

  • The result implies robust circuit-complexity lower bounds for products of k ≪ 2^n random rotations; a t-independent inverse-polynomial spectral gap remains an open question.The rotations can be implemented with O(kn) gates.Source: §1.2 · pp. 2–3
  • Sampling can be reduced to O(nt + log 1/ε) random bits, with explicit constants rather than reliance on the implicit spectral gap of [BG12].The seed-length reduction uses a pseudorandom sampling technique [OSP23].Source: §1.2 · p. 3
  • The approach also gives special-orthogonal-group results and quantum state-design bounds better than direct application of the unitary design.The orthogonal analysis uses parallel arguments.Source: §1 · p. 1, §1.2 · p. 3

1.3 Overview of the argument

  • Averaging over the angle turns each represented Pauli generator into a kernel projector, whose average is bounded using quadratic sums of represented operators.The sum of squares is a scalar multiple of the identity in each irrep, and the scalar is bounded in terms of t and N.Source: §1.3 · pp. 3–4

2 Lie algebras and probability distributions

The section recasts probability distributions on SU(N) through their induced distributions on the Lie algebra and on representations. Haar averaging is an orthogonal projection onto the trivial subrepresentation, providing a reference point for analyzing these distributions.

2 Lie algebras and probability distributions

  • The tensor representation’s induced Lie algebra representation lets the analysis study distributions on su(N) through represented operators.The paper moves between distributions on the Lie algebra, group, and representation spaces using the representation map and its induced Lie algebra map.Source: §2 · pp. 4–5
  • The notation su(N) refers to its complexification in representation contexts, but to Hermitian-operator distributions when describing probability distributions.The paper separately notes that it does not discuss infinite-dimensional representations.Source: §2 · pp. 4, 6
  • In the tensor representation, every eigenvalue of τ*(P/2) is an integer in [−t, t], and every integer in that range occurs.The proof uses simultaneous diagonalization of the summands in the induced representation.Source: §2 · p. 5
  • Haar averaging in a finite-dimensional unitary representation is the orthogonal projector onto its trivial subrepresentation.For the tensor representation U ↦ (U ⊗ Ū)^⊗t, the Haar average projects onto that representation’s trivial subspace.Source: §2 · p. 6

3 Random Pauli rotations

This section defines random Pauli rotations and relates their moment operators to kernel projectors in irreducible subrepresentations. It also describes how to implement the rotations with shallow circuits.

3 Random Pauli rotations

  • A random Pauli rotation is uniform over angles θ ∈ (−π, π) for a chosen nonidentity Pauli P, with mixtures allowing a distribution over P.The section focuses on the uniform distribution over P_n while also allowing general distributions over that set.Source: §3 · pp. 6–7
  • Averaging a rotation over θ projects onto the kernel of the represented P/2 operator, since its eigenvalues are integers.The resulting moment operator on a subrepresentation is expressed using K(H), the orthogonal projector onto ker H.Source: §3 · p. 7
  • For any Pauli string P, the rotation can be implemented with O(n) one-qubit and CNOT gates in depth O(log n).The construction conjugates the Pauli string to a single-qubit X rotation using one-qubit gates and at most 2n−2 CNOT and SWAP gates; parallel gate layers are illustrated in Figure 1.Source: §3 · pp. 7–8, Figure 1 · p. 8

4 The special case of su(2)

The special-case analysis evaluates kernel projectors for su(2) irreducible representations and uses them to bound the averaged projector sum. The largest stated norm occurs in the five-dimensional irrep.

4 The special case of su(2)

  • For the tensor representation at order t, the irreps that appear are odd-dimensional and have dimension 2ℓ+1 with ℓ≤t.The representation is a 2t-fold tensor product of the defining su(2) representation.Source: §4 · p. 9
  • Each of K(Jx), K(Jy), and K(Jz) has rank one in every nontrivial odd-dimensional su(2) irrep.The represented Jz operator has eigenvalues ℓ, ℓ−1, …, −ℓ, each with multiplicity one.Source: §4 · p. 9
  • The overlap parameter f is 0 for odd ℓ, −1/2 for ℓ=2, and 3/8 for ℓ=4.The analysis reduces the cases to these values using the stated decreasing function of even integer ℓ.Source: §4 · p. 11
  • The sum K(Jx)+K(Jy)+K(Jz) has norm at most 7/4, attained when ℓ=4.Its norm is max(1−f, 1+2f), and the maximum occurs at f=3/8 for ℓ=4.Source: §4 · p. 11

5 A spectral gap bound by quadratic Casimir invariants

The section bounds the spectral gap through quadratic Casimir estimates on represented Pauli operators, using su(2) subalgebras to obtain lower bounds. It also gives a tighter estimate in the small-t regime and derives a circuit-length condition for diamond-distance accuracy.

5 A spectral gap bound by quadratic Casimir invariants

  • The random Pauli-rotation design has a spectral-gap lower bound of Ω(1/t).The proof uses ℓ≤t for the norm of a represented Pauli operator.Source: §5 · pp. 11, 12, 15
  • The sum of squares of represented Pauli operators is scalar on each irrep, allowing a quadratic Casimir bound to control the kernel projectors.The proof relates the represented-operator sum to the irrep’s Casimir scalar.Source: §5 · p. 12
  • Anticommuting Pauli operators form su(2) triples, whose representation-theoretic lower bound contributes to the spectral-gap estimate.The proof identifies such triples and applies an su(2) bound to vectors at the greatest eigenvalue.Source: §5 · pp. 12–13
  • For t≤N/2, Lemma 5.4 gives roughly a factor-of-two improvement over Lemma 5.3 when t≪N.At t=N/2, the two lemmas give the same bound.Source: §5 · pp. 14–15
  • A discrete set of angles preserves the kernel-projector averaging used in the proof for the integer eigenvalues arising in the t-moment representation.For general finite-dimensional SU(N) representations, the eigenvalues may instead be half-integers; averaging over a wider angle interval eliminates representations with zero kernel.Source: §5 · p. 15
  • k≥(4 log 2)nt^2+4t log(1/ε) iterations suffice for the stated diamond-distance bound of ε.The proof first bounds the 2→2 norm of the channel difference and then converts it to diamond norm.Source: §5 · p. 15

6 Orthogonal designs

The paper adapts its approach to special orthogonal groups in two constructions: one using skew-symmetric Pauli operators and another using an elementary skew-symmetric matrix basis. The second construction applies for general N and supports efficient generation of approximately Haar-random orthogonal matrices.

6.1 Skew-symmetric Pauli operators

  • The construction uses Pauli operators with an odd number of σy factors, whose real span after multiplication by i is so(2^n).The passage identifies this set as a basis-sized linearly independent family of skew-symmetric real matrices.Source: §6.1 · p. 16

6.2 Skew-symmetric elementary matrix basis

  • The paper gives another orthogonal design without requiring N to be a power of 2; Theorem 6.2 covers integers N ≥ 3 and t ≥ 1 and states E ∈ EN: ρ*(E)^2 ⪰ 1(ℓ^2 + (N − 2)ℓ).Source: §6.2 · pp. 17–18
  • Exponentiating an elementary basis matrix gives a 2×2 rotation block plus identity, so multiplying a dense N×N matrix by it takes O(N) arithmetic operations.The paper notes this can be preferable to generating Gaussian entries and applying Gram–Schmidt for some applications.Source: §6.2 · p. 18

A Discrete angles

The proof’s angle average can use a finite grid when the represented Hermitian operator has integer eigenvalues bounded by t. The resulting average still isolates the kernel projector, leaving the rest of the proof unchanged.

A Discrete angles

  • For integer eigenvalues in [−t,t], averaging over Θt={mπ/t : m∈Z∩[−t,t−1]} gives the kernel projector.The finite grid has 2t angle choices.Source: A Discrete angles · pp. 18–19
  • The discrete-angle identity applies to any Hermitian H with integer eigenvalues in [−t,t].The preceding averaging argument uses a continuous interval for the same projector operation.Source: A Discrete angles · p. 18
  • The remainder of the proof is exactly the same as for Theorem 1.1.Source: A Discrete angles · p. 19

B State designs

The appendix treats state designs as approximations to the SU(N)-invariant distribution on pure states, measured by t-th-moment trace distance. It gives a Schatten 1-norm bound and contrasts one asymptotic term with the corresponding unitary-design bound.

B State designs

  • The state-design target is the SU(N)-invariant measure on pure states, with approximation quality measured by t-th-moment trace distance.The text identifies pure states with normalized vectors modulo global phase, or equivalently rank-1 projectors.Source: B State designs · p. 19
  • Theorem B.1 gives a Schatten 1-norm bound for any integers t, k, n≥1 and normalized vector |α⟩∈C^N.Source: B State designs · p. 19
  • For large N, the last term in the stated bound is approximately (2N)^−1, contrasting with a term of approximately N^−2.The comparison is stated for the last terms of the respective bounds.Source: B State designs · p. 19
Loading 2402.05239v1…