Efficiently performing controlled rotations in HHL

Question

This question builds off of this question.

In the HHL algorithm, how do you efficiently do the $\tilde{\lambda}_k$-controlled rotations on the ancilla qubit? It seems to me that since you don't know the eigenvalues a priori, you would have to control on every single $\lambda$ within your eigenvalue bounds $[\lambda_{\text{min}},\lambda_{\text{max}}]$ (since every $\lambda$ requires a different rotation angle), requiring a potentially exponential number of controlled rotations.

I kind of get how you can avoid an exponential number of controls in Shor's algorithm, because we can split up the modular exponentiation $a^x\pmod N$ so that we can deal with each bit of $x$ separately, $a^{2^{k-1}x_{k-1}}a^{2^{k-2}x_{k-2}}...a^{2^0 x_0} \pmod N$, so you only need as many controls as the number of bits of $x$. But I'm not sure how you can do something similar in the case of HHL, because $\tilde{\lambda}_k$ is not only in the denominator, but nested inside an arcsin, e.g. \begin{align} \mathrm{Controlled\ Rotation}=\sum_{m \in [\lambda_{\text{min}},\lambda_{\text{max}}]}\underbrace{|m\rangle\langle m|}_{\text{control reg.}} \otimes \underbrace{R_y\left(\sin^{-1}(2C/m) \right)}_{\text{anc reg.}} \end{align} where the number of terms in the sum is exponential in the number of bits of precision in $\lambda$. Is there a way to do this more efficiently, and if not, wouldn't this severely eat into the exponential speedup of the algorithm?

Answer 1

The setting is that you've got some state $$\sum_{x\in\{0,1\}^n}\alpha_x|x\rangle$$ on a register, you introduce an ancilla in state $|0\rangle$, and you want to create some state $$ \sum_{x\in\{0,1\}^n}\alpha_x|x\rangle\otimes R_X(f(x))|0\rangle $$ where $f(x)$ is some angle that you can compute. So, certainly, if you had to build that gate out of the $2^n$ different gates "if register=$x$, then apply $R_X(f(x))$ on the ancilla" for each $x$, that would be a very bad way to go. So, here's another way to think about it.

• Firstly, let's not apply $R_X(f(x))$, but $HR_Z(f(x))H$. The two Hadamards don't have to be controlled off anything because every gate requires them.
• Secondly, let's assume that we know an efficient classical computation of $f(x)$. That means we can build a reversible quantum computation that runs in the same time. This involves introducing a second register. So, what you'd have is $$ \sum_x\alpha_x|x\rangle|f(x)\rangle $$ where $|f(x)\rangle$ is some $k$-bit representation of the value $2^kf(x)/\pi$.
• Now, recognise that if you've got some state $|z\rangle$ for $z\in\{0,1\}^k$, it's easy to turn it into $e^{i\pi z 2^k}$ - you apply $Z$ on the most significant bit, $\sqrt{Z}$ on the second-most, $Z^{1/4}$ on the third, $Z^{1/8}$ on the fourth, and so on (think about how you convert from a binary to a decimal representation). Thus, if you apply these gates but controlled off the ancilla, this achieves exactly what you need.
• Finally, you have to uncompute the second register.

Thus, overall, the scaling is limited primarily by the time it takes to compute $f(x)$. The point is this happens simultaneously for all values of $x$ due to linearity.