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?

  • 2
    that's the way I'd do it. – DaftWullie Jul 27 at 9:27
up vote 6 down vote accepted

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.

  • 1
    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 at 9:41
  • @F.Siciliano Working with qudits is not a scalable option. Just imagine your matrix has a huge prime dimension! – Norbert Schuch Jul 27 at 22:03

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.