Clifford testing: algorithms and lower bounds
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914081675411456 |
|---|---|
| author | Hinsche, Marcel Bao, Zongbo van Dordrecht, Philippe Eisert, Jens Briët, Jop Helsen, Jonas |
| author_facet | Hinsche, Marcel Bao, Zongbo van Dordrecht, Philippe Eisert, Jens Briët, Jop Helsen, Jonas |
| contents | We consider the problem of Clifford testing, which asks whether a black-box $n$-qubit unitary is a Clifford unitary or at least $\varepsilon$-far from every Clifford unitary. We give the first 4-query Clifford tester, which decides this problem with probability $\mathrm{poly}(\varepsilon)$. This contrasts with the minimum of 6 copies required for the closely-related task of stabilizer testing. We show that our tester is tolerant, by adapting techniques from tolerant stabilizer testing to our setting. In doing so, we settle in the positive a conjecture of Bu, Gu and Jaffe, by proving a polynomial inverse theorem for a non-commutative Gowers 3-uniformity norm. We also consider the restricted setting of single-copy access, where we give an $O(n)$-query Clifford tester that requires no auxiliary memory qubits or adaptivity. We complement this with a lower bound, proving that any such, potentially adaptive, single-copy algorithm needs at least $Ω(n^{1/4})$ queries. To obtain our results, we leverage the structure of the commutant of the Clifford group, obtaining several technical statements that may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_07164 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Clifford testing: algorithms and lower bounds Hinsche, Marcel Bao, Zongbo van Dordrecht, Philippe Eisert, Jens Briët, Jop Helsen, Jonas Quantum Physics Computational Complexity Data Structures and Algorithms We consider the problem of Clifford testing, which asks whether a black-box $n$-qubit unitary is a Clifford unitary or at least $\varepsilon$-far from every Clifford unitary. We give the first 4-query Clifford tester, which decides this problem with probability $\mathrm{poly}(\varepsilon)$. This contrasts with the minimum of 6 copies required for the closely-related task of stabilizer testing. We show that our tester is tolerant, by adapting techniques from tolerant stabilizer testing to our setting. In doing so, we settle in the positive a conjecture of Bu, Gu and Jaffe, by proving a polynomial inverse theorem for a non-commutative Gowers 3-uniformity norm. We also consider the restricted setting of single-copy access, where we give an $O(n)$-query Clifford tester that requires no auxiliary memory qubits or adaptivity. We complement this with a lower bound, proving that any such, potentially adaptive, single-copy algorithm needs at least $Ω(n^{1/4})$ queries. To obtain our results, we leverage the structure of the commutant of the Clifford group, obtaining several technical statements that may be of independent interest. |
| title | Clifford testing: algorithms and lower bounds |
| topic | Quantum Physics Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.07164 |