Combining Amplitude Amplification with HHL

Question

I'm recently learning about how to apply Grover search techniques to other places. An example I've come across is to amplify the probability of measure a $\lvert 1 \rangle$ of the ancilla qubit in HHL to reduce the expected number of trials to find a solution.

From the original HHL algorithm, I know that after applying QPE, the state of the registers are the following:

$$ \sum_{j=0}^{N-1} b_j \lvert \lambda_j \rangle \lvert u_j \rangle \left( \sqrt{1 - \frac{C^2}{\lambda_j^2}} \lvert 0 \rangle + \frac{C}{\lambda_j} \lvert 1 \rangle \right) $$

To make things simple, we can represent this state using some generic state vector $\psi_0, \psi_1$ and probability $p$.

$$ \Psi = \sqrt{1 - p} \lvert \psi_0 \rangle \lvert 0 \rangle + \sqrt{p} \lvert \psi_1 \rangle \lvert 1 \rangle $$

We need to repeat this $O(\frac{1}{p})$ times in order to measure a $\lvert 1 \rangle$ of the ancilla qubit. However, we can apply Grover-like Amplitude Amplification here to get $O(\frac{1}{\sqrt{p}})$ runtime instead.

In order to do so, we first define some initial state $\psi_{init}$ of the HHL system and a circuit (unitary $Q$) that takes the initial state to the $\Psi$ we got above.

$$ Q \lvert \psi_{init} \rangle = \sqrt{1 - p} \lvert \psi_0 \rangle \lvert 0 \rangle + \sqrt{p} \lvert \psi_1 \rangle \lvert 1 \rangle $$

Once we have this form, we can construct the Grover search oracle $U = I \otimes Z$ (do nothing for the $\psi$, but flip the sign of the ancilla if it's 1). Then, we can also construct the Grover diffusion operator $R = 2 Q \lvert \psi_{init} \rangle \langle \psi_{init} \rvert Q^{\dagger} - I$, which is a reflection along the initial state.

After applying the Grover operators $U, R$ multiple times (to be exact, $O(\frac{1}{\sqrt{p}})$), we can measure a 1 from the ancilla qubit.

However, the thing that I don't quite understand is - in the original HHL we are essentially relying on the $\frac{1}{\lambda_j}$ coefficient to build the inverse of the original $\mathbf{A}$ matrix. If we amplify the probability of measuring $\lvert 1 \rangle$ on the ancilla using Grover, doesn't that mean we also involuntarily destroy the original coefficient because now it's been amplified to something else?

I'm wondering whether my concern is valid, or is there anyway to fix the coefficient skewing after we measure the ancilla qubit?

Thanks!

Answer 1

I think you've effectively answered this yourself in the question! The $1/\lambda_j$ coefficients are all rolled up into the $|\psi_1\rangle$. So you just do amplitude amplification to get the output $\approx |\psi_1\rangle|1\rangle$ which still contains the $1/\lambda_j$ terms because the relevant weights are the relative ones between the different $|\lambda_j\rangle|u_j\rangle$ terms inside $|\psi_1\rangle$.

The only coefficient you lose is something about the overall normalisation (effectively, $C$). But that was never a relevant parameter anyway, because the $C$ was introduced to ensure that $C/\lambda_j<1$ for all $j$ and doesn't tell you anything about the problem itself.