Abstract
We present new designs for quantum random access memory. More precisely, for each function, f : F₂ⁿ → F₂^d, we construct oracles, 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 ε-approximated so that the Clifford + T depth is O ( ( n + log₂ ( d/ε ) ) W_f ), where W_f is the number of nonzero components in the Walsh-Hadamard Transform. The depth of the shallowest version is O ( n + log₂ ( d/ε ) ), using n + d W_f qubit. The connectivity of these circuits is also only logarithmic in 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^O ( √n log₂ ( n ) ).