Using QUBO to solve Linear systems

[NicoRenaud]

We can use Quantum Anealler to solve linear systems. We first need to recast the problem as a QUBO and then implement it on the the QA architecture.

Some work has been done in that area already

• Solving Linear System as QUBO : https://arxiv.org/pdf/1809.07649.pdf
• Solving Linear systems as QUBO : https://agenda.infn.it/event/17130/contributions/106935/attachments/69411/86244/Presentazione_Ottaviani.pdf
• Solving Least Square as QUBO : https://www.nature.com/articles/s41598-021-89461-4.pdf
• Using Adiabatic QC for least square and matrix factorization : https://scipost.org/preprints/scipost_202106_00008v1/

[PabRod]

Quick and dirty implementation in Python:

def non_square_solver(A, b):
    """ Solve an overdetermined system 

    The system Ax = b, where A is a non-square matrix,
    can be turned into a square-matrix problem by

    A^t A x = A^t b

    Q x = c

    x = Q^{-1} c
    """
    At = np.transpose(A)
    Q = np.matmul(At, A)
    c = np.matmul(At, b)

    Qinv = np.linalg.inv(Q)

    return np.matmul(Qinv, c)

[NicoRenaud]

we have it implemented and its also part of qalcore now