2025-10-09
Clifford testing: algorithms and lower bounds
Publication
Publication
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 $\Omega(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.
| Additional Metadata | |
|---|---|
| doi.org/10.48550/arXiv.2510.07164 | |
| Organisation | Algorithms and Complexity |
|
Hinsche, M., Bao, Z., van Dordrecht, P., Eisert, J., Briët, J., & Helsen, J. (2025). Clifford testing: algorithms and lower bounds. doi:10.48550/arXiv.2510.07164 |
|
