Résumé
Quantum Approximate Optimization Algorithm (QAOA) is one of the most
short-term promising quantum-classical algorithm to solve unconstrained
combinatorial optimization problems. It alternates between the execution of a
parametrized quantum circuit and a classical optimization. There are numerous
levers for enhancing QAOA performances, such as the choice of quantum circuit
meta-parameters or the choice of the classical optimizer. In this paper, we
stress on the importance of the input problem formulation by illustrating it
with the resolution of an industrial railway timetabling problem. Specifically,
we present a generic method to reformulate any polynomial problem into a
Polynomial Unconstrained Binary Optimization (PUBO) problem, with a specific
formulation imposing penalty terms to take binary values when the constraints
are linear. We also provide a generic reformulation into a Quadratic
Unconstrained Binary Optimization (QUBO) problem. We then conduct a numerical
comparison between the PUBO with binary penalty terms and the QUBO formulations
proposed on a railway timetabling problem solved with QAOA. Our results
illustrate that the PUBO reformulation outperforms the QUBO one for the problem
at hand.