Rotations to encode $f(x)$ into ancilla qubit for quantum Monte Carlo

Question

I'm trying to understand the quantum monte-carlo algorithm starting at the most basic version. A key step is rotating (Algorithm 1 p.g 8), an ancilla bit by rotation $R$ with respect to the value of a function $f(x)$ where $x$ is a bit string encoded in $|x\rangle$, such that:

$R|x\rangle|0\rangle = \sum_{x} |x\rangle(\sqrt{1-f(x)}|0\rangle + \sqrt{f(x)}|1\rangle) $

Starting with the simple function $f(x) \rightarrow y $, where $x \in \{0,1\}^k$ and $y \in [0,1]$, i.e $f(x)$ maps the bit string to its corresponding fractional number, I am trying to find the rotation $R$.

Initially I was thinking along the lines of using a controlled rotation for each bit $k$ such that $R_y^k|0 \rangle \rightarrow (\sqrt{1-\frac{1}{2^k}}|0\rangle + \sqrt{\frac{1}{2^k}}|1\rangle) $ however the issue here is that successive rotations aren't additive, so for example the the encoding the bit string $|x \rangle = \{1,1\} $:

$f(\{1,1\}) \rightarrow 0.75$,

the controlled rotations from the first and second bit would be

$R_y^1R_y^2|0 \rangle \neq (\sqrt{1-f(x)}|0\rangle + \sqrt{f(x)}|1\rangle)$ .

which is due to the nonlinearity of $\arccos$

$\arccos(\sqrt{0.5}) + \arccos(\sqrt{0.25}) \neq \arccos(\sqrt{0.75})$

The other approach is to have a controlled rotation for each permutation in $\{0,1\}^k$ however this results gates $O(2^K)$ .

For this simple $f(x)$ what is the best way to derive the circuit for rotation $R$ controlled by $|x \rangle$ and if there is a circuit that only involves $O(K)$ gates.

Thanks!

---- Current ideas ----

1) Linear approximation of $\arccos$ for sufficiently small $a,b$ we can apply a linear correction term to approximate

$\arccos(a) + \arccos(b) = \arccos(a+b) - \frac{\pi}{2}$

Generalising this for a $K$ bit system $\{i_1,i_2, \dots i_K\} $ the correction is $-\frac{\pi}{2}(1-\sum_ki_k)$.

In this case instead of $f(x) \rightarrow y $ it is required that $f(x) \rightarrow \sqrt{y} $, and assuming the linear approximation $O(K)$ rotations are required to map binary representation of $\sqrt{y}$ to the ancilla state

2) Be lazy and implement a qgan neural network that approximates the rotations. Given a $K$ bit system this only requires $2^K$ training values.

Answer 1

From "Supervised Learning with Quantum Computers" by M. Schuld & F. Petruccione (p. 157):

Answer 2

Please have a look at article Transformation of quantum states using uniformly controlled rotations, chapters 1 and 2. These provides you with construction of general rotation gate controlled by $n$ qubits with different rotations angles for each basis state $|x\rangle$.

You also might be interested in some of these articles on quantum computers application in finance. There are a few articles on Monte Carlo.