4
$\begingroup$

In the HHL algorithm, how do you efficiently do the $\lambda-$controlled rotation on the ancillary qubit ? It seems to me after reading around some answers that this can be done in two steps :

  • First, we map $|\lambda\rangle\mapsto |\frac{1}{\pi}\arcsin(\frac{C}{\lambda})\rangle$, defining $|\frac{1}{\pi}\arcsin(\frac{C}{\lambda})\rangle$ to be a binary representation $|\frac{1}{\pi}\arcsin(\frac{C}{\lambda})\rangle$ with $m$ qubits.
  • Then perform a controlled rotation $U_y(|\theta\rangle \otimes |0\rangle)\mapsto |\theta\rangle \otimes \big(\cos(\theta)|0\rangle + \sin{(\theta})|1\rangle\big)$ where $U_y$ is simply $$ U_y(|\theta\rangle \otimes |0\rangle) = \prod_{j=1}^m (I^{\otimes^m}\otimes R_y(2\pi\theta_j/2^j)) $$ i.e. a sequence of controlled rotations where we successively halve the angle of rotation conditionally of the digits of the binary representation of $\theta$.

My question is the following how can one implement efficiently the first step in an environment such as Qiskit ?

$\endgroup$
2
  • $\begingroup$ Hello, did you check this tutorial from Qiskit directly? qiskit.org/textbook/ch-applications/hhl_tutorial.html $\endgroup$ – Lena Dec 9 '20 at 17:50
  • $\begingroup$ Yes, I read the all tutorial but they didn't explain how to compute eigenvalue rotation without lost of generality. In their example developed in part B, they apply a $2-$controlled rotation by $01$ and $10$ but it's a particular case. $\endgroup$ – SRichoux Dec 9 '20 at 18:00
4
$\begingroup$

There is a new approach that will be merged soon in qiskit terra (here for the PR) that uses polynomial approximation to compute $\arcsin(C/\lambda)$, and asymptotically this would be the efficient implementation.

In practice if you are solving a $2\times 2$ matrix or a very small system it would be better to hard code the rotations.

The theory and error analyses of this approach are explained in Section VI of this paper.

$\endgroup$

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.