  We analyze the complexity of learning $n$-qubit quantum phase states. A
degree-$d$ phase state is defined as a superposition of all $2^n$ basis vectors
$x$ with amplitudes proportional to $(-1)^{f(x)}$, where $f$ is a degree-$d$
Boolean polynomial over $n$ variables. We show that the sample complexity of
learning an unknown degree-$d$ phase state is $\Theta(n^d)$ if we allow
separable measurements and $\Theta(n^{d-1})$ if we allow entangled
measurements. Our learning algorithm based on separable measurements has
runtime $\textsf{poly}(n)$ (for constant $d$) and is well-suited for near-term
demonstrations as it requires only single-qubit measurements in the Pauli $X$
and $Z$ bases. We show similar bounds on the sample complexity for learning
generalized phase states with complex-valued amplitudes. We further consider
learning phase states when $f$ has sparsity-$s$, degree-$d$ in its
$\mathbb{F}_2$ representation (with sample complexity $O(2^d sn)$), $f$ has
Fourier-degree-$t$ (with sample complexity $O(2^{2t})$), and learning quadratic
phase states with $\varepsilon$-global depolarizing noise (with sample
complexity $O(n^{1+\varepsilon})$). These learning algorithms give us a
procedure to learn the diagonal unitaries of the Clifford hierarchy and
IQP~circuits.
