Novel oracle constructions for quantum random access memory

Summary

We present novel ways of designing quantum (random access) memory, also known as quantum dictionary encoders or data-access oracles.

Details

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. The complexity of our method scales with the sparsity of the Walsh–Hadamard transform, yielding more favorable constructions for binary optimization problems and functions with low-degree Walsh–Hadamard Transforms. The design comes with a tunable amount of ancillas, allowing for depth-to-size trade-offs.

Tags