HHL Algorithm: How to compute the signs of the solution vector

Question

Let us assume we have used the HHL algorithm to approximately prepare $|x\rangle$, where $|x\rangle$ is a normalized quantum state corresponding to $\vec{x}$, the solution of a system of linear equations.

Is there any way we can recover information on the signs of $\vec{x}$?

So far, I can think of no way that doesn't include classically solving for $\vec{x}$ and extracting the relevant signs from $\vec{x}$, which obviously defeats the purpose of using HHL in the first place. Is there maybe some efficient classical way of determining the signs using $A$ and $b$ that takes at most $O(\log N)$ steps and therefore doesn't destroy the computational advantage of HHL?

Answer 1

Let us denote: $$|x\rangle=\sum_ix_i|i\rangle$$ If it was possible to learn the sign of each $x_i$, then you would have a way to distinguish $|x\rangle$ and $-|x\rangle$. Since these states only differ by a global phase, this is not possible.

There may be an algorithm that allows you to learn the relative signs between given $x_i$ and $x_j$, but learning them all would of course take at least $O(N)$ operations.

HHL is more to be seen as a routine in a bigger quantum algorithm, like evaluating $\langle x|M|x\rangle$ for instance, rather than an actual solver for systems of equations.