  Recently, binary optimization has become an attractive research topic due to
the development of quantum computing and specialized classical systems inspired
by quantum computing. These hardware systems promise to speed up the
computation significantly. In this work, we propose a new method to solve
linear systems written as a binary optimization problem. The procedure solves
the problem efficiently and allows it to handle large linear systems. Our
approach is founded on the geometry of the original linear problem and
resembles the gradient conjugate method. The conjugated directions used can
significantly improve the algorithm's convergence rate. We also show that a
partial knowledge of the intrinsic geometry of the problem can divide the
original problem into independent sub-problems of smaller dimensions. These
sub-problems can then be solved using quantum or classical solvers. Although
determining the geometry of the problem has an additional computational cost,
it can substantially improve the performance of our method compared to previous
implementations.
