  We present new designs for quantum random access memory. More precisely, for
each function, $f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^d$, we construct
oracles, $\mathcal{O}_f$, with the property \begin{equation}
  \mathcal{O}_f \left| x \right\rangle_n \left| 0 \right\rangle_d = \left| x
\right\rangle_n \left| f(x) \right\rangle_d. \end{equation} Our methods are
based on the Walsh-Hadamard Transform of $f$, viewed as an integer valued
function. In general, the complexity of our method scales with the sparsity of
the Walsh-Hadamard Transform and not the sparsity of $f$, yielding more
favorable constructions in cases such as binary optimization problems and
function with low-degree Walsh-Hadamard Transforms. Furthermore, our design
comes with a tuneable amount of ancillas that can trade depth for size. In the
ancilla-free design, these oracles can be $\epsilon$-approximated so that the
Clifford + $T$ depth is $O \left( \left( n + \log_2 \left( \tfrac{d}{\epsilon}
\right) \right) \mathcal{W}_f \right)$, where $\mathcal{W}_f$ is the number of
nonzero components in the Walsh-Hadamard Transform. The depth of the shallowest
version is $O \left( n + \log_2 \left( \tfrac{d}{\epsilon} \right) \right)$,
using $n + d \mathcal{W}_f$ qubit. The connectivity of these circuits is also
only logarithmic in $\mathcal{W}_f$. As an application, we show that for
boolean functions with low approximate degrees (as in the case of read-once
formulas) the complexities of the corresponding QRAM oracles scale only as
$2^{\widetilde{O} \left( \sqrt{n} \log_2 \left( n \right) \right)}$.
