# Building a state with parallel execution

I'm trying to implement the main algorithm described in the Quantum Recommendation Systems paper. In order to do this, I have to create a quantum state $$|x\rangle$$ corresponding to a real vector stored in QRAM. I used an algorithm described more in detail in another paper, in which one can read:

For the runtime, there are $$2^k$$ rotations executed at the $$k$$-th level of the tree, apart from the last level where there are none. For a given level these rotations can be executed in parallel as they are all controlled operations on the same qubit, conditioned on different bit-string values of a shared register. To see this, let $$U_x$$ be a single qubit rotation conditioned on a bitstring $$x \in \{0, 1\}^k$$. Then the unitary $$\bigoplus\limits_{x\in\{0,1\}^k} U_x$$ applied to $$|y\rangle\otimes|q\rangle$$ achieves the desired parallel operation on the single qubit $$|q\rangle$$, where $$|y\rangle = \sum\limits_{x\in\{0,1\}^k}\alpha_x\,|x\rangle$$ is some superposition over bitstrings.

I'm not sure that I understand this notion of parallel execution. In the algorithm, at a given step $$k$$, one performs on one qubit $$2^k$$ controlled rotation conditionned on every qubit amongst the first $$k-1$$. Hence, we can summarize this as one big unitary matrix that acts on the first $$k$$ qubits, which will look-like $$\begin{bmatrix}R_{\theta_1}&0&0\\\vdots&\ddots&\vdots\\0 & 0 & R_{\theta_{2^k}}\end{bmatrix}$$, where for a given angle $$\theta$$, $$R_\theta$$ is the rotation of angle $$\theta$$ around the $$Y$$-axis of the Bloch sphere.

If we assume that this big operator is applied in $$O(1)$$, then I understand the notion of parallelism: you don't have to successively apply the $$2^k$$ controlled gates, so you have a gain in complexity. But then, there is one problem I can't cope with. When you execute an algorithm on a quantum computer, I read that you are only allowed to use a specific set of gates. Hence, a compiler takes your code and transforms it to a compatible code. But am I sure that the compiler will always (or even sometimes) be able to decompose this big gate into a succession of smaller, allowed gates, without breaking the complexity?

However, in the specific case you're talking about, there is a nice implementation. Imagine that you want to apply the rotation $$R_y(\theta_x)$$ if the main register is in the state $$|x\rangle$$. Let me further more assume that there is a good $$t$$-bit approximation to the values $$\theta_x$$ for which there is an efficient classical function. So, I have a function $$f(x)$$ that outputs the value $$\tilde\theta_x$$, the $$t$$-bit approximation to $$\theta_x$$. Since it's a classical function, I can also write it as a quantum function $$V$$ that acts as $$V|x\rangle|0\rangle=|x\rangle|\tilde\theta_x\rangle$$, having introduced an ancilla system of $$t$$ bits. Implementation of $$V$$ is efficient because the evaluation of $$f$$ is efficient.
Next, I know that if I apply phase gates on the $$t$$ qubits of the ancilla register (phase $$\pi,\pi/2,\pi/4,\pi/8,\ldots$$), I can implement $$|\tilde\theta_x\rangle\rightarrow e^{i\tilde\theta_x}|\tilde\theta_x\rangle$$. If I just inverted my original calculation at this point, $$V^\dagger$$, then the net effect is $$e^{i\tilde\theta_x}|x\rangle\rightarrow|x\rangle$$. However, imagine now that I replace the phase gates with controlled-phase gates, controlled off the single qubit target. Then the net effect of the gate is a controlled-phase rotation of angle $$\tilde\theta_x$$ between the $$|x\rangle$$ register and the single qubit target. At this point, you're essentially there. You just need a basis rotation (e.g. $$(Z+Y)/\sqrt{2}$$) on the target qubit to convert the gate from controlled-$$Z$$ to controlled-$$Y$$.