Semiclassical quantum Fourier transform

Let $n\geq1$, $N=2^n$, $\omega=e^{2\pi i/N}$, and $\ket{\psi}=\sum_{j=0}^{N-1}\alpha_j\ket{j}$ be an $n$-qubit state. There exists an $n$-qubit quantum circuit using at most $n$ Hadamard gates, $n(n-1)/2$ single-qubit phase gates and $n$ classical bits to obtain a classical output $k\in\{0,\ldots,N-1\}$ with distribution $$ \Pr[k] = \frac{1}{N} \left|\sum_{j=0}^{N-1}\alpha_j\omega^{jk}\right|^2. $$