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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$2^{{\textsf{n}}}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mi mathvariant="sans-serif">n</mi> </msup> </math></EquationSource> </InlineEquation> is a random Pauli rotation <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$e^{\mathrm i \theta P /2}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>e</mi> <mrow> <mi mathvariant="normal">i</mi> <mi>θ</mi> <mi>P</mi> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> </math></EquationSource> </InlineEquation>. The spectral gap of this random walk is shown to be <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\Omega (1/t)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, which coincides with the best previously known bound for a random walk on the permutation group on <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\{0,1\}^{{\textsf{n}}}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mo stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">}</mo> </mrow> <mi mathvariant="sans-serif">n</mi> </msup> </math></EquationSource> </InlineEquation>. This implies that the walk gives an <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\varepsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ε</mi> </math></EquationSource> </InlineEquation>-approximate unitary t-design in depth <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\mathcal O({\textsf{n}} t^2 + t \log \frac{1}{\varepsilon })d$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mi mathvariant="sans-serif">n</mi> <msup> <mi>t</mi> <mn>2</mn> </msup> <mo>+</mo> <mi>t</mi> <mo>log</mo> <mfrac> <mn>1</mn> <mi>ε</mi> </mfrac> <mo stretchy="false">)</mo> <mi>d</mi> </mrow> </math></EquationSource> </InlineEquation> where <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$d=\mathcal {O}(\log {\textsf{n}})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>=</mo> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi mathvariant="sans-serif">n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is the circuit depth to implement <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$e^{\mathrm i \theta P /2}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>e</mi> <mrow> <mi mathvariant="normal">i</mi> <mi>θ</mi> <mi>P</mi> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> </math></EquationSource> </InlineEquation>. Our simple proof uses quadratic Casimir operators of Lie algebras.

Efficient Approximate Unitary Designs from Random Pauli Rotations

期刊论文
发表日期：

2025年10月30日

查看全文

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^{{\textsf{n}}}$ $2^{n}$ is a random Pauli rotation $e^{\mathrm i \theta P /2}$ $e^{i θ P / 2}$ . The spectral gap of this random walk is shown to be $\Omega (1/t)$ $Ω (1 / t)$ , which coincides with the best previously known bound for a random walk on the permutation group on $\{0,1\}^{{\textsf{n}}}$ ${0, 1}^{n}$ . This implies that the walk gives an $\varepsilon $ $ε$ -approximate unitary t-design in depth $\mathcal O({\textsf{n}} t^2 + t \log \frac{1}{\varepsilon })d$ $O (n t^{2} + t log \frac{1}{ε}) d$ where $d=\mathcal {O}(\log {\textsf{n}})$ $d = O (log n)$ is the circuit depth to implement $e^{\mathrm i \theta P /2}$ $e^{i θ P / 2}$ . Our simple proof uses quadratic Casimir operators of Lie algebras.