Learning and testing algorithms for the Clifford group

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\left(n\right)$ 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.