Learning and testing algorithms for the Clifford group
Richard A. Low · Physical Review A · 2009
Given oracle access to an unknown unitary $C$ from the Clifford group and its conjugate, we give an exact algorithm for identifying $C$ with $O(n)$ queries, which we prove is optimal. We then extend this to all levels of the Gottesman-Chuang hierarchy (also known as the ${\mathcal{C}}_{k}$ hierarchy). Further, for unitaries not in the hierarchy itself but known to be close to an element of the hierarchy, we give a method of finding this close element. We also present a Clifford testing algorithm that decides whether a given black-box unitary is close to an element of the Clifford group or far from every element of the Clifford group.