# Solving linear systems represented by NxN matrices with N not power of 2

As far as I have seen, when it comes to solving linear systems of equations it is assumed to have a matrix with a number of rows and columns equal to a power of two, but what if it is not the case?

If for instance I have the equation $Ax=b$ where A is a 4x4 matrix and x and b 4x1 vectors, I expect to find the solution in terms of amplitudes of the 4 basis states considered for the problem. What if instead of 4 there is 5? My idea would be to choose an Hilbert space of smallest dimension that it includes 5 i.e. 8, and then make it so that 3 basis states will have amplitude 0. Is it correct to reason in this way, or am i making problems for nothing?

• that's the way I'd do it. Jul 27 '18 at 9:27

This is indeed a correct way to solve linear systems with dimension not equal to a power of 2. Solve the smallest possible system of dimension 2$^n$ that contains the system you want to solve, and pad the matrices and vectors with zeros to make it the right size. This is because the vector $|b\rangle$ in the HHL algorithm, is a quantum state, which means if we have $n$ qubits, its dimension is naturally 2$^n$.

However, this procedure is not the only way to solve systems with dimension not equal to a power of 2.

Remember you do not have to work with qubits but can also work with other qudits such as qutrits (3-level systems). Then your $|b\rangle$ will have dimension 3$^n$, so you can do for example a 9x9 system without resorting to solving a 16x16 problem involving 4 qubits. The question then becomes whether or not your hardware can more easily perform the algorithm for the case where $|b\rangle$ is represented by 4 qubits, or for the case where it is 2 qutrits.

For a 5x5 matrix, you can use for $|b\rangle$ a qupit with $p=5$. Or you can use 3 qubits and work with an 8x8 matrix. Since there's not likely to be a lot of quantum computing hardware around with qupits, it may be easier to do what you suggest, which is to just use more qubits.

• I actually thought about using qudit rather than qubits, but as you pointed out, I do not know if there is any work related to the implementation of qudits rather than qubits so I put the idea aside!
– FSic
Jul 27 '18 at 9:41
• @F.Siciliano Working with qudits is not a scalable option. Just imagine your matrix has a huge prime dimension! Jul 27 '18 at 22:03