Qudit-based scalable quantum algorithm for solving the integer programming problem

Integer programming is a computationally hard combinatorial optimization problem widely used to model real-world challenges in areas such as finance, engineering, logistics, and operations research. Its classical solution complexity grows exponentially with problem size, making large instances intractable. Many existing quantum approaches suffer from poor resource efficiency because they encode integer variables using qubits. While prior work proposed using higher-dimensional quantum systems to improve encoding efficiency, those approaches lacked scalability for larger problems. In this work, we present a scalable, circuit-based quantum algorithm that uses multiple interacting qudits to efficiently represent and solve integer programming problems, demonstrating a quantum speedup. The algorithm employs a distillation step to separate feasible and infeasible solutions, followed by quantum encoding of the cost function and an optimization procedure based on phase estimation and controlled rotations. We show that the optimal solution is obtained with the highest measurement probability, and that the resulting time complexity offers a significant reduction compared to classical brute-force and exact algorithms for general polynomial integer programming problems.