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

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.

• You might be interested in this answer, in which I sketched out exactly what you're after! quantumcomputing.stackexchange.com/a/10282/1837 – DaftWullie Mar 30 at 14:16
• Please correct me if I wrong, I think the difference here is that I am looking to construct the rotation and angle $\theta$ such that it maps $f(x)$ to the ancilla state, rather than in the case of your example where $f(x) \rightarrow \theta$ – Sam Palmer Mar 30 at 14:26
• Your question makes me think I’ve misunderstood something. You’re trying to implement a controlled Y rotation of angle theta where cos(theta)=f(x), right? So you can do a classical computation to go from x to theta (approximately). – DaftWullie Mar 30 at 15:22
• @DaftWullie working through this a bit more, phase rotations are additive?, so I can do multiple controlled phase rotations $R_z^1R_z^2 | 0 \rangle = e^{i(\theta_1 + \theta_2)} |0>$ and then do a basis rotation to apply the y rotation $\hat{\theta} =\theta_1 + \theta_2$ to the state to get $\cos(\hat{\theta}) = f(x)$ ? – Sam Palmer Mar 30 at 16:15
• Yes, that's exactly what I'm proposing. – DaftWullie Mar 31 at 14:24

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$$.
• Ah, I remember reading that paper before, the issue I had here was that it relied upon $O(2^K)$ gates, I was wondering if there is a solution only involving $O(K)$ gates, however that may just seem not possible! – Sam Palmer Mar 30 at 15:22