  We develop a novel approach for efficiently applying variational quantum
linear solver (VQLS) in context of structured sparse matrices. Such matrices
frequently arise during numerical solution of partial differential equations
which are ubiquitous in science and engineering. Conventionally, Pauli basis is
used for linear combination of unitary (LCU) decomposition of the underlying
matrix to facilitate the evaluation the global/local VQLS cost functions.
However, Pauli basis in worst case can result in number of LCU terms that scale
quadratically with respect to the matrix size. We show that by using an
alternate basis one can better exploit the sparsity and underlying structure of
matrix leading to number of tensor product terms which scale only
logarithmically with respect to the matrix size. Given this new basis is
comprised of non-unitary operators, we employ the concept of unitary completion
to design efficient quantum circuits for computing the global/local VQLS cost
functions. We compare our approach with other related concepts in the
literature including unitary dilation and measurement in Bell basis, and
discuss its pros/cons while using VQLS applied to Heat equation as an example.
