Understanding the filter functions in the HHL algorithm

Question

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.

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