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?