Breaking the cubic barrier in the Solovay-Kitaev algorithm
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915537121968128 |
|---|---|
| author | Kuperberg, Greg |
| author_facet | Kuperberg, Greg |
| contents | We improve the Solovay--Kitaev theorem and algorithm for a general finite, inverse-closed generating set acting on a qudit. Prior versions of the algorithm efficiently find a word of length $O(n^{3+δ})$ to approximate an arbitrary target gate to $n$ bits of precision. Using two new ideas, each of which reduces the exponent separately, our new bound on the word length is $O(n^{1.44042\ldots+δ})$. Our result holds more generally for any finite set that densely generates any connected, semisimple real Lie group, with an extra length term in the noncompact case to reach group elements far away from the identity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_13158 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Breaking the cubic barrier in the Solovay-Kitaev algorithm Kuperberg, Greg Quantum Physics Data Structures and Algorithms Group Theory Representation Theory We improve the Solovay--Kitaev theorem and algorithm for a general finite, inverse-closed generating set acting on a qudit. Prior versions of the algorithm efficiently find a word of length $O(n^{3+δ})$ to approximate an arbitrary target gate to $n$ bits of precision. Using two new ideas, each of which reduces the exponent separately, our new bound on the word length is $O(n^{1.44042\ldots+δ})$. Our result holds more generally for any finite set that densely generates any connected, semisimple real Lie group, with an extra length term in the noncompact case to reach group elements far away from the identity. |
| title | Breaking the cubic barrier in the Solovay-Kitaev algorithm |
| topic | Quantum Physics Data Structures and Algorithms Group Theory Representation Theory |
| url | https://arxiv.org/abs/2306.13158 |