2
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ Hi and welcome to QCSE! It would be great if you could include the link where you found that example of applying AA to HHl. It can help people give you a better answer. $\endgroup$
    – epelaaez
    Jul 4 at 0:39
  • 1
    $\begingroup$ Hi - thanks for the quick response! Unfortunately this is from a QC talk that I went to a while ago. There isn't a link but I managed to take some notes about the intuition behind generalizing Grover to work on any initial states and applying it to HHL. I modified the original question with the detailed steps from my notes! Thanks. $\endgroup$ Jul 4 at 5:35
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.