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?


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

  • $\begingroup$ Thank you for the anwer! So would you say there's not just no way to learn the signs based on $|x\rangle$, but also no way to learn it from "other parts of the circuit" (I'm thinking of how the normalization constant can be estimated by measuring the Ancilla qubit)? $\endgroup$ Commented Mar 4, 2023 at 21:26
  • $\begingroup$ @DominikVereno If I'm not mistaken, the ancilla will only give you information on the norm of $x$. If you think about it, there's no reason for the ancilla to contain anything else: the relative phases are already encoded in $|x\rangle$. I may be mistaken, but I don't think the ancilla can be of any use here $\endgroup$
    – Tristan Nemoz
    Commented Mar 4, 2023 at 22:40
  • $\begingroup$ I wasn't talking about the ancilla in particular, but rather as an example of a "source of information" other than the result qubits. To be honest, I was mainly hoping to have overlooked something, some source of retrieving sign information. $\endgroup$ Commented Mar 7, 2023 at 21:03

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.