It is well-known that learning a pure n-qubit stabilizer state |\psi\rangle both requires, and can be accomplished with, access to a number of copies of |\psi\rangle linear in n. However, the precise constant coefficient of this scaling does n
It is well-known that learning a pure n-qubit stabilizer state |\psi\rangle both requires, and can be accomplished with, access to a number of copies of |\psi\rangle linear in n. However, the precise constant coefficient of this scaling does not appear to have been determined. Here we prove that L_\delta(n), the smallest number of copies from which a quantum procedure can identify any stabilizer state with failure probability at most 0<\delta<1/8, satisfies n+\lceil\log_2(1/\delta)\rceil-3\leq L_\delta(n)\leq n+\left\lceil\log_2(1/\delta)\right\rceil+4. We present a polynomial-time quantum learning algorithm that saturates this bound, achieving a constant factor improvement in sample-complexity over previously known approaches. As an immediate corollary, we obtain via the Choi-Jamiolkowski isomorphism an algorithm for learning an unknown n-qubit Clifford unitary from 2n+\left\lceil\log_2(1/\delta)\right\rceil+4 queries, the n-dependence of which we show to be optimal. Our proof technique, which involves Fourier analysis on the abelian group Z_4^n \times F_2^{n(n-1)/2}, seems to be qualitatively different to previous approaches to stabilizer state learning, and may be of some independent interest; in particular, it admits natural generalisations to further problems in quantum learning theory.