This is a continuation of Quantum algorithm for linear systems of equations (HHL09): Step 1 - Confusion regarding the usage of phase estimation algorithm

Questions (contd.):

Part 2: I'm not exactly sure how many qubits will be needed for the Step 1 of the HHL09.

In Nielsen and Chuang (section 5.2.1, 10th anniversary edition) they say:

Thus to successfully obtain $\varphi$ accurate to $n$-bits with probability of sucess at least $1-\epsilon$ we choose

$$t=n+\lceil { \log(2+\frac{1}{2\epsilon})\rceil}$$

So, say we want an accuracy of $90\%$ i.e. $1-\epsilon = 0.9 \implies \epsilon = 0.1$ and a precision of $3$-bits for $\frac{\lambda_j t}{2\pi}$ or $\lambda_j$ we'd need

$$t = 3 + \lceil { \log_2(2+\frac{1}{2 (0.1)})\rceil} = 3 + 3 = 6$$

Apart from that, since $|b\rangle$ can be represented as a sum of $N$ linearly independent eigenvectors of a $N\times N$ dimensional matrix $A$, we'd need minimum $\lceil{\log_2(N)\rceil}$ qubits to produce a vector space having at least $N$ - dimensions. So, we need $\lceil{\log_2(N)\rceil}$ for the second register.

Now, for the first register we not only $\lceil{\log_2(N)\rceil}$ qubits won't be sufficient to represent the $N$ eigenvalues $|\lambda_j\rangle$, that is because we'll need more bits for representing each $|\lambda_j\rangle$ precisely upto $n$-bits.

I guess we should again use the formula $$n+\lceil { \log(2+\frac{1}{2\epsilon})\rceil}$$ in this case. If we want each eigenvalue $|\lambda_i\rangle$ to be represented with a $3$-bit precision and $90\%$ accuracy then we'd need $6\times \lceil{\log_2(N)\rceil}$ for the first register. Plus, one more qubit which is needed for the ancilla.

So, we should need a total of $(6+1)\lceil{\log_2(N)\rceil}+1$ qubits for Step 1 of the HHL09 algorithm. That's quite a lot!

Say we want to solve a $2\times 2$ linear equation system such that $A$ is Hermitian that itself would require $7\lceil{\log_2(2)\rceil}+1 = 8$ qubits! In case $A$ is not Hermitian we'd need even more qubits. Am I right?

However, in this[$\dagger\dagger$] paper on page 6 they claim that they used the HHL09 algorithm to estimate the pseudoinverse of $A$ which of size ~$200\times 200$. In that paper, $A$ is defined as:

$$A := \begin{pmatrix} W - \gamma \Bbb I_d & P \\ P & 0 \end{pmatrix}$$

where $P$,$W$ and $\Bbb I_d$ are all $d\times d$ matrices.

enter image description here

In the H1N1 related simulated Lloyd et al. have claimed to have made, $d = 100$. And they further claim that they used the HHL09 algorithm to estimate the pseudo-inverse of $A$ (which is of size $200\times 200$). That would need a minimum of $7\lceil{\log_2(200)\rceil}+1 = 7(8)+1 = 57$ qubits to simulate. I have no idea how they could possibly do that using the current quantum computers or quantum computer simulations. As far as I know, IBM Q Experience at present supports ~$15$ qubits (that too it isn't as versatile as their $5$-qubit version).

Am I missing something here? Does this Step 1 actually require a lesser number of qubits than what I have estimated?

[$\dagger\dagger$]: A Quantum Hopfield Neural Network Lloyd et al. (2018)

  • $\begingroup$ @Nelimee That $6$ comes from the formula $t = 3 + \lceil { \log_2(2+\frac{1}{2 (0.1)})\rceil} = 3 + 3 = 6$. It denotes the number of qubits in the "first register" needed to represent each $|\lambda_j\rangle$ or $|\frac{\lambda_j t}{2\pi}\rangle$ to $3$-bits of precision and with $90\%$ accuracy. $\endgroup$ Jun 19, 2018 at 8:47
  • $\begingroup$ While my answer might look trivial now, it actually took me a good 3 days to figure everything out because, among other things, the papers were not clear. I believe I have the right number of qubits now though, and the resulting number makes it quite clear why the authors of this H1N1 paper could easily simulate the required number of qubits (at least for "step 1"). $\endgroup$ Jun 24, 2018 at 5:28

1 Answer 1


Calculation of the inverse of an $N\times N$ matrix can be done by applying HHL with $N$ different $\vec{b}_i$ (specifically, HHL is applied $N$ times, once for each computational basis vector used as the $\vec{b}_i$).

In each case, phase estimation has to be done for an $N \times N$ matrix.

The number of qubits required for phase estimation is written on page 249 of the 10th anniversary edition of N&C:

"The quantum phase estimation procedure uses two registers. The first register contains $t$ qubits."

"The second register [...] contains as many qubits as is necessary to store $|u\rangle$", where $|u\rangle$ is an $N$-dimensional vector.

So you are correct that we would need $6$ qubits for the first register, and $\log N=8$ qubits for the second register.

This is 14 qubits in total to do the phase esitmation part of each HHL iteration involved in calculating the inverse of a matrix. 14 qubits is well within the capabilities of a laptop.

  • $\begingroup$ In your comment, two different meanings of "simulation" are used. "Hamiltonian simulation" is a part of HHL, which is done with qubits, for example in Section 4.2 of this. "What would you use for simulating 14 qubits" refers to a different type of simulation though, which does not use qubits but classical bits, and this is what the authors of the H1N1 paper did. They generated the $2^{14} \times 2^{14}$ matrices (probably in MATLAB using the KRON function which does tensor products) and simulated the QC the way you and I do for 4x4's $\endgroup$ Jun 24, 2018 at 5:57
  • $\begingroup$ If they used IBM, it would say so in the paper. If you search "IBM" nothing comes up. As you read more papers and get more experienced, it will become more and more obvious to you when someone's used a quantum computer or just simulated one. Here they simulated it on a classical computer (perhaps using MATLAB). As for the "problem in my estimation of the number of qubits", I am unfortunately not able to understand what the problem is. I have just given the number of qubits required for phase estimation of a 200 x 200 matrix. N&C say it is t qubits for register 1 and log_2(N) for register 2. $\endgroup$ Jun 24, 2018 at 7:40

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.