# Gate-level implementation of Eigenvalue-Inversion in HHL

I am trying to understand how does the gate-level implementation of eigenvalue-inversion step in the HHL algorithm works.

I am following this reference, where it is stated (Lemma 4) that this can be accomplished by the use of controlled rotations:

$$U_\theta: |\widetilde{\theta} \rangle |0 \rangle \rightarrow |\widetilde{\theta} \rangle \left(\cos \widetilde{\theta} |0\rangle + sin \widetilde{\theta} |1 \rangle \right )$$

$$U_\theta = \sum_{\widetilde{\theta} \in \{0,1\}^n} |\widetilde{\theta}\rangle \langle \widetilde{\theta}| \otimes \exp \left(-i \widetilde{\theta} \sigma_y \right)$$

where $$\widetilde{\theta}$$ is the n-bit finite precision representation of the angle $$\theta$$, and $$\sigma_y$$ the Y Pauli matrix.

My question is, how are the rotation angles $$\widetilde{\theta}$$ for the unitary $$U_\theta$$ calculated/applied without a-priori knowledge of the eigenvalues $$\lambda_j$$ of the system matrix $$A$$?

I understand that the state-vector $$|\widetilde{\theta} \rangle$$ is obtained in the previous step of the algorithm by extracting the eigenvalues $$|\lambda_j \rangle$$ of $$A$$ using QPE (and then applying an inverse + arcsin function as described here), but I am not sure how are these angles also applied as the parameters for the controlled-rotation gates (exponent parameter in $$U_\theta$$.)

FYI, I did see this other post where it is stated: "You... ...have (at least a good approximation to) your eigenvalues recorded on a register. If you control off that register, you can use it to decide the angle of the rotation for each eigenvector."

So my question is how do you "use it [the register containing $$|\widetilde{\theta} \rangle$$] to decide the angle of the rotation [$$\widetilde{\theta}$$ in the $$\exp$$ function of $$U_\theta$$]"?

Thanks!

• Nice question. If there's no answers after a while you can ping me and I can try my best to make time to write you an answer. Dec 28, 2020 at 0:37
• Thank you @user1271772, with some help, I have actually identified a way to implement this, but I would appreciate if you could let me know if this is what you had in mind. For theta in [0,2*pi): Each qubit theta_k (of the n-bit representation of theta) is used as the control of an CRx(alpha_k) gate acting on an ancilla qubit. The angle applied alpha_k is given by (2*pi/2^n)*2^k Dec 28, 2020 at 20:16
• You do have an answer now, thankfully :) Dec 28, 2020 at 20:17

Using the register to decide the angle of rotation means the following: you have a register $$|\tilde{\theta}\rangle$$ (composed of potentially more than one qubit) and you apply rotations of another register controlled on the value of the qubits of $$|\tilde{\theta}\rangle$$. Different rotations that you apply result in different functions being implemented on your ancilla qubits. But that was possibly already known to you.
The question of which rotations to do for applying a specific function is much more complicated, and I am not aware of any general solution. For once, Qiskit has its own implementation of HHL, but I don't know up to which point it is general. There are however, other examples in which it is "easy" to implement, for instance, the eigenvalue inversion function required for HHL. In this paper, the authors implement an approximation of the eigenvalue inversion subroutine (the code in Quil can be found in the associated GitLab repository) that is exact in the case of eigenvalues that are powers of 2. The reason why it is exact for powers of 2 is because in that case the inversion can be written as a combination of bit swaps, so the eigenvalue inversion subroutine is a collection of controlled SWAP gates (a pictorial representation of the circuit is in Fig. 3 in this paper). But, as I said before, I am not aware of general ways of implementing large classes of functions, so far.
• The problem is in the first step of the two in the question you refer to. The second part maps a bit string into an amplitude, and that is fairly easy done with controlled Ry gates. The problem still lies in the first step, the one that (roughly) maps a register encoding $\lambda$ to a register encoding $1/\lambda$. From the answer to the question it is possible that IBM has figured out a way to do so, but it is by no means a simple thing to do.