{"ID":2858859,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.07164","arxiv_id":"2510.07164","title":"Clifford testing: algorithms and lower bounds","abstract":"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.","short_abstract":"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 mini...","url_abs":"https://arxiv.org/abs/2510.07164","url_pdf":"https://arxiv.org/pdf/2510.07164v1","authors":"[\"Marcel Hinsche\",\"Zongbo Bao\",\"Philippe van Dordrecht\",\"Jens Eisert\",\"Jop Briët\",\"Jonas Helsen\"]","published":"2025-10-08T16:02:07Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}