Implementasi level gerbang dari Eigenvalue-Inversion di HHL

Dec 28 2020

Saya mencoba untuk memahami bagaimana implementasi level gerbang dari langkah inversi eigenvalue dalam algoritma HHL bekerja.

Saya mengikuti referensi ini , di mana dinyatakan (Lemma 4) bahwa ini dapat dicapai dengan menggunakan rotasi terkontrol:

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

dimana $\widetilde{\theta}$ adalah representasi presisi hingga n-bit dari sudut tersebut $\theta$, dan $\sigma_y$ matriks Y Pauli.

Pertanyaan saya adalah, bagaimana sudut rotasinya $\widetilde{\theta}$ untuk kesatuan $U_\theta$ dihitung / diterapkan tanpa pengetahuan a-priori tentang nilai eigen $\lambda_j$ dari matriks sistem $A$?

Saya memahami bahwa negara-vektor $|\widetilde{\theta} \rangle$ diperoleh pada langkah algoritma sebelumnya dengan mengekstraksi nilai eigen $|\lambda_j \rangle$ dari $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!

Jawaban

1 Alex Dec 28 2020 at 18:25

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.