We devise several classical algorithms to design quantum circuits implementing the time-evolution operator of a Hamiltonian encoding a high-order polynomial binary optimization problem. They are of two kinds: a first algorithm applies a template that gives an efficient circuit for implementing a polynomial containing all possible monomials, followed by a simplification heuristic to reduce the redundancy coming from the absence of some monomials. The second strategy is to use integer linear programs to generate the circuit. Because the set of feasible solutions is too large to be explored efficiently, we implement additional constraints to these programs. We then compare these different formulations by studying the depth of the circuit returned, and the running time of the classical algorithm returning the circuit.