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?

  • $\begingroup$ Aren’t there still an exponential number of $\lambda_i$? $\endgroup$ May 7, 2021 at 12:17
  • $\begingroup$ @Mark S: Exponentials should be eliminated by inverse Fourier in phase estimation. $\endgroup$ May 7, 2021 at 13:22
  • $\begingroup$ What do you mean by "we are able to get whole solution and at the same time the exponential speed-up is preserved?" Are you trying to prepare the state $\vert x\rangle$, or get some expectation? You could always execute the Hamiltonian simulation/perform QPE/calculate the inverse in superposition, and then measure your last register to get $\vert x_i\rangle$ having a large probability. HHL's paper describes a "simple example" on page 2 - therein all of $A$ and $\vert b\rangle$ are real I think. $\endgroup$ May 7, 2021 at 14:36
  • $\begingroup$ There are still $2^n$ different eigenvalues. If you need to know all of them then you'd still need tomography, right? $\endgroup$ May 7, 2021 at 14:51
  • $\begingroup$ @MarkS: I meant that in case we are not sure that the solution of our linear system is real, we have to do complete tomography to take phases into account. In case we know that that the solution is real, we need to measure the output in computational basis only. As a result, we save a resources for doing the tomography and speed-up given by HHL is not hindered. $\endgroup$ May 7, 2021 at 21:58

1 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.

  • $\begingroup$ Thank you, now I see where is flaw in my reasoning. $\endgroup$ May 8, 2021 at 17:27

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.