We give an exact algorithm for minimizing an arbitrary rational quadratic polynomial
xTQx+ cTx+ γ over the integer points of a bounded rational polyhedron Ax ≤b. For n
variables and m inequalities, the running time is
2O(n log(n+1))(m+ 1)O(n)φ_{A,Q}^O(n)(1 + φ)O(1),
where φ_{A,Q} is one plus the maximum binary encoding length of an entry of A or Q, and φ is
the full input encoding length. The polynomial degree in φ is absolute; the encoding of b,c,γ
enters only this fixed-degree factor. We construct a cover of the feasible integer points by cells
with symmetric displacement sets that contain all cell differences and permit feasible moves
in both directions. A negative integer displacement rules out the associated cell. Otherwise,
the quadratic identity supplies supporting inequalities on integer points, allowing exact cell
optimization by an integer-query convex feasibility algorithm. A refinement through scaled
lattices solves the negative-displacement search in 2O(n log(n+1)) times a fixed-degree polynomial
in its input length. Boundary and directional-gradient localization, followed by integer sensitivity,
removes the right-hand sides from the dimension-dependent encoding factor. Combining the
bounded algorithm with a separate unboundedness test extends the method to arbitrary rational
polyhedra.