In HHL, vector $\vec{b}$ is assumed to be decomposed in the eigenbasis {$u_i$}$_{i=1}^n$ of a Hermitian matrix $A$. However, as we do not calculate explicitly the eigenvectors $u_i$ in course of the algorithm, how do we load $\vec{b}$ into the quantum computer (using amplitude encoding), if we don't even know the $b_i$'s?


1 Answer 1


We do explicitly calculate $A$'s eigendecomposition of $\vec b$, but in superposition. This is the quantum phase estimation portion of HHL.

You can provide your initial vector $\vec b$ in the computational basis (e.g., in the $|0\rangle,|1\rangle$ basis), and as long as you can simulate $A$ as a Hamiltonian you can perform controlled-versions of this simulation, with the controlling qubits being part of a $k$-qubit ancilla register. Your initial vector $\vec b$ can be anything and need not be prepared in any eigenbasis of $A$, because the QPE is what does the decomposition.

After doing the Hamiltonian simulations $2^k-1$ times, an inverse-QFT on the $k$ qubits stores the phases (eigenvalues) of $e^{-iAt}$ into the ancilla register, with probability amplitudes given by the amount of overlap to the eigendecomposition of $\vec b$. This explicitly calculates the eigenvalues of $A$ and “writes” $\vec b$ into this eigenbasis, but in superposition and indexed by the phases $|k\rangle$.

The rest of the algorithm is eigenvalue surgery on these phases (and uncomputation and post-selection if needed).

  • $\begingroup$ Ok, so vector $\vec{b}$ can be loaded in the computational basis, the decomposition in the eigenbasis of $A$ happens during the algorithm. Can you direct me to places, where it is explained, what are the options used to load $\vec{b}$? One needs to understand how amplitude encoding is being done, what is the error of this operation, right? $\endgroup$
    – wondering
    Jun 27, 2023 at 15:05
  • $\begingroup$ @wondering I don't know of any one source that could explain how to prepare $\vec b$ as $|b\rangle$ efficiently, but yes that needs to be done and would have error associated with it perhaps, if $|b\rangle$ cannot be prepared error-free. You could for example adiabatically prepare $|b\rangle$. I guess the key-words to search for are "state preparation" or something. $\endgroup$ Jun 27, 2023 at 20:16

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.