I am continuing my studies of the HHL algorithm here. In applying the controlled rotation conditioned on the eigenvalues of the matrix, the authors use so called filter functions in order to filter out the portion of $|b \rangle$ that is in the ill-conditioned subspace of subspace of $A$, which the authors define as the eigenvalues $\lambda_j\geq \frac{1}{\kappa}$ where $\kappa$ is the condition number of the matrix defined to be the ratio $\lambda_{max} / \lambda_{min}$.

Consider a controlled rotation, say controlled on state $|a \rangle |0 \rangle $ with angle $\theta$ where $a \in \{0,1\} $ where $R_{\theta} |a \rangle |0 \rangle = |a \rangle (cos(\theta) |0 \rangle + sin (\theta) |1 \rangle$) if $a=1$, and which does nothing otherwise. In this case we have that the 1-bit ancilla register is what is being "rotated".

But in the HHL algorithm, we are left with a register S of the form $|h(\tilde{\lambda_j}) \rangle : = \sqrt{1-f(\tilde{\lambda_k})^2 - g(\tilde{\lambda_k})^2} |$ nothing $\rangle + f(\tilde{\lambda_k})|$well$\rangle$ + $g(\tilde{\lambda_k})|$ill$\rangle$, where

"nothing" corresponds to no inversion taking place

"well" correspondins to a successful inversion

"ill" indicates that part of $|b \rangle$ is in the ill-conditioned subspace of $A$. The discussion section describes that formally we are transforming $|b \rangle$ to the state $\sum_{j, \lambda_j < 1 / \kappa} \lambda_j^{-1}\beta_j |u_j \rangle | well \rangle + \sum_{j, \lambda_j \geq 1 / \kappa} \beta_j |u_j \rangle | ill \rangle$

The authors describe the register $S$ as being of dimension $3$. I'm not sure why the dimension is $3$ and not $1$ as in my above description of a controlled rotation.


1 Answer 1


Note that the ancilla qubit in your example has dimension 2, not 1, because it goes into a superposition of 2 basis states, $|0\rangle$ and $|1\rangle$.

For the HHL algorithm, you need an ancilla capable of recording the three options "nothing", "well" and "ill". As such, you need a Hilbert space of dimension 3 (also called a qutrit).

Now, it is true that in the equation you've written, it appears as if they're only using a two-dimension system spanned by "well" and "ill", but that's just because you're only taking a snapshot of the process at a particular moment (presumably when you've post-selected on that ancilla not being in the "nothing" state, since that's part of the repeat until success procedure).

  • $\begingroup$ Ah I see now I was confusing dimension with number of qubits required to represent something. As a side question, is there a discussion anywhere of how to implement this transformation alongside the fliter functions since it is now different than a strict controlled rotation. I.e. How is $g(\tilde{\lambda_j})|ill \rangle$ achieved (gates and such)? $\endgroup$ Jul 31, 2019 at 19:30
  • $\begingroup$ @IntegrateThis I don't know if there's an explicit discussion (I've not looked for one). I think it's generally just left as the techniques required are very similar to the techniques used throughout the rest of the paper. $\endgroup$
    – DaftWullie
    Aug 1, 2019 at 6:36
  • $\begingroup$ I will accept this answer, although I am not sure what you mean when you say the techniques required are similar to other techinques. I see discussed the notion of a controlled rotation, and the proof of why $| h( \lambda_k} \rangle$ is Lipschitz, and I believe the authors admit that these functions are not unitary, but how they are implemented seeing how the eigenvalues are not known (as they are not measured) seems mysterious to me. $\endgroup$ Aug 4, 2019 at 7:05
  • $\begingroup$ The eigenvalues might not be precisely known, but they are estimated, so you have the best $t$-bit approximation of the eigenvalue (at least with high probability). So you might, for example, mark any eigenvalues that have come out as $p\pi/2^t$ for some small $p$ as "ill". Just because you haven't performed the measurement after the phase estimation doesn't mean that, internally, you can't access the values. $\endgroup$
    – DaftWullie
    Aug 5, 2019 at 8:30

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.