How to recover the normalization constant of the HHL solution

Question

HHL solves the linear equation $Ax=b$ by the quantum state $|x\rangle=A^{-1} |b\rangle$. However, the quantum state $|x\rangle$ is normalized and thus diffs a normalization constant from the solution vector $x$. My question is how to recover the missing normalization constant?

Especially, HHL is supposed to be applied to a scenario which does not need $x$ itself by some number $x^T M x$. In this case, normalization constant matters to compute $x^TMx$ by $\langle x|M|x\rangle$.

Answer 1

I'm not sure of the formal answer to your question, but for simulation purposes, this approach worked for me:

1. Create a function that scales a matrix down by its largest eigenvalue if this eigenvalue is greater than $2\pi$. This is so QPEs "angle truncation" doesn't cause HHL to output an incorrect answer.
2. Scale the input matrix A by the constant returned by this function.
3. Perform HHL
4. Scale up the output vector by the same constant and return the result.

Edit:

To extract the unnormalized vector $x$ from $\left| x \right\rangle$ (a normalized quantum state) you would have to do full state tomography, which is a bigger problem than extracting the normalization constant. To extract the normalization constant, notice in the HHL paper that the normalization constant that we do not know "pops out" after measuring an ancilla qubit in a success basis state. So to $\textit{estimate}$ the normalization we could do HHL over and over again and take the number of times we measure success on the ancilla qubit divided by the total number of runs. Alternatively, we know the vector $b$ is normalized to make $\left| b \right\rangle$ and we know this normalization constant. Then $A^{-1}$ is applied to $\left| b \right\rangle$, during which, the known normalization constant is multiplied by another constant that is unknown. These constants together make up the overall normalization constant.

Answer 2

HHL is solving the problem $x^\prime = A^{-1}\frac{b}{||b||}$, so your solution will always be normalised as $x^\prime=x/||b||$. You always have access to this information because HHL is a probabilistic algorithm, and the probability of success is $||x^\prime||=||x||/||b||$.

It can happen that your solution is normalised by other factors, but these will then depend on your algorithm and it should be possible to calculate them a priori. E.g. in the rotation step, if you perform the operation $$ |\lambda\rangle|0\rangle\mapsto|\lambda\rangle(\sqrt{1-\frac{C^2}{\lambda^2}}|0\rangle+\frac{C}{\lambda}|1\rangle), $$ then your solution will become $x^\prime=\frac{Cx}{||b||}$.