HHL for non power of 2 matrix

Question

I'm trying to see how HHL does on a series of matrices coming from a linear problem I'm interested in. These matrices are always square, real, and symmteric. They are not, however, very often exactly a power of 2. In Qiskit's old HHL implementation, they had a class parameter truncate_powerdim that seemed to handle this case, but no such option exists in the current source.

As an example, let's consider the case of a 15x15 matrix. Then, of the $2^4$ possible qubit states, one of them is not a valid dimension of our computation. Since we get to construct our mapping to qubits, let's just say that the 1111 state is the one we want to ignore. It seems silly then, to do the standard QPE starting routine of putting an arbitrary superposition over 16 states rather than the 15 states we know will actually be valid. It's not at all obvious to me how to produce a uniform distribution over a (non-power of 2) subset of states. Does anyone have any suggestion for how to do this in Qiskit?

Also, for the matrix and vector defining the linear system, is it a valid operation to just pad them with zeros corresponding to states outside of the dimension of the system?

Ultimately, I'm hoping for a solution that doesn't involve too much re-inventing the wheel and that uses the available resources in qiskit or other qSDKs.

Thanks for the help!

Answer 1

Assume that your system of linear equations is of $m$ equations in $m$ variables, $x_1, x_2, \ldots, x_m$ where $2^{n-1} < m < 2^n$. One solution to make the system compatible with HHL algorithm requirements is to add extra $2^n - m$ equations:

$x_j = 0$, where $j=m+1, \ldots, 2^n$

That is, we expand the matrix to become $2^n \times 2^n$ with ones on the diagonal and zeros on the off-diagonal and expand the vector with zeros accordingly.

This solution was available in old Qiskit's implementation of HHL via expand_to_powerdim method and you can find the code here.