Building a state with parallel execution

Question

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?

Answer 1

am I sure that the compiler will always be able to decompose this big gate into a succession of smaller, allowed gates, without breaking the complexity

No, you're not. This is the whole problem with algorithms, be they classical or quantum.

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$.