Novel oracle constructions for quantum random access memory

We present novel ways of designing quantum (random access) memory. More precisely, given a function, \(f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^d\), we construct oracles, \(\mathcal{O}_f\), with the property \(\mathcal{O}_f |x\rangle_n |0\rangle_d = |x\rangle_n |f(x)\rangle_ d\). Our constructions 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 (\frac{d}{\epsilon}) \right) W_f \right)\), where \(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 (\frac{d}{\epsilon}) \right)\), using \(n + d W_f\) qubit.

Preprint is available here.