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)}$.
Categories: quant-ph