Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908816491151360 |
|---|---|
| author | LaRacuente, Nicholas Leditzky, Felix |
| author_facet | LaRacuente, Nicholas Leditzky, Felix |
| contents | 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/ε) + k \log k ) k\, \text{polylog}(k) \big )$ depth, where $m$ is the number of qudits in the complete system and $ε$ the approximation error. This sublinear depth construction answers a variant of [Harrow and Mehraban 2023, Section 1.5, Open Questions 1 and 7]. Moreover, entanglement generated by the sublinear depth scheme follows area laws on spatial lattices up to corrections logarithmic in the full system size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_07876 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits LaRacuente, Nicholas Leditzky, Felix Quantum Physics Mathematical Physics 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/ε) + k \log k ) k\, \text{polylog}(k) \big )$ depth, where $m$ is the number of qudits in the complete system and $ε$ the approximation error. This sublinear depth construction answers a variant of [Harrow and Mehraban 2023, Section 1.5, Open Questions 1 and 7]. Moreover, entanglement generated by the sublinear depth scheme follows area laws on spatial lattices up to corrections logarithmic in the full system size. |
| title | Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits |
| topic | Quantum Physics Mathematical Physics |
| url | https://arxiv.org/abs/2407.07876 |