Determining the number of qubits to represent the eigenvalues in HHL algorithm?

Question

I am trying to understand how well the HHL algorithm would scale. Therefore my first inquiry is how the number of qubits scale with the size of the problem ie the size of the Matrix A in the linear system Ax = b.
I have found an article that gives in a table how many qubits are required based on the parameters of the problem for an application in physics:

https://doi.org/10.48550/arXiv.2209.07964

The first number of qubits can easily be obtained by taking a number of state qubits equal to $\left\lceil \log_2{(matrix\;rank)} \right\rceil +1$ $\\\\$ (the plus one is because we use $\begin{pmatrix} 0 & A \\ A^{\dagger} & 0\\ \end{pmatrix}$ as the matrix to ensure it is hermitian). And the last number is just the ancilla qubit. However I don't know how to compute the second number which represent the number of qubits to represent the eigenvalue. It seems to be $\simeq $$\left\lceil \log_2{(\frac{1}{|\lambda_{min}|})} \right\rceil$ but it doesn't fit for the last line of the table.

Question

How should I compute the number of qubits needed to represent the eigenvalues of the matrix ?

Answer 1

It appears that you wish to know how many ancillary qubits $n_c$ are needed or used in Figure 5 of the paper by Lapworth, which implements the HHL algorithm and is reproduced below for convenience:

In general, as $n_c$ increases more precision is obtained with respect to the eigenvalues (eigenphases) stored therein. You are correct that the quantum phase estimation (QPE) algorithm uses an inverse quantum Fourier transform (iQFT) on these $n_c$ qubits; and yes, this iQFT uses $\frac{n_c(n_c+1)}{2}$ or so gates.

Before the iQFT however, the quantum phase estimation performs multiple rounds of Hamiltonian simulation to simulate a unitary $U=\exp(-i H t)$, where $H$ is the hermitian version of your matrix $A$.

Referring to the circuit from the English-language Wikipedia article on the QPE algorithm, you can see that there's a plurality of controlled-$U$ gates that store the phases into the ancilla register. Furthermore there is a controlled gate $U^{2^{n-1}}$ in the most significant qubit of the ancilla register - this is usually performed with $2^{n-1}$ different controlled-Hamiltonian simulations, controlled with the most significant ancilla qubit. These ancilla qubits are the registers upon which the $\mathcal{QFT}^{-1}_{2^n}$ is performed.

Indeed, we can compare Wikipedia's registers to Lapworth - $n$ in Wikipedia corresponds to $n_c$ in Lapworth, while $m$ in Wikipedia corresponds to $n_i$ in Lapworth. That is, the QPE in Figure 5 of Lapworth includes $n_c$ clock qubits and the $n_i$ input qubits, which is the $n$ clock qubits and the $m$ input qubits in Wikipedia, respectively.

Thus, to answer your question you don't need (or really want to have) $n_c$ be much bigger than polylogarithmic in $n_i$ for the HHL algorithm, because if $n_c$ were that much bigger, you would need to do an exponentially longer number of controlled unitaries to simulate $H$ or $A$.