HHL algorithm for linear systems with a real matrix and a real right side

Question

HHL algorithm can be used for solving linear system $A|x\rangle=|b\rangle$. If we put $|b\rangle$ (to be precise its normalized version) into the algorithm and measuring ancilla to be $|1\rangle$ we are left with the state $$ \sum_{i=1}^n \beta_i\frac{C}{\lambda_i}|x_i\rangle, $$ where $|x_i\rangle$ is ith eigenvector of matrix $A$, $\lambda_i$ is respecitve eigenvalue and $\beta_i = \langle b|x_i\rangle$ is ith coordinate of $|b\rangle$ in basis composed of eigenvectors of $A$.

It is known that HHL brings exponential speed-up, however, to get whole state $|x\rangle$ we need to do a tomography which cancels the speed-up completely.

However, let us assume that $A$ is real matrix and $|b\rangle$ is real vector. Since HHL assumes that $A$ is Hermitian, $\lambda_i$ are real. Eigenvalues satisfy relation $A|x_i\rangle = \lambda_i|x_i\rangle$ and since they are real and $A$ is real, it follows that we can find $|x_i\rangle$ to be real (despite that fact that they are orthogonal basis of $\mathbb{C}^n$). As a result, coeficients $\beta_i$ are also real as they are inner product of two real vectors. In the end we are left with real probability amplitudes $\beta_i\frac{C}{\lambda_i}$ in the state above.

This all means that in case of real matrix and real right side, we can simply measure probabilities of possible outcomes in an output register and do not have to employ tomography. Hence, for real systems $Ax=b$, we are able to get whole solution and at the same time the exponential speed-up is preserved.

Is my reasoning right or am I missing something?

Answer 1

If you mean by this sentence:

we are able to get whole solution

to know all the components of vector $x$, then I'm afraid you are wrong.

Given a sparse $N \times N$ matrix with a condition number $\kappa$, HHL algorithm has a runtime $O(\log(N)\kappa ^{2})$. This offers an exponential speedup over the best known classical algorithm, which has a runtime $O(N\kappa )$.

Now $x$ is $N$-dimensional vector, which means we need $O(N)$ measurements to get all its components. That would kill the exponential speedup.

In his paper, "Equation solving by simulation", Andrew Childs said:

Producing a quantum state proportional to $A^{−1}|b〉$ does not, by itself, solve the task at hand. To extract information from a quantum state, we must perform a measurement. Learning all $N$ amplitudes of an $N$-dimensional quantum state requires a number of measurements at least proportional to $N$. Thus, if our goal is to completely reconstruct a solution $x$, there is no hope for a quantum algorithm to offer a significant advantage over classical methods.