# Quantum algorithm for linear systems of equations (HHL09): Step 1 - Number of qubits needed

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

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)

• @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. – Sanchayan Dutta Jun 19 '18 at 8:47
• 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"). – user1271772 Jun 24 '18 at 5:28

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.

• I do not have much experience with simulations other than playing a bit with the IBM Quantum Experience. What would you use for simulating 14 qubits ? Till now, I've never seen the circuit model for larger than $4\times 4$ matrices. Hamiltonian simulation looks like the hardest part of HHL. – Sanchayan Dutta Jun 24 '18 at 5:40
• 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 – user1271772 Jun 24 '18 at 5:57
• Yes, I'm aware that Hamiltonian simulation is a part of HHL. However, I was wondering whether they used an actual quantum computer like the IBM 16 qubit or IBM 20 qubit version. That KRON function in MATLAB does sound interesting (but it is classical), but I was thinking of the possibility of doing it in the IBM 16 qubit one (which unfortunately doesn't have all the necessary gates), and thus, we'd need to approximate the gates (I'm not completely sure how). – Sanchayan Dutta Jun 24 '18 at 6:05
• Moreover, I think there's another problem with your estimation of the number of qubits: "Here the problem comes from the fixed precision versus the non-fixed dimension N. As he has a fixed precision, $3$ (or $6$) qubits are sufficient to encode the eigenvalues to the given precision, but he might have more than $2^3$ (or $2^6$) eigenvalues" (see the discussion in chat related to this). – Sanchayan Dutta Jun 24 '18 at 6:07
• 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. – user1271772 Jun 24 '18 at 7:40