Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
The chapter about solving linear systems in the qiskit textbook describes the last (6th) step of the HHL algorithm as follows
Apply an observable $M$ to calculate $F(x):=\langle x |M|x\rangle$.
How is this observable $M$ chosen? What are the considerations?
The main limitation of the HHL algorithm is that the solution to the linear system $Ax = b$ is obtained as a quantum state $|x\rangle$. Thus, we cannot determine the full vector $x$ directly without running the algorithm an exponential number of times.
However, we can estimate $f(x)$ where $f$ is any function of the solution which can be expressed as $f(x) = \langle x|M|x \rangle$ for a Hermitian operator $M$ which we know how to measure. The HHL algorithm is useful in applications where we know how to cast the quantity of interest as such a function. Designing and implementing an observable $M$ appropriate for a given application is one of the key tasks in using the algorithm.
Example of what can be computed
A fairly general example of a quantity we know how to efficiently estimate from $|x\rangle$ is the overlap $f_\psi(x) = \langle x| \psi\rangle$ of $|x\rangle$ with any quantum state $|\psi\rangle$ for which we know the preparation, e.g. $|\psi\rangle = U|0\rangle$. We can accomplish this using the Hadamard test.
We start with an auxiliary qubit $A$ in the $|+\rangle$ state and a quantum register $R$ in the $|0\dots0\rangle$ state. Using controlled operations we apply $U$ to $R$ if $A$ is $|0\rangle$ and if $A$ is $|1\rangle$ we put $R$ into the state $|x\rangle$ using the HHL algorithm. These operations result in the entangled state
$$ \frac{1}{\sqrt{2}}(|0\rangle|\psi\rangle + |1\rangle|x\rangle).\tag1 $$
Now, in order to estimate the real part of $\langle x|\psi\rangle$ we first apply Hadamard to $A$, obtaining
$$ \frac{1}{2}|0\rangle(|\psi\rangle + |x\rangle) + \frac{1}{2}|1\rangle(|\psi\rangle - |x\rangle) $$
and then we measure $A$ in the computational basis. The output probabilities are
$$ p_0 = \langle\phi|0\rangle\langle 0|\phi\rangle = \frac{1}{4}(\langle\psi|\psi\rangle + \langle\psi|x\rangle + \langle x|\psi\rangle + \langle x|x\rangle) = \frac{1}{2} + \frac{\mathrm{Re} \, \langle x|\psi\rangle}{2} \\ p_1 = \langle\phi|1\rangle\langle 1|\phi\rangle = \frac{1}{4}(\langle\psi|\psi\rangle - \langle\psi|x\rangle - \langle x|\psi\rangle + \langle x|x\rangle) = \frac{1}{2} - \frac{\mathrm{Re} \, \langle x|\psi\rangle}{2}. $$
In order to estimate the imaginary part of $\langle x|\psi\rangle$ we first apply the $S$ gate and then Hadamard to $A$ in $(1)$, obtaining
$$ \frac{1}{2}|0\rangle(|\psi\rangle + i|x\rangle) + \frac{1}{2}|1\rangle(|\psi\rangle - i|x\rangle) $$
and then we measure $A$ in the computational basis. This time, the output probabilities are
$$ p_0 = \langle\phi|0\rangle\langle 0|\phi\rangle = \frac{1}{4}(\langle\psi|\psi\rangle + i\langle\psi|x\rangle - i\langle x|\psi\rangle + \langle x|x\rangle) = \frac{1}{2} + \frac{\mathrm{Im} \, \langle x|\psi\rangle}{2} \\ p_1 = \langle\phi|1\rangle\langle 1|\phi\rangle = \frac{1}{4}(\langle\psi|\psi\rangle - i\langle\psi|x\rangle + i\langle x|\psi\rangle + \langle x|x\rangle) = \frac{1}{2} - \frac{\mathrm{Im} \, \langle x|\psi\rangle}{2}. $$
A simple special case of the above is the efficient estimation of the $k$th component $x_k$ of $x$. Another is the determination whether solutions $x_1$ and $x_2$ to two linear systems $A_1x_1=b_1$ and $A_2x_2=b_2$ are orthogonal.
