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 S
    Nov 19 '21 at 20:31

Your Answer

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

Browse other questions tagged or ask your own question.