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:


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.


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

  • $\begingroup$ Welcome to QCSE. To be clear you want to know $n_c$ in Figure 5 of that paper? In general the bigger $c$ is the better precision on the quantum phase estimation (QPE), but also the longer you need to simulate your Hermitian matrix, which usually means that it's polylogarithmic in $n_i$ in Figure 5. The QPE includes a number of controlled unitaries that need to repeated up to $2^{n_c}$ times. $\endgroup$ Commented Jul 11, 2023 at 13:50
  • $\begingroup$ Thanks, I would indeed like to be able to know how they compute $n_c$ to have a better understanding of the relationship between the precision, the matrix properties and $n_c$. I do get that when you improve the number $n_c$ of qubits you improve precision, but augment the number of gates. However i'm not sure that QPE requires up to $2^{n_c}$ gates I would have said that it goes up to $\frac{n_c(n_c+1)}{2}$ based on the number of gates in QFT <colibritd.com/getting-to-know-quantum-fourier-transform> and in QPE before. Maybe I misunderstood your statement or am wrong. $\endgroup$ Commented Jul 11, 2023 at 14:11

1 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:

Figure 5 of Lapworth

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$. QPE circuit from Wikipedia

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$.


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.