  Solving linear systems is of great importance in numerous fields. In
particular, circulant systems are especially valuable for efficiently finding
numerical solutions to physics-related differential equations. Current quantum
algorithms like HHL or variational methods are either resource-intensive or may
fail to find a solution. We present an efficient algorithm based on convex
optimization of combinations of quantum states to solve for banded circulant
linear systems whose non-zero terms are within distance $K$ of the main
diagonal. By decomposing banded circulant matrices into cyclic permutations,
our approach produces approximate solutions to such systems with a combination
of quantum states linear to $K$, significantly improving over previous
convergence guarantees, which require quantum states exponential to $K$. We
propose a hybrid quantum-classical algorithm using the Hadamard test and the
quantum Fourier transform as subroutines and show its PromiseBQP-hardness.
Additionally, we introduce a quantum-inspired algorithm with similar
performance given sample and query access. We validate our methods with
classical simulations and actual IBM quantum computer implementation,
showcasing their applicability for solving physical problems such as heat
transfer.
