Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.04921 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912631624826880 |
|---|---|
| author | Cleve, Richard Ding, Zhiqian Schaeffer, Luke |
| author_facet | Cleve, Richard Ding, Zhiqian Schaeffer, Luke |
| contents | The commutative depth model allows gates that commute with each other to be performed in parallel. We show how to compute Clifford operations in constant commutative depth more efficiently than was previously known. Bravyi, Maslov, and Nam [Phys. Rev. Lett. 129:230501, 2022] showed that every element of the Clifford group (on $n$ qubits) can be computed in commutative depth 23 and size $O(n^2)$. We show that the Prefix Sum problem can be computed in commutative depth 16 and size $O(n \log n)$, improving on the previous depth 18 and size $O(n^2)$ bounds. We also show that, for arbitrary Cliffords, the commutative depth bound can be reduced to 16. Finally, we show some lower bounds: that there exist Cliffords whose commutative depth is at least 4; and that there exist Cliffords for which any constant commutative depth circuit has size $Ω(n^2)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_04921 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Clifford operations in constant commutative depth Cleve, Richard Ding, Zhiqian Schaeffer, Luke Quantum Physics The commutative depth model allows gates that commute with each other to be performed in parallel. We show how to compute Clifford operations in constant commutative depth more efficiently than was previously known. Bravyi, Maslov, and Nam [Phys. Rev. Lett. 129:230501, 2022] showed that every element of the Clifford group (on $n$ qubits) can be computed in commutative depth 23 and size $O(n^2)$. We show that the Prefix Sum problem can be computed in commutative depth 16 and size $O(n \log n)$, improving on the previous depth 18 and size $O(n^2)$ bounds. We also show that, for arbitrary Cliffords, the commutative depth bound can be reduced to 16. Finally, we show some lower bounds: that there exist Cliffords whose commutative depth is at least 4; and that there exist Cliffords for which any constant commutative depth circuit has size $Ω(n^2)$. |
| title | Improved Clifford operations in constant commutative depth |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2510.04921 |