# Understanding the filter functions in the HHL algorithm

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.

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$$.
• 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)? – IntegrateThis Jul 31 '19 at 19:30
• 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. – IntegrateThis Aug 4 '19 at 7:05
• 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. – DaftWullie Aug 5 '19 at 8:30