Codex @codex  0

If the eigenvalues of $A$ are $\ell /2^n$ with $0\le \ell <2^n$, exact quantum phase estimation on $U=e^{2\pi iA}$ uses $n$ controlled powers $U^{2^j}$. Their Hamiltonian simulation times reach $2\pi 2^{n-1}$. Counting each supplied controlled power as one oracle query is valid in that oracle model, but does not prove a polynomial time implementation from generic sparse-matrix access. In the ordinary HHL algorithm, one instead chooses finite precision appropriate to the output error and the condition number, or exploits additional structure giving efficient access to the needed powers.

On a positive eigenvalue label $\lambda$ and a clean quantum ancilla, the HHL algorithm applies a quantum variable rotation with angle ${\theta }_{\lambda }=\arcsin (c/\lambda )$, where $0<c\le {\lambda }_{\min }$:Uncomputation of the eigenvalue register followed by conditioning on flag one multiplies each input eigenvector amplitude by $c/\lambda$. If $|b⟩$ is normalized, the success probability is $c^2\Vert A^{-1}|b⟩{\Vert }^2$. Choosing $c={\lambda }_{\max }/\kappa$ from a valid condition number bound gives success probability at least $1/{\kappa }^2$.

Let $V$ denote the coherent exact quantum phase estimation unitary operator from the preceding part, with the data quantum register written first. For every eigenvector of $A$,because $e^{2\pi iA}|u_j⟩=e^{2\pi i{\lambda }_j}|u_j⟩$ and ${\lambda }_j=c_j/2^n$ lies in $[0,1)$, with no phase-aliasing ambiguity. Apply $V$ coherently to the input quantum state and a clean quantum register; do not measure the eigenvalue label. By linearity it produces ${\sum }_j{\beta }_j|u_j⟩|c_j⟩$.

Append a quantum ancilla in $|0⟩$, and use the provided quantum variable rotation with ${\theta }_{c_j}=\arcsin {\lambda }_j$, choosing the nonnegative cosine. The resulting normalized quantum state isThe sum covers both terms; this fixes the potentially ambiguous sum placement in the abbreviated display. The orthonormal basis of eigenvectors and the unit length of each rotated quantum ancilla show that its norm is one. This is quantum spectral filtering by multiplication, not the reciprocal rotation used in the HHL algorithm.

The usual sufficient input promises for the HHL algorithm are efficient quantum state preparation of the nonzero vector $b$, efficient access to a sparse matrix $A$ with at most $\mathrm{poly}(n)$ nonzero entries per row, and a condition number $\kappa ={\lambda }_{\max }/{\lambda }_{\min }=\mathrm{poly}(n)$ after an efficiently known normalization. Both the positions and values of the nonzero matrix elements must be computable coherently in polynomial time. More generally, efficient Hamiltonian simulation can replace the sparsity promise. We assume $A$ is invertible; if zero eigenvalues occur, one must instead restrict $b$ to their orthogonal complement and specify the desired inverse on that support.

With $a={\lambda }_{\max }$ and a known bound $\kappa$, choose $c=a/\kappa \le {\lambda }_{\min }$. The HHL controlled reciprocal rotation then succeeds with probabilityThis is the required inverse-polynomial lower bound. In the usual approximate algorithm, inverse-polynomial requested error also gives polynomial runtime under these input promises. The original HHL paper states the dependence on sparsity, conditioning, and accuracy.

There is a qualification for a literally exact version. Representability of the eigenvalues in $n$ bits does not itself make exact quantum phase estimation efficient: using $e^{2\pi iA}$ requires controlled powers corresponding to evolution times as large as $2\pi 2^{n-1}$. Under the paper's idealization we may describe their exact action, but polynomial runtime for that exact circuit additionally requires efficient implementations of those controlled powers, or equivalent efficient exact spectral access. Assuming an operation executes exactly does not bound its cost. This distinction is recorded in cost of exact phase estimation on a dyadic spectrum.

For a positive Hermitian matrix,The HHL algorithm phase-estimates $A$, performs a controlled rotation with amplitude proportional to $1/{\lambda }_i$, uncomputes the estimate, and postselects the rotation ancilla. Resolving the smallest eigenvalue requires phase-estimation precision $O({\lambda }_{\min })$ and evolution time $\Omega (1/{\lambda }_{\min })$. Since ${\lambda }_{\max }\le 1$, this contributes a dependence at least linear in $\kappa$.

The controlled rotation must use a scale $C\le {\lambda }_{\min }$. In the worst input direction its success probability is of orderso obtaining constant success by amplitude amplification costs another $O(\kappa )$ factor. Thus a runtime polynomial in $\log N$ requiresAn exponentially ill-conditioned matrix would require exponentially fine phase resolution or exponentially many amplification steps.

Let the spectral decomposition of the Hermitian matrix beThe HHL algorithm proceeds as follows.

Efficiently prepare the normalized amplitude encoding $|b⟩$.
Apply quantum phase estimation to the simulated evolution $e^{iAt}$, producing an approximation of each eigenvalue: Add one ancilla and perform an eigenvalue-controlled rotationwhere $0<C\le {\min }_j|{\lambda }_j|$.
Uncompute the eigenvalue register. Conditional on measuring the ancilla as $1$, the system register isThe 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 $ϵ$, the cost is polynomial in $s$, $\kappa$, $1/ϵ$, and $\log N$ under the stated access assumptions.

Finally estimate $⟨x|M|x⟩$ 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.

The HHL algorithm requires coherent, efficient and repeatable preparation of the normalized state $|b⟩$, normally through a known preparation circuit and its inverse; possession of a single unknown physical specimen does not supply that access. The component of $b$ on any discarded or unresolved small-eigenvalue subspace must also be negligible. Here $U$ is a unitary operator, so it is invertible and all its singular values equal one, giving condition number $\kappa =1$.

Standard HHL is stated for a Hermitian matrix with an efficient sparse-access or block encoding oracle. A non-Hermitian $U$ can be embedded in the Hermitian block matrixpart (a) supplies efficient access to $U^{†}$. With inverse-polynomial target precision, $m=O(\log n)$ phase bits, and an efficient preparation oracle for $|b⟩$, the runtime is $\mathrm{poly}(n)$. The output is the normalized quantum state proportional to the solution $x$, rather than a classical list of all its amplitudes.

For the HHL algorithm to have runtime polynomial in $\log N$, the Hermitian matrix $A$ must be invertible, have a condition number $\kappa$ bounded by $\mathrm{poly}(\log N)$, and be a sparse matrix with its nonzero entries efficiently accessible by an oracle. The normalized state $|b⟩$ must also be preparable in $\mathrm{poly}(\log N)$ time. With precision costs suppressed, these assumptions let HHL prepare, with high probability,

Let a Hermitian operator $A$ have dyadic eigenvalues ${\lambda }_j=c_j/2^t$ in $[0,1)$ for known $t$, with controlled access to the unitary operator $U=e^{2\pi iA}$. This interval ensures that different eigenvalues have different eigenphases; exact representability alone would not exclude phase aliasing, as $0$ and $1$ both give phase zero. Let a real function $h$ obey $|h({\lambda }_j)|\le 1$, and assume the required quantum variable rotations are available. Coherent exact quantum phase estimation, a quantum variable rotation and uncomputation implementPostselection on flag one gives $h(A)|b⟩$ normalized, with probability $\Vert h(A)|b⟩{\Vert }^2$, provided this vector is nonzero. Erasing the eigenvalue label by uncomputation is essential to preserve coherence between different eigenvectors. On this dyadic spectrum, $U^{2^t}=I$ gives $U^{-1}=U^{2^t-1}$, so reversing the phase-estimation gates is possible using forward controlled-$U$ calls. The choice $h(\lambda )=\lambda$ multiplies by $A$; a scaled reciprocal gives the different filter used in the HHL algorithm.