Solving Integer Linear Optimization Problems with a Fully Quantum Algorithm

Integer Linear Programming (ILP) underpins a wide range of industrial optimization problems but remains computationally challenging due to its NP-complete nature. Classical solvers rely on branch-and-bound and meta-heuristic methods that scale poorly with problem size. In this work, we present a fully quantum version of the Metropolis–Hastings algorithm for ILP. The method implements all arithmetic and constraint-evaluation steps as reversible quantum circuits, enabling coherent exploration of the feasible region without quantum-RAM assumptions. The resulting quantum walk naturally amplifies the amplitudes of high-quality integer solutions and supports integration with amplitude-amplification techniques. Preliminary analyses and simulations suggest that this approach preserves the flexibility of classical Metropolis sampling while providing a pathway toward exploiting quantum parallelism in combinatorial optimization.