Isn't the exponential speedup and the output $\langle x|M|x\rangle$ in contradiction in HHL algorithm? How can we print the solution vector $|x\rangle$ without losing the exponential speedup?
-
7$\begingroup$ The beginning of page 2 of the paper provides the answer. "Clearly, to read out all the components of $\vec x$ would require one to perform the procedure at least $N$ times. However, often one is interested not in $\vec x$ itself, but in some expectation calue $\vec x^T M\vec x$, where $M$ is some linear operator (our procedure also accommodates nonlinear operators as described below)." $\endgroup$– Mark SNov 19, 2021 at 20:31