4
$\begingroup$

In the HHL paper the authors have mentioned that if the user wants to get all the components of vector $\vec{x}$, one needs to run the process at least $N$ times, where $N$ is the dimension of the matrix $A$. This point is not clear. How could just running the process at least $N$ times give the result out? If for example, I had a $2 \times 2$ matrix, would running the process at least $2$ times give me all the components?

I know I'm lacking some concepts here,any help would be very much appreciated.

Thank you so much.

$\endgroup$

1 Answer 1

4
$\begingroup$

The HHL algorithm is not intended for finding the exact vector $\vec{x}$ which is the solution vector to the equation $A\vec{x} = \vec{b}$ (while $A$ and $\vec{b}$ are given) - But rather it is intended for finding the expectation value $\langle x|M|x\rangle$ - I.e the result of applying some operator $M$ upon $|x\rangle$, while $|x\rangle$ is the quantum representation of the solution vector $\vec{x}$.

Generally speaking, the only information we can get about a quantum mechanical system is provided by a measurement that causes a collapsion of the wave function and returns one single value. The value being measured is due to a probability that is determined by the entries of the statevector (each entry is a probability amplitude to measure a corresponding basis state). Hence, given a quantum system described by a statevector $|x\rangle$ - For figuring the entries of $|x\rangle$ one needs to measure the system many times and then it can be infered from the probability distribution of the results what are the approximate entries of $|x\rangle$.


In the HHL algorithm original paper indeed it's written:

This procedure yields a quantum-mechanical representation $|x\rangle$ of the desired vector $\vec{x}$. Clearly, to read out all the components of $\vec{x}$ would require one to perform the procedure at least $N$ times.

In light of the explanation provided above, I think that the author's intention here is about infering $|x\rangle$ from a probability distribution of measuring the system at least $N$ times.

For example, let $|x\rangle = \frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$, then if we measure the system $2$ times and we get one $|0\rangle$ and one $|1\rangle$ - We can crudly infer that $|x\rangle = \frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$. Of course that we need more measurements (but still $O(N)$) in order to get a reliable approximation for $|x\rangle$. I think that by stating that at least $N$ performings of the procedure would be needed the author meant that $O(N)$ iterations would be needed.

However, and as being explained at first - There is no point in repeating the procedure $O(N)$ times for approximating $\vec{x}$, because classically we can find $\vec{x}$ in roughly $O(N)$ repetitions (it's $O(Nsk\ log(\frac{1}{\epsilon}))$ actually).


Edit: I have approached to Avinatan Hassidim (one of the authors of HHL) in order to verify my conjecture presented above. He confirmed it. I am attaching the correspondece for the sake of complecity.

My question:

In the HHL paper the following statement appears:

This procedure yields a quantum-mechanical representation $|x⟩$ of the desired vector $\vec{x}$. Clearly, to read out all the components of $\vec{x}$ would require one to perform the procedure at least $N$ times.

It's well understood that the HHL algorithm is not intended for finding $\vec{x}$ (or $|x⟩$) exactly but rather to estimate $⟨x|M|x⟩$.

However, what is the exact meaning of the above quote? I assumed that the intention behind this statement is that if we run the procedure $O(N)$ times, then we might get a reliable probability distribution of the results that allows a decent approximation of $|x⟩$. But of course many iterations (still $O(N)$, but many) are needed for a reliable estimation of $|x⟩$, while $N$ iterations only clearly won't allow a good approximation for $|x⟩$.

Is that indeed the case? Or am I missing something? Is by stating that at least $N$ iterations over the procedure are required the intention is for $O(N)$ iterations?

Avinatan Hassidim's answer:

You are right. We were stating a clear lower bound. The upper bound is $O(N\ log\ N)$ (coupon collector).

$\endgroup$
2
  • $\begingroup$ Thanks, @Ohad for your response. I got it, so they just mentioned it to give us the minimum runs required but as you also mentioned one can only infer the entries of state vector from probability distribution which results from running the system multiple times. Anyway, this is also not the main motivation of the HHL algorithm to get the entries of state vector $|x>$ out. $\endgroup$ Sep 7, 2022 at 17:58
  • $\begingroup$ Yes, I think that the authors meant that in order to get an approximation for $|x\rangle$ (and therefore also for $\vec{x}$) it takes $O(N)$ runnings of the algorithm. As said, it’s pointless to do so because it provides no speedup over the classical case. The point is by applying an operator $M$ upon $|x\rangle$ - We get result for that exponentially faster compared to the classical best method of solving the linear equations system and then apply $M$ on the resulted vector $\vec{x}$. $\endgroup$
    – Ohad
    Sep 7, 2022 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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