4

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.

Sam Palmer
  • 949
  • 4
  • 11
  • 2
    You might be interested in this answer, in which I sketched out exactly what you're after! https://quantumcomputing.stackexchange.com/a/10282/1837 – DaftWullie Mar 30 '20 at 14:16
  • 1
    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 '20 at 14:26
  • 1
    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 '20 at 15:22
  • yeah I think i'm trying to find the rotation controlled Y s.t. $\cos(\theta) = \sqrt{f(x)}$ – Sam Palmer Mar 30 '20 at 15:34
  • @DaftWullie, so if I understand your answer correctly (after rereading a few times) I need to implement a second function, $g(x)$ that maps $f(x) \rightarrow_{g(x)} \theta_x$? – Sam Palmer Mar 30 '20 at 15:38
  • 1
    @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 '20 at 16:15
  • the issue with this approach is still that $\arccos(\sqrt{0.5}) + \arccos(\sqrt{0.25}) \neq \arccos(\sqrt{0.75})$ – Sam Palmer Mar 30 '20 at 16:38
  • But this is not what you're trying to use. Instead, you're trying to say that $\arccos(\sqrt{0.75})=\theta\pi$, and that $\theta$ has a binary expansion $0.\theta_1\theta_2\theta_2\ldots\theta_k$, which means that $\theta=\sum_i\theta_i/2^i$. So, if we can create individual phase rotations $e^{i\theta_j Z\pi/2^j}$, then those phases all add up to give what you need. Note that $e^{i Z\pi/2^j}$ is just a standard $Z$ rotation. The effect of the $\theta_j\in{0,1}$ can be implemented by use of a control ($\theta_j=0$ means don't do a rotation, $\theta_j=1$ means do the rotation. – DaftWullie Mar 31 '20 at 07:24
  • but does this not still then require a gate of size $2^K$ to encode $\theta_i$ for all the binary basis states? as each state would require its own $\theta$, or are you proposing that there is also an $\arccos$ circuit implemented to calculate $\theta_i$ on the fly. – Sam Palmer Mar 31 '20 at 14:19
  • 1
    Yes, that's exactly what I'm proposing. – DaftWullie Mar 31 '20 at 14:24
  • my idea of using the linearity is that for each number represented in ${0,1}^K$ would only require one rotation for each qubit $k$ that is $|1 \rangle$ and each $\theta_k = \arccos(2^{-k})$. Then in theory this would only require $K$ controlled rotations to be implemented – Sam Palmer Mar 31 '20 at 14:27
  • @DaftWullie I see :D, I will look into $\arccos$ circuits....I didn't realise how more involved this seemingly 'simple' rotation R would be! – Sam Palmer Mar 31 '20 at 14:29

2 Answers2

2

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

enter image description here

Farida
  • 21
  • 3
1

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.

Martin Vesely
  • 13,891
  • 4
  • 28
  • 65
  • 1
    Thanks! yeah so the bigger picture is that I am trying to implement the Rebentrost, Gupt and Bromely paper! – Sam Palmer Mar 30 '20 at 14:29
  • 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 '20 at 15:22
  • @SamPalmer: According to this paper https://arxiv.org/pdf/quant-ph/0404089.pdf number of gates is increasing exponentially for such construction with increasing number of controlling qubits. – Martin Vesely Mar 30 '20 at 18:13