4
$\begingroup$

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.

Improve this question
$\endgroup$
12
  • 2
    $\begingroup$ You might be interested in this answer, in which I sketched out exactly what you're after! quantumcomputing.stackexchange.com/a/10282/1837 $\endgroup$
    – DaftWullie
    Mar 30, 2020 at 14:16
  • 1
    $\begingroup$ 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 $ $\endgroup$
    – Sam Palmer
    Mar 30, 2020 at 14:26
  • 1
    $\begingroup$ 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). $\endgroup$
    – DaftWullie
    Mar 30, 2020 at 15:22
  • 1
    $\begingroup$ @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)$ ? $\endgroup$
    – Sam Palmer
    Mar 30, 2020 at 16:15
  • 1
    $\begingroup$ Yes, that's exactly what I'm proposing. $\endgroup$
    – DaftWullie
    Mar 31, 2020 at 14:24

2 Answers 2

Reset to default
2
$\begingroup$

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

enter image description here

Improve this answer
$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.