HHL algorithm, how to decide n qubits to prepare for expressing eigenvalue of A?

Question

I am trying to understand the HHL algorithm for solving linear systems of equations (Harrow, Hassidim, Lloyd; presented in arXiv:0811.3171 and explained on page 17 of arXiv:1804.03719). By reading some papers, I think I got rough idea but there are many things I still do not understand. Let me ask some.

When applying Quantum Phase Estimation, in page 49 of the same article, it says "Prepare $n$ register qubits in $|0\rangle^{\bigotimes n}$ state with the vector $|b\rangle$", so that, by applying QPE to $|b\rangle |0\rangle^{\bigotimes n}$, we can get $\sum_j \beta_j |u_j\rangle |\lambda_j\rangle$.

And $|\lambda_j\rangle$ is the $j^{th}$ eigenvalue of matrix $A$ and $0 < \lambda_j < 1$, and $\left|u_j\right>$ is the corresponding eigenvector.

I also understand $|\lambda_j\rangle$ is the binary representation for fraction of $j^{th}$ eigenvalue of $A$. (i.e. $\left|01\right>$ for $\left|\lambda\right>=1/4$)

My questions are,

Q1: How to decide $n$, how many qubits to prepare? I assume it is related to the precision of expressing the eigenvalue, but not sure.

Q2: What to do if $\lambda_j$ of $A$ is $≤ 0$ or $≥ 1$?

Answer 1

The number $n$ decides the size of the register to be used for phase estimation, which in turn determines the accuracy. If you knew your eigenvalues (for a unitary) were a subset of the ${2^n}^{th}$ roots of unity, $e^{2\pi i m/2^n}$, then using $n$ bits is guaranteed to give you the exact answer. Assuming you don't have exactly this guarantee, then you can think of the phase estimation as returning the best $n$-bit approximation of those values, i.e. $\phi/(2\pi)$, where the eigenvalue is $e^{i\phi}$, would be approximated to within $1/2^{n+1}$ (with caveats about the probability of this happening, which we can lower-bound by $4/\pi^2$, and can improve further by using a slightly larger $n$).

If memory serves, what you want to do to prepare $A$ is two things (I'm leaving out the connection between implementing a non-unitary $A$ and the unitaries required for phase estimation, since you didn't ask):

• Add enough $\mathbb{I}$ so that $A^{(1)}=A^{(0)}+B\mathbb{I}$ is non-negative (i.e. all $\lambda_i\geq 0$)

• Rescale to $A=\epsilon A^{(1)}$ so that the maximum eigenvalue is less than 1.

These operations don't change the eigenvectors, and change the eigenvalues by known amounts that you can compensate for later, $\lambda_i=\epsilon(\lambda_i^{(0)}+B)$. You might worry that this rescaling requires you to know the very information that you're trying to calculate. However, it's easy to make at least some crude estimates of the limits of the spectrum via, for example, Gershgorin's Circle Theorem.

Actually, you could probably get away with just a rescaling (and no $\mathbb{I}$) if you ensure all eigenvalues are in the range $-1/2$ to $1/2$, due to the periodicity of the Quantum Fourier Transfer, but making use of it gives you the maximum opportunity to spread all the eigenvalues out as much as possible, and hence to get as accurate an estimate on them as possible.