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.