1
$\begingroup$

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

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!

$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Knowing the exact eigenvalues of $A$ is not a requirement. The only requirement you have is to know an upper-bound and a lower-bound on the eigenvalues (see quantumcomputing.stackexchange.com/q/2604/1386). You can also perform Hamiltonian Simulation without knowing the eigenvalues, else VQE would never have been a thing. $\endgroup$ – Nelimee May 14 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.