Why does the quantum linear inversion algorithm allow to implement $e^{-ig(\rho)}$ efficiently using multiple copies of $\rho$?

Question

In (Lloyd et al. 2013), the authors write (beginning of page 3) that the quantum matrix inversion techniques presented by some of the same authors in (Harrow et al. 2008) allow to efficiently implement $e^{-ig(\rho)}$ for any simply computable function $g(x)$, using multiple copies of the density matrix $\rho$ (see (1) below for a bit more context).

Given that (Harrow et al. 2008) presents a quantum algorithm to obtain a state $|x\rangle$ proportional to $A^{-1}|b\rangle$ for a given $A$ and $|b\rangle$, it doesn't seem obvious to me how this can be used to compute $e^{-ig(\rho)}$.

To which techniques exactly are the authors referring to? And how are they applied to get the stated result?

---

(1) More precisely, in the (Lloyd et al. 2013) paper, before making the statement that is the object of this question, the authors describe a method to construct $e^{-i\rho t}$, to accuracy $\epsilon$, using $n$ copies of $\rho$ with $n=O(t^2 \epsilon^{-1})$.

Moreover, what is meant by simply computable function does not seem to be explained in the paper.

Answer 1

One way to go about this is using the Linear Combination of Unitaries (LCU) algorithm. The LCU algorithm simulates the action of any operator that can be written as a linear combination of simulatable unitary operators. A full treatment of this can be found in Kothari's thesis. Using LCU algorithm, given the ability to apply $e^{i \rho t}$ to the state, the action of $f(\rho)$ on a state can be simulated. You do this by first writing $f(\rho)$ in Fourier space,

$$ f(\rho) = \int^{+\infty}_{-\infty} dt~ \hat{f}(t) ~e^{i\rho t}.$$

You can already see that this represents $f(\rho)$ as a sum of simulatable unitaries. But this is a continuous and infinite sum. For many functions this integral can be truncated and discretized to approximate $f(\rho)$ well. Kothari's thesis has some examples of such functions, including $A^{-1}$. See also this work, that uses this technique to simulate the action of $e^{-\beta H}$ on a state.

I don't think that this is the technique Llyod et.al has in their mind. But the LCU algorithm is a more recently developed technique that solves the problem.