5
$\begingroup$

In HHL algorithm, for subroutine involving controlled rotation, after applying $R_y(\theta)$, where $\theta=2\sin^{-1}\left(\frac{C}{\lambda}\right)$ to the ancilla, the state changes to $\sqrt{1-\frac{C^2}{\lambda^2}}|0\rangle+\frac{C}{\lambda}|1\rangle.$

Question

If $\lambda=1$, then by $\sqrt{1-\frac{C^2}{\lambda^2}}|0\rangle+\frac{C}{\lambda}|1\rangle$ and choosing $C=1$, we get $\theta=\pi$. For $\lambda=2$, $\theta=\frac{\pi}{3}.$ So in general, for each $\lambda$, correspondingly there's a different $\theta$. Since we don't know eigenvalues a priori, how do we account $\theta $s for superpositon of eigenvalues?

With respect to the circuit here on page 5, I don't understand how the controlled rotation part works. Will this circuit work when I choose a hermitian matrix $A_{4\times 4}$ such that, one of it's eigenvalues, $\lambda_j=10\neq 2^i,i \in \mathbb{Z}$ ?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ There are too many questions here. Please ask one question per post, as it will help us give you better answers. $\endgroup$
    – DaftWullie
    Commented Apr 6, 2020 at 8:22
  • $\begingroup$ How I remember, the circuit in the paper (Fig.4) is working only for (1) matrix from the same paper. The more generic solution/circuit is proposed in other figures of the same paper. $\endgroup$
    – Davit Khachatryan
    Commented Apr 6, 2020 at 9:25

2 Answers 2

Reset to default
4
$\begingroup$

You don't know the eigenvalues a priori, but you have performed phase estimation, and 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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ The state of register after phase estimation will be superposition of all the eigenvalues of matrix A. We use it as control rotation to ancilla. I don't understand that how do we decide the angles of rotation? $\endgroup$
    – Omkar
    Commented Apr 6, 2020 at 9:39
  • 2
    $\begingroup$ No, it's entangled with the input state. So if the eigenvectors of $A$ are $|\lambda_i\rangle$, then the input state is decomposed as $\sum_i\alpha_i|\lambda_i\rangle$, then after phase estimation on $t$ qubits, you have $\sum_i\alpha_i\lambda_i\rangle|\theta_i\rangle$, where $\theta_i$ is the best approximation to $e^{2\pi\theta_i/2^t}=\lambda_i$. If you do a controlled rotation off the $|\theta_i\rangle$ part, that you can say "if the angle is $\theta_i$, do rotation $R_y(f(\theta_i))$ where $f$ is some extra calculation you might perform. $\endgroup$
    – DaftWullie
    Commented Apr 6, 2020 at 9:43
  • $\begingroup$ Please also have a look at this question: quantumcomputing.stackexchange.com/questions/11347/… and in particular my comments after the question. $\endgroup$
    – DaftWullie
    Commented Apr 6, 2020 at 9:44
  • $\begingroup$ In this case is $f(\theta_i)=arcsin(\frac{2C}{\theta_i})$? If yes, how do we compute it? $\endgroup$
    – Omkar
    Commented Apr 6, 2020 at 17:13
  • 3
    $\begingroup$ My point is that there is a way that you can calculate it on a classical computer, even if the translation from high-level programming language to a sequence of logical operations is absolutely awful (and I don't know what it actually is, just that it exists). So, you find that circuit and you translate it into a reversible set of logic gates, and you can implement that same set of logic gates on a quantum computer. $\endgroup$
    – DaftWullie
    Commented Apr 8, 2020 at 15:20
0
$\begingroup$

The question of how the eigenvalue inversion subroutine is implemented in general is not solved yet in a satisfactory way, to my knowledge. I myself spent quite some time looking for the classical algorithm implemented in classical computers to try to make it reversible, but even that was lost time. What I am aware of is that Qiskit has its own implementation (although I don't know how general it is), and that there are some papers that propose/implement approximations of the inversion function. For instance, this paper implements 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). It is however very unlikely that this algorithm can be improved further without a huge increase in qubit count, since the next step of the iteration (Fig. 4 in the last paper cited) has an output very nonlinear in the input.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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