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

Integer programming (IP) is an NP-hard combinatorial optimization problem that is widely used to represent a diverse set of real-world problems spanning multiple fields, such as finance, engineering, logistics, and operations research. It is a hard problem to solve using classical algorithms, as its complexity increases with problem size. Most quantum algorithms for solving IP are highly resource-inefficient because they encode integers into qubits. In [1], the issue of resource inefficiency was addressed by mapping integer variables to qudits. However, [1] has limited practical value due to a lack of scalability to multiple qudits to encode larger problems. In this work, by extending upon the ideas of [1], a circuit-based scalable quantum algorithm is presented using multiple interacting qudits for which we show a quantum speed-up for solving the integer programming problem. The quantum algorithm consists of a distillation function that efficiently separates the feasible from the infeasible regions, a phase-amplitude encoding for the cost function, and a quantum phase estimation coupled with a multi-controlled single-qubit rotation for optimization. We prove that our algorithm yields the optimal solution with the maximum measurement probability. The time complexity for the quantum algorithm is shown to be O(r P(mn 2log d + d n/2/N y s 1/2 + n ε QPE-1)) for a problem with the number of variables n taking d integer values, satisfying m constraints with a precision of ε QPE and r P repetitions required for reaching a success probability P. Compared to the classical time complexity of brute force O(d n) and the classical exact algorithm O( O(n)), it incurs a reduction of about d n/2 in the time complexity (for a polynomial number of repetitions and precision requirements) for solving a general polynomial IP problem.