Clifford testing: Algorithms and lower bounds

We consider the problem of Clifford testing, which asks whether a black-box n-qubit unitary is a Clifford unitary or at least ϵ-far from every Clifford unitary. We give the first 4-query Clifford tester, which decides this problem with probability poly(ϵ). 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 ω(n1/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.

• View at Publisher
• View at Scopus

Free Full Text ( Final Version , 635kb )

See Also
techReport Clifford testing: algorithms and lower bounds M. Hinsche (Marcel), Z Bao (Zongbo), P.J. van Dordrecht (Philippe), J. Eisert (Jens), J. Briët (Jop) and J. Helsen (Jonas)