Is HHL executed in a single run? If yes, how do they carry out controlled rotation without knowing eigenvalues?

Question

Even after reading several papers and almost all HHL related questions and answers here on Quantum Computing Stack Exchange, one thing is yet not clear. In several papers, for illustrating HHL they choose matrix $A$ with convenient eigenvalues of the form $2^k$ such that the rotation angles are like $\frac{v\pi}{2^r}$; and show a full circuit of HHL. It's not always the case. Eigenvalues can be anything. So how can one find the angles for rotation without measuring the eigenvalues?

Does HHL need to be run in two steps? First to get the eigenvalues and then perform the rotation and QPE-inverse?

Answer 1

In the original linear systems algorithm, you may need to execute portions of the algorithm a few times - but this is because postselection can fail, not because we need to separately extract the eigenvalues to determine how much rotation is needed.

---

In particular, one trick in the algorithm includes rotating the flag qubit by an amount indicating whether the inversion happens. Recall also that the probability that the flag register measures a success is based on the condition number $\kappa$ of the underlying matrix $A$ to be inverted. By post-selection this register on being $|\mathrm{success}\rangle$, we can be assured that the input register $|x\rangle$ is in the proper state. If, instead, we measure the flag as $|\mathrm{fail}\rangle$, we can "repeat-until-success."

But even though a whole bunch of repetitions may have to occur because our matrix $A$ is ill-conditioned; we don't need multiple measurements to determine the amount of rotation, as we have the eigenphases $|\lambda_k\rangle$ in superposition after performing the forward Quantum Phase Estimation algorithm. It is from these eignephases that we do the ket-to-scalar rotation of the ancilla flag register.

---

The answer to the question in the body of the OP:

Does HHL need to be run in two steps? First to get the eigenvalues and then perform the rotation and QPE-inverse?

is "yes", but it's more like:

1. First get the eigenvalues with phase estimation
2. Then perform the rotation of the flag register, without measuring any eigenvalues
3. Then measure the flag register, and if $|\mathrm{fail}\rangle$ go back to step 1, else
4. Uncompute the phase estimation with the QPE-inverse.

(Also, don't forget to 0: Prepare the initial state $|b\rangle$ in the first place.)

In any single successful run, each of steps 1, 2, and 4 are done in-situ without multiple measurements of any eigenvalues, because the ket-to-scalar rotation is done in superposition.

Take note also that by the principle of deferred measurement we can measure the flag register in step 3 even after we've uncomputed the phase estimation.