How are black-box oracles implemented in Hamiltonian simulation?

Question

I am currently trying to decompose a hessian to a sum of unitaries $H=\sum a_i U_i$.

The papers VQLS and Black-box Hamiltonian Simulation state that it can be done, but requires the use of an oracle acting as

$$O_F \left| j, k \right> = \left| j, f(j, k)\right>$$ for any $j \in \{1,... N\}$ and $k \in \{1, ..., D\}$, where $f(j,k)$ gives the row index of the $k$th nonzero element of column $j$.

It is also stated in the paper that this is generally not hard to contruct, yet I don't have a clue how to do that.

So, is it that trivial to implement this oracle?

Answer 1

Black boxes in general are not uniquely defined. See, for instance, the Deutsch-Jozsa algorithm: there are many ways to create a balance or constant function. You'd need to test ways to manipulate your input to get the output, so you need to play around with linear algebra and think about how this would translate to a circuit.

Answer 2

From my understanding, black boxes(oracle) which is the same idea as classical computer functions, is an idea of a group of unknown gates or things that are irreversible, that help transform a system from quantum state $|x>$ into $|f(x)$>, trough the evolution of quantum states, like Grover search make use of amplitude amplification, which is similar to an oracle, but try to amplitude average.For more detailed explanation of Grover search
For a more detailed explanation:

• https://medium.com/@brcsomnath/qml-quantum-oracle-c8a48cdaf851
• https://arxiv.org/pdf/2112.06700.pdf
• https://quantumcomputing.stackexchange.com/a/4626

hope it helps you understand how to construct an oracle.

Answer 3

The question essentially boils down to this question.

Quick answer: it is not always possible to build an efficient oracle.

In terms of "is it easy for the programmer to implement this oracle?", most of the time it is not. Here are links you might be interested in:

• It turns out I implemented a similar oracle a few years ago. The research paper is available here^paywall and here^free (you just have to click on the "PDF" button and you'll have access to the paper legally and for free, thanks ACM).
• The implementation linked with the paper above is available here. It is heavily documented, you will just have to render the ReStructuredText.
• The hodl aims at simplifying this.