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?
$\begingroup$
$\endgroup$
1
-
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 SpinelliCommented Nov 19, 2021 at 20:31
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
To memorialize the observation above, you are right insofar as we never output the entire solution vector $|x\rangle$ as this will take an exponential amount of time. Rather, we always report on some observable $M$ related to $\vec x$. The original paper clarifies this point:
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$ tiself, but in some expectation value $\vec x^T M\vec x$...
Lloyd is fond of telling a story that, when the paper was originally posted on the arXiv, it was picked up by Slashdot and an early commenter/reviewer made the same observation as the OP, which was responded to with a snarky comment to the effect of "if the reviewer had read more than $\log N$ of the paper they would have noticed this!"
This point is emphasized often - see, e.g., Read the Fine Print. A hard part is not so much finding a good observable $M$ of interest; rather, the very hard part is finding a good observable while maintaining the BQP-completeness or at least the exponential advantage of HHL.