Random unitaries are useful in quantum information and related fields, but hard to generate with limited resources. An approximate unitary k-design is an ensemble of unitaries with an underlying measure over which the average is close to a Haar random ensemble up to the first k moments. A particularly strong notion of approximation bounds the distance from Haar randomness in relative error. Such relative-error approximate designs are secure against queries by an adaptive adversary trying to distinguish it from a Haar ensemble. We construct relative-error approximate unitary k-design ensembles for which communication between subsystems is O(1) in the system size. These constructions use the alternating projection method to analyze overlapping Haar averages, giving a bound on the convergence speed to the full averaging with respect to the 2-norm. Using von Neumann subalgebra indices to replace system dimension, the 2-norm distance converts to relative error without introducing any additional dimension dependence. We use these constructions as the building blocks of a two-step protocol that achieves a relative-error design in <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$O \big ( (\log m + \log (1/\epsilon ) + k \log k ) k\, \text {polylog}(k) \big )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mrow> <mo maxsize="1.2em" minsize="1.2em" stretchy="true">(</mo> </mrow> <mo stretchy="false">(</mo> <mo>log</mo> <mi>m</mi> <mo>+</mo> <mo>log</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mi>ϵ</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mi>k</mi> <mo>log</mo> <mi>k</mi> <mo stretchy="false">)</mo> <mi>k</mi> <mspace width="0.166667em" /> <mtext>polylog</mtext> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> <mrow> <mo maxsize="1.2em" minsize="1.2em" stretchy="true">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> depth, where m is the number of qudits in the complete system and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\epsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation> the approximation error. This sublinear depth construction answers a variant of [<CitationRef CitationID="CR21">21</CitationRef>, Harrow and Mehraban 2023, Section 1.5, Open Question 1] and [<CitationRef CitationID="CR21">21</CitationRef>, Harrow and Mehraban 2023, Section 1.5, Open Question 7]. Moreover, entanglement generated by the sublinear depth scheme follows area laws on spatial lattices up to corrections logarithmic in the full system size.

Approximate Unitary k-Designs from Shallow, Low-Communication Circuits

期刊论文
出版模式：

开放获取
发表日期：

2026年2月5日

查看全文

Nicholas LaRacuente,
Felix Leditzky

摘要

Random unitaries are useful in quantum information and related fields, but hard to generate with limited resources. An approximate unitary k-design is an ensemble of unitaries with an underlying measure over which the average is close to a Haar random ensemble up to the first k moments. A particularly strong notion of approximation bounds the distance from Haar randomness in relative error. Such relative-error approximate designs are secure against queries by an adaptive adversary trying to distinguish it from a Haar ensemble. We construct relative-error approximate unitary k-design ensembles for which communication between subsystems is O(1) in the system size. These constructions use the alternating projection method to analyze overlapping Haar averages, giving a bound on the convergence speed to the full averaging with respect to the 2-norm. Using von Neumann subalgebra indices to replace system dimension, the 2-norm distance converts to relative error without introducing any additional dimension dependence. We use these constructions as the building blocks of a two-step protocol that achieves a relative-error design in $O \big ( (\log m + \log (1/\epsilon ) + k \log k ) k\, \text {polylog}(k) \big )$ $O ((log m + log (1 / ϵ) + k log k) k polylog (k))$ depth, where m is the number of qudits in the complete system and $\epsilon $ $ϵ$ the approximation error. This sublinear depth construction answers a variant of [21, Harrow and Mehraban 2023, Section 1.5, Open Question 1] and [21, Harrow and Mehraban 2023, Section 1.5, Open Question 7]. Moreover, entanglement generated by the sublinear depth scheme follows area laws on spatial lattices up to corrections logarithmic in the full system size.