= Solution
Let the <spectral decomposition> of the Hermitian matrix be
$$
A=\sum_j\lambda_j|u_j\rangle\langle u_j|,
\qquad
|b\rangle=\sum_j\beta_j|u_j\rangle.
$$
The <HHL algorithm> proceeds as follows.
<# Efficiently> prepare the normalized amplitude encoding $|b\rangle$.
<# Apply> <quantum phase estimation> to the simulated evolution $e^{iAt}$, producing an approximation of each eigenvalue:
$$
\sum_j\beta_j|u_j\rangle|\widetilde\lambda_j\rangle.
$$
<# Add> one ancilla and perform an eigenvalue-controlled rotation
$$
|\widetilde\lambda_j\rangle|0\rangle
\longmapsto
|\widetilde\lambda_j\rangle
\left(\sqrt{1-\frac{C^2}{\widetilde\lambda_j^2}}|0\rangle
+\frac{C}{\widetilde\lambda_j}|1\rangle\right),
$$
where $0<C\leq\min_j|\lambda_j|$.
<# Uncompute> the eigenvalue register. Conditional on measuring the ancilla as $1$, the system register is
$$
|x\rangle=
\frac{A^{-1}|b\rangle}{\|A^{-1}|b\rangle\|}
=\frac{\sum_j\beta_j\lambda_j^{-1}|u_j\rangle}
{\sqrt{\sum_j|\beta_j|^2|\lambda_j|^{-2}}}.
$$
The postselection probability can be increased with <amplitude amplification>.
The ingredients used here are efficient sparse <Hamiltonian simulation> of $e^{iAt}$ and <quantum phase estimation>, which converts an eigenphase of that evolution into a binary approximation of $\lambda_j$. For sparsity $s$, condition number $\kappa$, and error $\epsilon$, the cost is polynomial in $s$, $\kappa$, $1/\epsilon$, and $\log N$ under the stated access assumptions.
Finally estimate $\langle x|M|x\rangle$ by repeated measurement of an efficient observable decomposition of $M$, or by a <Hadamard test> when $M$ is unitary. A general efficiently block-encoded Hermitian $M$ can similarly be measured through its block encoding. Repetition and a <concentration inequality> give additive sampling error $O(1/\sqrt R)$ after $R$ independent preparations.
Back to article page
