  We prove a quantum information-theoretic conjecture due to Ji, Liu and Song
(CRYPTO 2018) which suggested that a uniform superposition with random
\emph{binary} phase is statistically indistinguishable from a Haar random
state. That is, any polynomial number of copies of the aforementioned state is
within exponentially small trace distance from the same number of copies of a
Haar random state.
  As a consequence, we get a provable elementary construction of
\emph{pseudorandom} quantum states from post-quantum pseudorandom functions.
Generating pseduorandom quantum states is desirable for physical applications
as well as for computational tasks such as quantum money. We observe that
replacing the pseudorandom function with a $(2t)$-wise independent function
(either in our construction or in previous work), results in an explicit
construction for \emph{quantum state $t$-designs} for all $t$. In fact, we show
that the circuit complexity (in terms of both circuit size and depth) of
constructing $t$-designs is bounded by that of $(2t)$-wise independent
functions. Explicitly, while in prior literature $t$-designs required linear
depth (for $t > 2$), this observation shows that polylogarithmic depth suffices
for all $t$.
  We note that our constructions yield pseudorandom states and state designs
with only real-valued amplitudes, which was not previously known. Furthermore,
generating these states require quantum circuit of restricted form: applying
one layer of Hadamard gates, followed by a sequence of Toffoli gates. This
structure may be useful for efficiency and simplicity of implementation.
