HHL algorithm -- problem with the outcome of postselection

Question

See edit at the end of the question

---

All the references in this question refer to Quantum algorithm for solving linear systems of equations (Harrow, Hassidim & Lloyd, 2009).

HHL algorithm consists in an application of the quantum phase estimation algorithm (QPE), followed by rotations on an ancilla qubit controlled by the eigenvalues obtained as output of the QPE. The state of the quantum registers after the rotations is $$ \sum_{j=1}^{N} \sum_{k=0}^{T-1} \alpha_{k|j}\beta_j \vert \tilde\lambda_k\rangle \vert u_j \rangle \left( \sqrt{1 - \frac{C^2}{\tilde\lambda_k^2}} \vert 0 \rangle + \frac{C}{\tilde\lambda_k}\vert 1 \rangle \right). $$

Then, the algorithm just uncomputes the first register containing the eigenvalues ($\vert \tilde\lambda_k \rangle$) to give the state $$ \sum_{j=1}^{N}\beta_j \vert u_j \rangle \left( \sqrt{1 - \frac{C^2}{\lambda_j^2}} \vert 0 \rangle + \frac{C}{\lambda_j}\vert 1 \rangle \right). $$

Here, the notation used assumes that the QPE was perfect, i.e. the approximations were the exact values.

The next step of the algorithm is to measure the ancilla qubit (the right-most one in the sum above) and to select the output only when the ancilla qubit is measured to be $\vert 1 \rangle$. This process is also called "post-selection".

The state of the system after post-selecting (i.e. after ensuring that the measurement returned $\vert 1 \rangle$) is written

$$ \frac{1}{D}\sum_{j=1}^{N}\beta_j \frac{C}{\lambda_j} \vert u_j \rangle $$ where $D$ is a normalisation constant (the exact expression can be found in the HHL paper, page 3).

My question: Why is the $\frac{C}{\lambda_j}$ coefficient still in the expression? From what I understood, measuring $$ \left( \sqrt{1 - \frac{C^2}{\lambda_j^2}} \vert 0 \rangle + \frac{C}{\lambda_j}\vert 1 \rangle \right) $$ should output $\vert 0 \rangle$ or $\vert 1 \rangle$ and destroy the amplitudes in front of those states.

---

EDIT: Specifying the question.

Following @glS' answer, here is the updated question:

Why does the post-selection works like described by @glS' answer and not like above?

Answer 1

Your intuition is correct for a single qubit, in that if I measure $$\alpha\vert 0 \rangle + \beta\vert 1 \rangle$$ I would get either $\vert 0 \rangle$ or $\vert 1 \rangle$. But since the qubits are in a large entangled state, the relevant information stored in the ratios of different probabilities is still held fixed, and the $\frac{C}{\lambda_j}$ factors are part of that overall coeffecient on each $\vert u_j \rangle$.

In essence, you can't think of the process as if you are measuring just $$ \sqrt{1 - \frac{C^2}{\lambda_j^2}} \vert 0 \rangle + \frac{C}{\lambda_j}\vert 1 \rangle $$

because then you are ignoring the entanglement of the qubits.

EDIT: To go into more detail. The distiction is between how the one renormalizes after a measurement. So in the beginning if you have a normalized state

$$\alpha\vert a\rangle + \beta\vert b\rangle$$

and you measure it and get $\vert b \rangle$, you are essentially saying that "My measurement returned b, so only states which are consistent with my measurement can exist" and then normalizing the superposition of all of those states. But only $\vert b\rangle$ is consistent and as such you end up with it, and a prefactor of 1 out front.

However imagine an entagled state of the following:

$$\alpha_{00}\vert 00\rangle + \alpha_{01}\vert 01\rangle + \alpha_{10}\vert 10\rangle + \alpha_{11}\vert 11\rangle$$

If I measure the first qubit and get $\vert 0\rangle$, there are two states, $\vert 01\rangle$ and $\vert 00\rangle$ which are consistent, and so your state must be a superposition of those two. In this example that leads to a final state of $$A\left(\alpha_{00}\vert 00\rangle + \alpha_{01}\vert 01\rangle\right)$$

where A is the overall factor to bring the normalization back to 1. The important thing to see is that the ratio between the two remaining probabilities remains constant at $\alpha_{00}/\alpha_{01}$. This ratio would, in the HHL example, be the factors containing different $\frac{C}{\lambda_j}$ values, and as such they must remain. Physically this correspond to the states which are "still viable" being unaltered relative to eachother, which those which have now been ruled out have their probability set to 0.

In terms of more natural language, imagine I give you 4 scenarios and their likelihoods. If I was to specify their relative probabilities, and then rule out 2 of them, it should be natural that the two which have not been ruled out would still have the same relative probability, as whatever extra information has been added was already assumed in order for those scenarios to have been true.

Answer 2

You are half right, in that the $C$ factor is only kept there for (what I assume being) explanatory purposes.

However, the $1/\lambda_j$ factors definitely stays there after postselection. One way to see this is that you can think of those factors as attached to the other registers, so that the state is equivalently written as

$$ \left(\sum_j\beta_j\sqrt{1-\frac{C^2}{\lambda_j^2}} |u_j\rangle\right)|0\rangle + \left(\sum_j\beta_j\frac{C}{\lambda_j} |u_j\rangle\right)|1\rangle.\tag1 $$ Keeping only the term on the right we get a normalised version of $$\sum_j\beta_j\frac{C}{\lambda_j} |u_j\rangle|1\rangle.$$

As an analogy, it's like having the state $$(a|0\rangle+b|1\rangle)|0\rangle.$$ By your reasoning, postselecting on $|0\rangle$ (which here trivially happens with 100% probability) should lead to something like $|0\rangle+|1\rangle$, which is clearly not correct.

Stated in yet another way, you are basically applying the measurement postulate wrong. The state remaining after postselection is the sum of all states with ancilla in the state $|1\rangle$, which results in (1). The factors disappear only if you consider postselection over the ancilla alone, which neglects the fact that the ancilla is entangled with the other registers. Mathematically, you can see it in the fact that the postselected state is the one obtained applying the projector $\mathbb 1\otimes |1\rangle\langle1|$, and renormalizing the result.