In the rotation part of HHL algorithm, how do you decompose $R$ in terms of universal gates?

Question

In this paper, there is a diagram explaining how HHL works, which I attached below:

My question is, for the rotation part, how do you write $R$ as a combination of universal set of gates without knowing the eigenvalues a priori? Or what is a generic way of writing $R$ without doing any classical pre-computation regarding the eigenvalues?

In most of the implementations that I found online, it is assumed that the eigenvalues are known, and then one can find the angles of rotation by calculating for each eigenvalue: $\theta_i = arccos(\frac{C}{\lambda_i})$. After that, one can append for the ancilla register multiple $R_y$ gates with the aforementioned angles of rotation as arguments.

Thanks in advance for the help!

Answer 1

I think you are misunderstanding what HHL is doing here. Let's recall the problem definition earlier in §3.1:

We are given a system of $N$ linear equations with $N$ unknowns which can be expressed as $Ax=b$, where $x$ is a vector of unknowns, $A$ is the matrix of coefficients and $b$ is the vector of solutions. If $A$ is an invertible matrix, then we can write that the solution is given by $x=A^{−1}b$.

From this we can see that it is in fact $x$, not $A$, that is the unknown to be found. So, since you know what $A$ is, you do in fact know the eigenvalues of $A$ beforehand. In fact, since $A$ must be known to implement $U$, you must even know them in steps a) and c) also! Hence what you describe as "pre-computation" is actually a necessary step, encoding the problem statement into the gates in the algorithm :)

Edit:

As Nelimee mentioned in the comments, it seems that you don't necessarily need to know the eigenvalues exactly, and it is sufficient to know an upper and lower bound, as discussed in a previous post.