Convert a quantum Phase Oracle into a Probability Oracle

As a bare minimum, you would need access to a controlled version of your oracle. This cannot be created from the oracle itself (I'm sure there's already an SE question about this part, but cannot immediately lay my hands on it).

A typical construction would allow you to create (Hadamard - controlled oracle - Hadamard) would create an output $$ cosfrac{f(x)}{2}|0rangle+isinfrac{f(x)}{2}|1rangle, $$ which is obviously not what you're asking for. There might be some simple modifications that let you approximate what you're after.

To get what you're actually asking for, I suspect you have to do some quite sophisticated stuff. Essentially, perform phase estimation to estimate the value of $f(x)$ onto a second register, and use that register as a control to produce the state you want, with an accuracy defined by the size of the register.

Given controlled access to the phase oracle, this is possible with surprisingly small overhead by avoiding phase estimation altogether. The technique you are after relies on applying "quantum singular value transformations" to objects that are known as "block encodings", and it was invented by Gilyén et al. in 2018. The idea was originally introduced in this paper, Appendix B, which builds on techniques from this paper. Alternatively, you can have a look at this master's thesis, Circuit 6.2.5.

It appears that there is a slight error in the statement of the latter reference, as the action of $Q_f$ in the box referred to should actually be:

$$Q_f : |xrangle otimes |0rangle^{otimes 3} mapsto |xrangle otimes left(sqrt{frac12 + frac14f(x)}|0rangle^{otimes 3} + sqrt{frac12 - frac14f(x)}|psi(x)rangle|1rangleright).$$

Similarly, the action of $Q_2$ further down in the box should be:

$$Q_2 : |0rangle^{otimes 3} otimes |xrangle mapsto left(frac12sqrt{frac12 + frac14f(x)}|0rangle^{otimes 3} + sqrt{frac78 - frac{1}{16}f(x)}|1rangle|phi(x)rangleright)|xrangle.$$

All the rest should be correct as stated.

Keep in mind that the operation you wish to implement, i.e., the probability oracle of $f$, makes little sense whenever $f$ takes negative values. Moreover, the square root that appears in the probability oracle behaves erratically close to $0$, so it makes sense to assume that the function values of $f$ are bounded away from $0$. Gilyén et al. overcome this by assuming that the values of $f$ are contained in $(delta,1-delta)$. The latter reference essentially does the same thing, but overcomes it by assuming that $|f| leq 1/2$ and implementing the probability oracle of $frac12 + frac14f(x)$.

As a final remark, note that the conversion you are after up to norm error $varepsilon$ takes $O(log(1/varepsilon)^2)$ queries to the phase oracle, which is surprisingly little compared to the number of queries $O(1/varepsilon)$ you would need if you used phase estimation as an intermediate step. An explanation can be given along the following lines: phase estimation gives you a binary representation of the function value $f(x)$, which you subsequently postprocess to implement the probability oracle. This is a difficult task, as it requires learning the value of $f(x)$ in the process (as you could measure after phase estimation to get a binary value of $f(x)$). The new techniques circumvent writing down such a binary representation of $f(x)$. This is why I like to call the new technique an instance of analog computation, and I refer to subroutines that give you binary representations, like phase estimation, as instances of digital computation.